CS502 Midterm MCQs Set 2 by VU Topper RM

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

B. ϴ (n2) Page 84

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

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

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

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

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

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) 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

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)

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

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

C. Randomly Page 35

D. Less than 5

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 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

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

A. n Page 36

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

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

_________ 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

The worst case running time of Quick sort algorithm _____.

A. Is quadratic

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

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