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: 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)
    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.)
    By the definition of S, S(k+1) = _____________________________________________.
    By the inductive hypothesis, _________________________________________________.
    Substituting into line 1, this gives S(k+1) =  _______________________________
    = (simplify) ______________________________________________________________________________.