Ques 1.

The maximum subsequence sum problem is defined as follows: If are in Z, find the maximum value  for all  

Ques 2.

a) With the help of an example, explain the following:
i) Algorithm.
ii) Input and output for an algorithm.
iii) Running time of an algorithm.

Ques 3.

b) Using Fig. 7.1 in page 147 of the book as the model, illustrate the operation of Partition on the array

Ques 4.

a) The maximum subsequence sum problem is defined as follows: If  are in Z, find the maximum value  for all  We assume that the answer is 0 if all the  are negative or if the sum is empty. The following algorithm finds a solution to the problem. Here, we assume that  s are stored in the array A.

Maximum-Subsequence

1      

2      

3                    

4                         

5                          

6                                

7                               

8                                               

State precisely a loop invariant for the for loop in line 2–8. Prove that your loop invariant holds and hence conclude that the algorithm works.

b) Analyse the algorithm and find an upper bound for the run time of the above algorithm.

Ques 5.

a) For the set of keys {3, 7, 9, 4, 6, 8, 12} draw binary search trees of height 2, 3, 4, 5 and 6. 
b) Using Fig. 6.3 in page 134 of the book as a model, illustrate the operation of Build-Max-Heap on the array

Ques 6.

a) Show the results of inserting the keys

Ques 7.

Show how mergesort sorts the array

Ques 8.

 For the following set of points, describe how the closest-pair algorithm finds a closest pair of
points: 
(3, 2), (2, 1), (2, 3), (1, 2), (3, 1), (2, 2), (1, 3), (3, −1), (5, −2)

Ques 9.

) Find an optimal parenthesisation of a matrix chain product whose sequence of dimensions is (3, 5, 7, 3, 4).

Ques 10.

a) In the Coin changing problem, we have to give change for n rupees using the least number of coins of a given set of denominations. It is clear that we cannot give change for any

Ques 11.

Show the

Ques 12.

Use Kruskal’s algorithm to find a minimal spanning tree in the graph given in Fig. 2.

Ques 13.

a) Show the comparisons the naive string matcher makes for the pattern  with 

Ques 14.

b) When working modulo how many spurious hits does the Rabin-Karp matcher encounter in the text  when looking for the pattern when looking for the pattern 

Ques 15.

c) Compute the values  that the call - (10117,11591) returns.

Ques 16.

a) Find all the solutions of the equation  (mod  114).

Ques 17.

Let   and  be the point-value representation of 

Ques 18.

Compute the DFT of the vector (−1, 3, 1, −1).