CS502 Quiz 1 by VU Topper RM

Q01. Vu-Topper RM (1 marks)

There are __________ entries in the Edit Distance Matrix. A. ϴ (n)

B. ϴ (n2) Page 84

C. ϴ (n+2) D. ϴ (n + 100)

Q02. Vu-Topper RM (1 marks)

For average-case time analysis of Quick sort algorithm, Pivot selection is on average basis from ______

A. All possible random values Page 50

B. Pivot is input separately C. Values greater than 5

Q03. Vu-Topper RM (1 marks)

As per algorithm of Dynamic Programming, we need to store A. First sub-problem only B. Best solution only

C. Intermediate sub-problems Page 75

D. Final solution only

Q04. Vu-Topper RM (1 marks)

In chain matrix multiplication, table is filled _________ to find the multiplication of matrix. A. row wise B. column wise C. diagonally

D. bottom-to-up Page 86

Q05. Vu-Topper RM (1 marks)

The only way to convert a string of i characters into the empty string is with i deletions, represented as A. E(0.j) =j B. E(i.j) = 1 C. E(0.i) = j

D. E (i.0)=I Page 78

Q06. Vu-Topper RM (1 marks)

If there are θ (n2) entries in edit distance matrix then the total running time is: A. θ (n) B. θ (1)

C. θ (n2) Page 84

D. θ (n logn)

Q07. Vu-Topper RM (1 marks)

In average –case time analysis of quick sort algorithm , the most balanced case for partion is when we divide the list of elements into _.

A. Equal no. of pieces as of input elements

B. Single piece exactly C. Two nearly equal pieces D. Three nearly equal pieces

Q08. Vu-Topper RM (1 marks)

If matrix A of dimension p x q is multiply with matrix B of dimension q x r, then each entry in resultant matrix takes _______ time.

A. O (q) Page 84

B. (1) C. (p x q) D. (q x r)

Q09. Vu-Topper RM (1 marks)

Fibonacci Sequence was named on ______, a famous mathematician in 12th Century. A. Fred Brooks B. Grady Booch

C. Leonardo Pisano Page 73

D. Edgar F. Codd

Q10. Vu-Topper RM (1 marks)

In quick sort algorithm, we choose pivot___________. A. Always the smallest element B. Greater than 5

C. Randomly Page 35

D. Less than 5

Q11. Vu-Topper RM (1 marks)

For comparison-based sorting algorithms, it is possible to sort more efficiently than Omega n log(n) time. A. Always B. Sometimes not

C. NOT Page 54

D. Sometimes

Q12. Vu-Topper RM (1 marks)

The sequence of merge sort algorithm is: A. Divide Combine-Conquer B. Conquer-Divide-Combine

C. Divide-Conquer-Combine Page 27

D. Combine-Divide-Conquer

Q13. Vu-Topper RM (1 marks)

In ______ Knapsack Problem, limitation is that an item can either be put in the bag or not. Fractional items are not allowed. A. 0 B. 1

C. 0/1 Page 91

D. Fractional

Q14. Vu-Topper RM (1 marks)

In Selection algorithm, we assume pivot selection takes theta __________ running time.

A. n Page 36

B. n2 C. n3 D. log (n)

Q15. Vu-Topper RM (1 marks)

In Heap Sort algorithm (using max heap), when every time maximum elements removed from top ________. A. We call merge Sort Algorithm B. it becomes Order n2 Algorithm C. Divide and Conquer strategy helps us

D. We are left with a hole Page 41

Q16. Vu-Topper RM (1 marks)

_________ is a method of solving a problem in which we check all possible solutions to the problem to find the solution we need. A. Plane-Sweep Algorithm B. Sorting Algorithm

C. Brute-Force Algorithm Google

D. Greedy approach

Q17. Vu-Topper RM (1 marks)

The worst case running time of Quick sort algorithm _____.

A. Is quadratic

B. Is linear C. Cannot be quadratic D. ls always Exponential

Q18. Vu-Topper RM (1 marks)

In max heap (for Heap Sort algorithm), when every time maximum element is removed from top we replace it with _____ leaf in the tree.

A. Last Page 41

B. First C. Any D. Second last