CPSC 220
Fall 2007
HW 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) ______________________________________________________________________________.