## CPSC 220Fall 2007HW 6: More Testing and Recurrence Relations

1. 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.
For each program, make a table showing what input you ran it on and what results you got. Use the information in the table to answer the questions above. Your answers should be in clear, complete sentences.

2. 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) ______________________________________________________________________________.
```