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.
-
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.
-
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 :
-
sorted input
-
reverse-ordered input
-
random input
Exercise 4 [10]: Prove that : T(N) = (1/N) | Sumi=0N-1
T(i) | + cN = O(N)
Exercise 5 [10]:
-
Prove that any comparison based algorithm to sort 4 elements requires 5
comparisons.
-
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 :
-
Give an O(N2) algorithm to solve this problem.
-
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