CS502 Midterm Past Paper 3

CS502-ALGORITHMS

MID –FALL2007

Q1. Total time for heapify is:

Ο (log2 n) Ο (n log n) Ο (n2 log n) Ο (log n)

Q2. Solve the recurrence using iteration method and also find time complexity (Θ notation)

T (n) = C + O (1) + T (n-1) T (1) =1 and C is a constant.

Q3. Suggest the criteria for measuring algorithms. Also discuss the issues need to be discussed in the algorithm design.

Q4. If an algorithm has a complexity of log 2 n + nlog 2 n + n. we could say that it has complexity

O(n) O( n log2 n) O(3) O( log2 ( log2 n )) O ( log2 n)

Q5. Let the set P = {(1, 13), (2, 9), (3, 15), (4, 12), (5, 14), (6, 6), (7, 3), (8, 10), (9, 2), (10, 8), (11, 9), (13, 6), (15, 3), (18, 5)}. You are required to give the final state of stack after the execution of sweep line algorithm for 2d-maxima. No intermediate steps or graphics to be shown.

Q6. Suppose we have hardware capable of executing 106 instructions per second. How long would it take to execute an algorithm whose complexity function is T (n) = 2n2 on an input of size n = 108?

Q7. In RAM model instructions are executed

One after another Parallel Concurrent Random

Q8. In selection algorithm, because we eliminate a constant fraction of the array with each phase, we get the

Convergent geometric series Divergent geometric series None of these

Q9. Due to left-complete nature of binary tree, heaps can be stored in

Link list Structure Array None of above