Homework 2

Reading assignment

Please read chapter 7 (Heapsort).

Written assignment (assigned October 3, due October 10)

This homework covers the material in chapters 1, 2, and 4 of the textbook.

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. (Each part is worth 5 points.)
   • T(n) = 2 if n = 1,
     T(n) = T(n - 1) + 2 otherwise.

   • T(n) = 1 if n = 1,
     T(n) = T(n/3) + 1 otherwise.
     You may assume that n is a power of 3.

   • T(n) = 1 if n = 1,
     T(n) = 3T(n/3) + n otherwise.
     You may assume that n is a power of 3.

2. Do problem 2-1, parts (b) and (c), on page 38. (Each part is worth 5 points.)

3. Do problem 2-4, part (c), on page 39. (5 points)

4. Give two functions f(n) and g(n) such that it is the case that neither f is O(g) nor g is O(f). (5 points)

5. Consider the functions f(n) = 10000n, g(n) = 10n³, and h(n) = 2ⁿ. For each pair of functions determine the smallest values of n such that the asymptotic ordering of the functions and the ordering by values is the same. (5 points)

6. Corrected: 10/10/01
   Suppose you are given two subroutines, Least and Median. Both have an array as input and return an element of the array: Least returns the smallest element of the array; Median returns the median (i.e., the n/2-th element in the array if it were put in increasing order). You are told that both routines use cn comparisons, for some constant c.

   Consider the sorting algorithms described below. The input is an array of size n.

   Sort1(A)
   if n = 1 return
   else x := Least(A)
   compare x with every element of A
   let A1 be the set of values in A smaller or equal to x, A2 the rest of A.
   B1 := A1
   B2 := Sort1(A2)
   return B1 followed by B2

   Sort2(A)
   if n = 1 return
   else x := Median(A)
   compare x with every element of A
   let A1 be the set of values in A smaller or equal to x, A2 the rest of A.
   B1 := Sort2(A1)
   B2 := Sort2(A2)
   return B1 followed by B2

   • Derive a recurrence relation to count the number of comparisons used by Sort1 and by Sort2. (5 points)

   • Give asymptotic growth rates for the number of comparisons. Which is the more efficient algorithm? (5 points)

   Challenge Problem (optional)

   • Prove that lg n! is Theta(n lg n). (5 points)

   Gerry Brady
   Wed Oct 10 16:52:10 CDT 2001