CS 502 Quiz # 2

1) In quick sort algorithm, we choose pivot _____________

1. Greater than 5
2. Randomly
3. Less than 5
4. Always the smallest element

2) We can use the ____________ property to devise a recursive formation of the edit distance problem.

1. Algorithmic
2. Real
3. Small substructure
4. Optimal substructure

3) Selection sort is a _________ sorting algorithm.

1. Stable
2. Not In-Place
3. In-partition
4. In-Place

4) Dynamic Programming algorithms often use some kind of __________ to store the results of intermediate sub-problems.

1. Loop
2. Variable
3. Table
4. Stack

5) Suppose we have 4 matrices A, B, C, D. What is correct expansion of m [1,2] in chain matrix multiplication

1. m [1, 2] = m [1, 2] + m [1, 2] + P0. P1. P2
2. m [1, 2] = m [1, 1] + m [2, 2] + P0. P1. P2
3. m [1, 2] = m [1, 2] + m [2, 2] + P0. P1. P2
4. m [1, 2] = m [1, 1] + m [2, 2] + P0. P1. P2

6) In chain matrix multiplication, if there are n items, there are _________ ways in which outer most pair of parentheses can placed

1. n+1
2. 2n
3. N-1
4. N^2

7) In Fibonacci Sequence, each term is calculated by ___________ previous __________ terms.

1. Adding, Three
2. Multiplying, Two
3. Subtracting, Two
4. Adding, Two

8) Insertion sort is a ___________ sorting algorithm.

1. In-place
2. Not In-Place
3. In-partition
4. Unstable

9) If there are Θ ( ) entries in edit distance matrix then the total running time is:

1. Θ (1)
2. Θ (n log n)
3. Θ ( )
4. Θ (

10) Consider two matrices A and B, where A is 10*30 and B is 30*40. What is correct number of multiplications requiring to multiply A and B

1. 10*30*40
2. 30*40
3. 10*30
4. 30*30