Fall 2007

HW 6: More Testing and Recurrence Relations

- Revisiting HW 5, file sorts.zip
contains class files for four sorting
programs and a number of data files. Download this file, unzip it, and
test each of the four sorting programs as follows:
- Determine whether it sorts correctly.
- Determine whether it satisfies the usage specified in HW 4. If not, explain what behavior is incorrect.
- Use the sorting times to determine whether or not the program really implements the quicksort algorithm. You may find the data files useful for this.

- Find a closed form solution for the recurrence relation below by
filling in the blanks:
S(1) = 3 S(n) = 5 + S(n-1)

**Expand:**S(n) = 5 + S(n-1) = 5 + (____________________________________) (expand) = _____________________________________________ (expand again) General form: _________________________________________________. To get the S term to the base case, let k = ___________________. This gives ____________________________________________________________________________ which is the**guess.****Verify**that given the definition for S above, S(n) = _______________________.Base case (n=1): _______________________________________ Inductive Step: (Hint: If the guess holds for k, it also holds for k+1. Write this out mathematically using the actual guess.) _______________________________________________________________________________. Proof: By the definition of S, S(k+1) = _____________________________________________. By the inductive hypothesis, _________________________________________________. Substituting into line 1, this gives S(k+1) = _______________________________ = (simplify) ______________________________________________________________________________.