CS502 Grand Quiz Dec 2020 by MCS

CS-502 (Fundamentals of Algorithms)

Grand Quiz - Fall 2020

If you found any error in the file, Please correct it accordingly.

Q1. The sequence of merge sort algorithm is:

1. Divide Combine-Conquer
2. Conquer-Divide-Combine
3. Divide-Conquer-Combine
4. Combine-Divide-Conquer

Correct answer: Divide-Conquer-Combine

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

1. 0
2. 1
3. 0/1
4. Fractional

Correct answer: 0/1

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

1. n

Page - 36

b. n2 c. n3 d. log (n)

Q4. In Heap Sort algorithm (using max heap), when every time maximum elements removed from top ________.

1. We call merge Sort Algorithm
2. it becomes Order n2 Algorithm
3. Divide and Conquer strategy helps us
4. We are left with a hole

Correct answer: We are left with a hole

Page – 41

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

1. O (q)

Page - 84

b. O (1) c. O (p x q) d. O (q x r)

Q6. _________ is a method of solving a problem in which we check all possible solutions to the problem to find the solution we need.

1. Plane-Sweep Algorithm
2. Sorting Algorithm
3. Brute-Force Algorithm

Correct answer: Brute-Force Algorithm

google

d. Greedy approach

Q7. The worst case running time of Quick sort algorithm _____.

1. Cannot be quadratic
2. Is quadratic google QuickSort and its Analysis ( ) &
3. ls always Exponential
4. Is linear

Correct answer: Is quadratic google QuickSort and its Analysis ( ) &

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

1. second last
2. Last

Correct answer: Last

Page -41

c. First d. Any

Q9. Quick sort algorithm was developed by -

1. AlferdAho
2. Sedgewick
3. John Vincent Atanasoff
4. Tony Hoare

Correct answer: Tony Hoare

– Google wikipedia

Q10. If Matrix-A has dimensions "3x2" and Matrix-B has dimensions "2x3", then multiplication of Matrix-A and Matrix-B will result a new Matrix-C having dimensions.

1. 3x2
2. 2x3
3. 2x2
4. 3x3

Correct answer: 3x3

Q11. For comparison-based sorting algorithms, it is possible to sort more efficiently than Omega n log(n) time.

1. Always
2. Not

Correct answer: Not

P-54

c. Sometimes d. Sometimes not

Q12. Dynamic Programming approach is usually useful in solving optimization problems.

1. True
2. False

Correct answer: True

Q13. In Sorting the key value or attribute_____ from an ordered domain.

1. Must be
2. Not always
3. May be
4. Occasionally

Correct answer: Must be

Q14. Result of asymptotical analysis of n(n -3) and 4n*n is that _______

1. n(n-1) is asymptotically Less
2. n(n-1) is asymptotically Greater
3. Both are asymptotically Not equivalent
4. Both are asymptotically Equivalent

Correct answer: Both are asymptotically Equivalent

page 23 (4n*n= 4n2)

Q15. Floor and ceiling are ______ to calculate while analyzing algorithms

1. Very easy
2. Usually considered difficult

Correct answer: Usually considered difficult

P-31

c. 3rd Option is missing d. 4th Option is missing

Q16. _____ of reference is an important fact of current processor technology.

1. Defining
2. Assigning
3. Formality
4. Locality

Correct answer: Locality

P-8

Q17. In max-heap, largest element is stored at root node. Where is the smallest element stored?

1. Right Node
2. Leaf Node
3. Middle Node
4. Left Node

Correct answer: Leaf Node