Homework 6 Solution

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 log2n), 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
      Answer: T(n) = O(log n)
    2. T(n) = 2T(n/2) + log n
      Answer: T(n) = O(n)
    3. T(n) = 2T(n/2) + n
      Answer: T(n) = O(n log n)
    4. T(n) = 2T(n/2) + n log n
      Answer: T(n) = O(n log2n)
    5. T(n) = 2T(n/2) + n2
      Answer: T(n) = O(n2)

     

  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); 
}
    For this algorithm, the recurrence is T(n) = T(n/5) + T(3n/4) + O(n). The code above is derived from a real algorithm: it's the method for doing selection (finding the k-th element) in worst-case linear time.

    3.  

  3. (10 pts) Do problem 3-11 on page 79 of Skiena.
    1. If you know what k is then you know that the smallest element is in position (k mod n) where n is the size of the array.  Thus the largest element is in position (k-1) mod n.  [The answer here depends on whether arrays start at 1 or 0 --- I've assumed they start at 0.]
    2. If you don't know k then the idea is to use binary search to locate the largest element.  We assume that the elements are distinct (if not then the problem can't be solved within the allotted time: consider an array in which all elements are the same except for one large one). We first determine the element A[1]. This element tells us how to locate the "border" between large elements and small elements: large elements are greater than A[1] and should be clustered near the beginning of the array and small elements are less than A[1] and should be clustered near the end of the array.  We now perform binary search, moving right in the array when we encounter a large number and left when we encounter a small one.  Once we locate the border between large and small, we report the number on the left of the border.  This takes time O(log n) because each step cuts the number of elements involved in half.

     

  4. (10 pts) Do problem 3-12 on page 80 of Skiena.
    Note that once you find a number larger than its index position, there is no way for a later number to match its own index position.  In other words, A[i] > i for some i implies that A[i+j} > i+j for all j>0.  This is because we need j numbers to fill in the array positions between A[i+1] and A[i+j]; these numbers need to be both distinct and sorted.  This information is enough to allow a kind of binary search.  The rules are: (1) if A[i] < i then we move right; (2) if A[i] > i then we move left; (3) if A[i]=i then we report it, check on each side of i for an adjacent block of such numbers to report, and quit.

     

  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.
      The recurrence is T(n) = 2T(n/2) + log n.
    2. What is the solution to this recurrence? or How long does it take to build a heap using this method?
      The solution is T(n) = n.  Thus, it takes linear time to build a heap using this method.  A variation of this method is the fastest method known for building a heap: the recursion used here is not really necessary since you can start heap-building at the leaves and work your way up.
    3. How long does it take to build a heap by using Insert to add elements to the heap one at a time?
      Each Insert operation take time O(log n).  Thus the total running time is O(n log n).  It's possible to show that this bound is tight.

Addendum:  For those interested, here's the induction proof for problem 1d: T(n) = 2T(n/2) + n log n.

Claim: T(n) < An log2n where A is a constant (independent of n) yet to be determined.

Basis: T(2) = 2T(1) + 2 = 4 by the recurrence (assuming T(1) = 1).  Thus the claim holds provided A is greater than 2.

Induction: Suppose T(k) < Ak log2k for k < n.  Then using the recurrence, we have
T(n) < 2(A(n/2) log2(n/2)) + n log n = An (log n - 1)2 + n log n.

Rearranging terms, we have:
T(n) < An log2n + [An - (2A-1)n log n].
This gives us the answer we want if we can make the quantity in the brackets be less than 0, but this works for almost any value of A.  In particular it works for A = 3.

Thus, we know T(n) < 3n log2n.  Or T(n) = O (n log2n).