CS502 Quiz 1 Set 2 by VU Topper RM

While solving Selection problem, in Sieve technique we choose pivot

A. Minimum element

B. Randomly C. Average element D. Maximum element

While applying the sieve technique, ___________ subarray will contain all elements that are greater than pivot element x.

A. A[q+1....n]

B. A[1....n] C. A[1....q-1] D. A[q]

The total running time for Selection algorithm is ___________ in n. A. Exponential B. Geometric

C. Quadratic

D. Linear

What is the worst-case time of a quick sort which happens rarely?

1. O(log n)
2. O(n log n)
3. O(n2)
4. O(n)

Correct answer: O(n2)

While applying the sieve technique, ___________ subarray will contain all elements that are less than pivot element x. A. A[q+1....n]

B. A[1....q-1]

C. A[1....n] D. A[q]

A Principal operation for maintaining the heap property is called heapify, it is also called: A. Sifting Up B. Sifting left C. Sifting right

D. Sifting down Page 43

After partitioning array in Quick sort, pivot is placed in a position such that A. Values larger than pivot are on left and smaller than pivot are on right B. Pivot is the first element of array C. Pivot is the last element of array D. Values smaller than pivot are on left and larger than pivot are on right Page 35

Sieve technique is a special case of ___________ strategy. A. Greedy approach B. Graph

C. Divide-and-Conquer

D. Dynamic programming

Selection sort takes theta __________ in the worst case. A. (n)

B. (n^2)

C. nlog(n) D. n(logn)

Array divided into _____ subarrays while applying sieve technique to selection problem. A. 1

B. 2

C. 3 D. 4

If input “n” is odd, then median will be _________ A. n/2 B. n+2 C. (n-1)/2

D. (n+1)/2 Page 34

Quick sort is based on ___________ strategy. A. Graph Theory B. Greedy approach

C. Divide-and-Conquer

D. Dynamic programming

_________ is one of the few problems, where provable lower bounds exist on how fast we can sort.

A. Sorting Page 39

B. Graphing C. Searching D. Both Searching & Sorting

In Quick sort algorithm, the subarray ______________ has elements which are less than pivot element x. A. A[q] B. A[p....r] C. A[q+1....r]

D. A[p....q-1]

In ___________ sorting algorithm, we just need to swap positions of data during the Partitioning function. A. Merge sort B. Counting sort C. Radix sort

D. Quick sort

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 programing, we need to store the result(s) of __________. 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