CS502 Quiz 1 Set 7

Q1. What is the best case time complexity of merge sort?

1. O((n^2logn)
2. O((n^2)
3. O((nlogn)
4. O((nlogn^2)

Correct answer: O((nlogn)

Q2. The important factors to measure the running time of the brute-force 2-d maxima algorithm are

1. Count the number of steps of the pseudo code that are executed
2. The number of comparisons that are performed
3. All of above
4. Count the number of times an element of P is accessed

Correct answer: All of above

Q3. In 3-Dimensional space, a point P has ______________ coordinate(s).

1. (0, Y)
2. (X, 0)
3. (X, Y, Z)
4. (X, Y)

Correct answer: (X, Y, Z)

Q4. Plane-Sweep algorithm can run in _______ time.

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

Correct answer: Θ(n log n)

Q5. The ___________________ is the weighted sum of running times with weights.

1. worse-case time
2. both best-case and average-case.
3. best-case time
4. average-case time

Correct answer: average-case time

Q6. An algorithm is a mathematical entity, which is independent of _______________.

1. Compiler and Programming language
2. Programming language, Compiler and Machine
3. Machine and Programming language
4. Programming language

Correct answer: Programming language, Compiler and Machine

Q7. There are no hard formal rules to the syntax of the ________ code.

1. Basic
2. Programming
3. Pseudo
4. Assembly

Correct answer: Pseudo

Q8. In the following loop statement: for i ← 1 to n For loop executes _______ times.

1. n
2. It is not correct statement
3. log n
4. n2

Correct answer: n

Q9. The definition of theta-notation relies on proving ___________ asymptotic bound.

1. upper
2. lower
3. both lower and upper
4. one

Correct answer: both lower and upper

Q10. ______________ time is the maximum running time over all legal inputs.

1. Best-case
2. Good-case
3. Worst-case
4. Average-case

Correct answer: Worst-case