Homework 3

Reading assignment

Please read chapters 8 (Quicksort) and 9 (sorting in linear time).

Written assignment (assigned October 9, due October 17)

This homework covers the material in chapter 7 of the textbook, as well as review exercises on recurrences.

Please note: your solutions should be readable, and justifications should be given for steps in the proofs. Elegance counts!

1. Solve the following recurrences. Prove your answers by induction. You may assume that n has a convenient form (e.g., n is a power of 3) if this is helpful. (Each part is worth 5 points.)
   • T(n) = 1 if n = 1,
     T(n) = 2T(n/2) + n³ otherwise.

   • T(n) = 1 if n = 1,
     T(n) = T(7n/10) + n otherwise.
     

   • Corrected: 10/15/01
     T(n) = T(n/2) + T(n/3) + n
     You may assume that T(n) is a suitable constant for n = 1, 2, and 3.

2. Do exercise 7.3-3 on page 147. (10 points)

3. Do exercise 7.4-2 on page 149. (10 points)

4. Do exercise 7.5-6 on page 151. (10 points)

5. Do problem 7-1 on page 152. (Each part is worth 5 points.)

6. Do problem 7-2 on page 152. (Each part is worth 2 points.)

7. Consider the following two statements about a function f(n) > 1:
   • f(n) = O(n^{lg n}).
   • f(n) = n^{O(lg n)}.
   The notation in the second statement means that f(n) = n^g(n) for some function g(n) which satisfies the relation g(n) = O(lg n).

   Answer the following questions:

   1. Does f(n) = n^{O(lg n)} follow from f(n) = O(n^{lg n})?
   2. Does f(n) = O(n^{lg n}) follow from f(n) = n^{O(lg n)}?

      (Each part is worth 5 points.)

   Gerry Brady
   Tue Oct 9 13:42:10 CDT 2001