CS 4625 Spring 2001
Assignment 2

Handed out: Fri, Feb 02
Due: Thurs, Feb 27
Total Marks: [110]

Exercise 1 [10]:  Give an algorithm to find all nodes less than some value X, in a binary
heap. Your algorithm should run in O(K), where K is the number of nodes output.

Exercise 2 [20]: Each deleteMin operation uses 2 lg N comparisons in the worst case.

1. Propose a scheme so that the deleteMin operation uses only log N + log log N + O(1) comparisons between elements. This need not imply less data movement.
2. Extend your scheme in part (1) so that only log N + log log log N + O(1) comparisons are performed.

Exercise 3 [10]: Determine the running time of mergesort for :

1. sorted input
2. reverse-ordered input
3. random input

Exercise 4 [10]: Prove that : T(N) = (1/N) | Sum_i=0^N-1  T(i) |  + cN  = O(N)

Exercise 5 [10]:

1. Prove that any comparison based algorithm to sort 4 elements requires 5 comparisons.
2. Give an algorithm to sort 4 elements in 5 comparisons.

Exercise 6 [10]:  We are given an array that contains N numbers. We want to determine if there are two numbers whose sum equals a given number K. For instance, if the input is 8, 4, 1, 6, and K is 10, then the answer is yes (4 and 6). A number may be used twice. Do the following :

1. Give an O(N²) algorithm to solve this problem.
2. Give an O(N log N) algorithm to solve this problem (Hint: sort the items first. After that is done, you can solve the problem in linear time).

Exercise 7 [30]: Problem 7-2 page 152

Exercise 8 [10]: Exercise 8-2-4 page 160