Homework 6

CS409 - Spring 2000

Due: Thursday, Mar 16

Note added on 3/15: Problem 1d on HW06 is more difficult than I meant it to be.  The solution to 1d is T(n) = O(n log²n), but this requires an inductive proof.

1. (5 pts) Give tight big-O bounds for T(n) in each of the following recurrences.  Assume T(1) = 1.
   1. T(n) = T(n/2) + 1
   2. T(n) = 2T(n/2) + log n
   3. T(n) = 2T(n/2) + n
   4. T(n) = 2T(n/2) + n log n
   5. T(n) = 2T(n/2) + n²

    

2. (5 pts) Here's the pseudocode for a recursive algorithm.  What is the recurrence for this algorithm?

   doSomething(array A) returns integer {
   	n = size(A);
   	if (n < 5) return some-easy-to-compute-value;
   	Divide A into n/5 groups each of size 5; 
   	Choose an item from each group and place it in array B; 
   	i = doSomething(B); 
   	Use i (somehow) to select just part of A in O(n) time; 
   	Copy this part of A into array C (C is of size 3n/4);
   	return doSomething(C); 
   }

3. (10 pts) Do problem 3-11 on page 79 of Skiena.

    

4. (10 pts) Do problem 3-12 on page 80 of Skiena.

    

5. (10 pts) Divide & Conquer can be used to design a technique for building a heap. Consider the following algorithm: Choose some item x (the first item in the array, for instance).  Make the remaining items into two separate, smaller heaps (recursively). Use x as the root of a heap with the two smaller heaps as the children of x and use the bubble-down operation (as discussed in class) to fix up the heap.
   1. What is the recurrence relation for this algorithm? Note that all of the operations described above can be done in-place (i.e., we don't need any extra space aside from the array holding the items), so there is no cost for copying data between data structures.
   2. What is the solution to this recurrence? or How long does it take to build a heap using this method?
   3. How long does it take to build a heap by using Insert to add elements to the heap one at a time?