C455 – Test 1 Sample and Study Guide

• You'll be given any necessary reference material such as algorithms from the text or notes, definitions of W, Q, O and summation formulas.

• You can bring one page of notes on the front and back of an 8.5x11 inch paper and a calculator.

• No cell phones. Please plan to disable your cell phone during the test and make arrangements accordingly.

1. Know the following terminology:

• algorithm, instance of a problem, correct algorithm, data structure
• loop invariant, analyzing an algorithm, random-access machine, input size, running time, functions: constant, linear, quadratic, logarithmic, cubic, exponential; worst-case running time, order of growth, divide-and-conquer, recurrence equation
• floor function, ceiling function, asymptotic upper bound, asymptotic lower bound, asymptotic tight bound
• induction proof, recursion tree
• W, Q, O, ëû, éù
   

2. Loop invariants
   • What three properties must be shown about a loop invariant? Not just the names but a description of each.
   • Given a loop, state the loop invariant.
      
3. Given code containing a loop, perform a loop trace cost analysis.
    

6. 

7. 

8. 
    
9. Given T(n) = T(n * 9/10) + n, use substitution proof to show that T(n) = W(n)

   IH: T(n*9/10)  ³ c n * 9/10

   Show:    T(n) = T(n * 9/10) + n  ³ c n

   Proof:

   T(n) = T(n * 9/10) + n   ³ c n * 9/10 + n   = (c*9/10+1) n   ³ c n

   (c*9/10+1) n ³ c n (c*9/10+1) ³ c Holds for c = 1 > 0

   Base:

   Try n0 = 1, c = 1 T(n) = T(n * 9/10) + n ³ c n T(1) = T(1 * 9/10) + 1  ³ 1 * 1 Holds for n0 = 1, c = 1

    

10. 
    
11.  Given an algorithm, define the recurrence.