CS 3620 - Spring 2002
Assignment 4

Handed out: Mon March 25 2002
Due: Mon April 08 2002
Total Marks: [100]

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.

Solution : Perform a preorder traversal of the heap.

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.

Solution: If the heap is organized as a (min) heap, then starting at the hole at the root, find a path down to a leaf by taking the minimum child. This requires roughly logN comparisons. To find the correct place where to move the hole, perform a binary search on the logN elements. This takes O(log log N) comparisons.
2. Extend your scheme in part (1) so that only log N + log log log N + O(1) comparisons are performed.

Solution: Find a path of minimum children, stopping after log N - log log N levels. At this point, it is easy to determine if the hole should be placed above or below the stopping point. If it goes below, then continue finding the path, but perform the binary search on only the last loglogN elements on the path, for a total of  logN + log log log N comparisons. Otherwise, perform a binary search on the first log N - log log N elements. The binary search takes at most log log N comparisons, and the path finding took only log N - log log N, so the total in this case is log N. So the worst case is the first case.

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

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

Solution: The merging step always takes O(N) time, so the sorting process takes O(N log N) time on all inputs.

Exercise 4 [10]:

1. Prove that any comparison based algorithm to sort 4 elements requires 5 comparisons.

Solution: log 4! = log 24 < log 32 = log 2^5 = 5
2. Give an algorithm to sort 4 elements in 5 comparisons.

Solution: Compare and exchange (if necessary) a1 and a2 so that a1>=a2, and repeat with a3 and a4. Compare and exchange a1 and a3. Compare and exchange a2 and a4. Finally, compare and exchange a2 and a3.

Exercise 5 [10]  :  exercise 7.42 page 299

Solution:

• a) log 5! = log 120 < log 128 = log 2^7 = 7
• b) Compare and exchange (if necessary) a1 and a2 so that a1 >= a2, and repeat with a3 and a4 so that a3 >= a4. Compare and exchange (if necessary) the two winners, a1 and a3. Assume without loss of generality that we now have a1 >= a3 >= a4, and a1 >= a2 (the other case is obviously identical). Insert a5 by binary search in the appropriate place among a1,a3,a4. this can be done in two comparisons. finally, insert a2 among a3,a4,a5. If it is the largest among those three, then it goes directly after a1 since it is already known to be larger than a1. This takes two more comparisons by a binary searh. The total is thus seven comparisons.

 Exercise 6 [10]

Suppose that the splits at every level of quicksort are in the proportion 1- a to a, where 0 < a < 1/2 is a constant. Show that the minimum depth of a leaf in the recursion tree is approximately - log(n) / log(a) and the maximum depth is approximately  -log(n)/log(1-a) (don't worry about integer round-off).

Solution:

• The shortest branch corresponds to log_1/a(N) =  (log(N)) / (log(1/a)) = - log(N) / log(a)
• The longest branch corresponds to log_1/1-a (N) = (log N) / (log(1/1-a)) = - log(N) / log(1-a)

Exercise 7 [10]

The running time of quicksort can be improved in practice by taking advantage of the fast running time of insertion sort when its input is "nearly" sorted. When quicksort is called on a subarray with fewer than k elements, let it simply return without sorting the subarray. After the top-level call to quicksort returns, run insertion sort on the entire array to finish the sorting process. Argue that this sorting algorithm runs in O(nk + n log(n/k)) expected time. How should k be picked, both in theory and in practice ?

Solution:

• T(N) = running time of quicksort + running time of insertion sort (for the remaing N/K arrays of size K(or less than K))
•         =   N ( log N - log K) + N/K (K^2) = N log(N/K) + NK
• In theory, K has to be chosen such that : N K + N log (N/K) = N log N ==> K = log N ( K can't be more than log N otherwise the total running time will be more than N log N).
• In practice, K should be the largest list length on which insertion sort is faster than quicksort.    

Exercise 8 [10] : exercise 4.6 page 171

Solution:
This can be shown by induction.
Alternatively, let N = number of nodes, F = number of full nodes, L = number of leaves, and H = number of half nodes (nodes with one child). Clearly, N = F + H + L. Further, 2F + H = N - 1 (hint: see exercise 4.4). Subtracting yields L - F = 1.

Exercise 9 [10] : exercise 4.45  page 175

Solution:
The function below is O(N) since in the worst case it does a traversal on both t1 and t2.
bool similar (Node *t1, Node *t2)
{

if (t1 == NULL || t2 == NULL)

return t1 == NULL && t2 == NULL;

return similar (t1->left, t2->left) && similar (t1->right, t2->right);

}

Hand in

• In class (Mon April 08)
• or via e-mail to mark3620@cs.uleth.ca with a backup copy to mouhoub@cs.uleth.ca