Up:assignments
 
 

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) | Sumi=0N-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(N2) 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
 



 
 Malek Mouhoub 2001-02-01