CS502 Midterm Past Paper 1

A PC like computer can perform 10 operations per second. Consider that we have five

CS502 Fundamentals of Algorithms · Mid Term Examination - November 2004 · Time Allowed: 90 Minutes · Instructions

1. The duration of this examination is 90 Mins.
2. This examination is closed book, closed notes, closed neighbors.

Q4. Some of the examination consists of multiple-choice questions. Choose only one choice as your answer.

1. If you believe that two (or more) of the choices are correct for a particular question, choose the best one.
2. On the other hand, if you believe that all of the choices provided for a particular question are wrong then select the one that appears to you as being the least wrong.

Questions: 7

Q1. Total

Marks : 15

different algorithms for a specific problem. For each algorithm i, we know the number of operations Ti(n) it will perform on a problem of size n:

T1(n) = 6000000 ·n Describe an efficient algorithm to find the median of a set of 10 integers; it is known that T2(n) = 60000 ·nlogn

T3(n) = 0.003 ·n

T4(n) = 10 �6

n

T5(n) = 10 �18 n

For each algorithm compute the size nmax of the largest problem the respective algorithm can solve within 1 second, 1 minute and 1 hour. Enter the maximal problem sizes into the following

Q2. Marks : 5

there are fewer than 100 distinct integers in the set.

Q3. Recall the counting sort algorithm, where

Marks : 20

n is the number of elements to be sorted each element is an integer in the range 1 to k A is the input array, of size n B is the final sorted output array C is the intermediate array of size k

1: for i = 1 to k 2: C[i] = 0

4: C[A[i]] = C[A[i]] + 1 5: for i = 2 to k 6: C[i] = C[i] + C[i-1] 7: for i = n downto 1 8: 9: B[C[A[i]]] = A[i] C[A[i]] = C[A[i]] - 1

(a) For the input array [6,3,7,5,4,3,3,2,8,9,1,6], and k = 9, specify the contents of the arrays B and C · (4 points) after the second for-loop (line 3); C = · (2 points) after the third for-loop (line 5); C = · After each of the first three iterations of the fourth loop (line 7);

1. (3 points) B= C= 2. (3 points) E(i, j �1)  1 E(i, j) = min��

� E(i�1, j�1) ifA[i] B[ j]� B= C= 3. (3 points) B= C= (b) (5 points) Suppose that the for-loop on line 7 above, is modified as follows:

Will the algorithm still sort the input? If no, explain why not. If yes, what is the effect of this Modification to the algorithm and the output?

Q4. When using merge sort to sort an array, do the recursive calls to merge sort depend on the

number of elements in the array, the values of the elements or both? Briefly explain.

Q5. Marks : 5

Marks : 5

Insertion sort can be expressed as a recursive procedure as follows: In order to sort array A[1..n], we recursively sort array A[1..n-1] and then insert A[n] into the sorted array A[1..n-1]. Give an equation that describes the overall running time of this algorithm on an input array of size n, in terms of the running time on smaller input.

T(n) =

Q6. Marks : 10

Compute the edit distance and edit scripts for the strings "HEAP" and "CHEAT". Recall that the edit distance recurrence is

� E(i�1, j) 1�

� E(i�1, j�1) 1 ifA[i] B[ j]�

Q7. Using big-oh notation, give the running time of the following piece of code. Briefly

justify your answer.

for (i = 1; i <= n; i++) for (j = 1; j <= n/2; j++) for (k = 1; k <= j; k++) cout << "hello world\n";