Peg Game

Assignment 2

Objective: Understanding of recursive solutions, data structures.

Assignments from Book: Do the following problems from the Cormen book:

• 3.1-2 - Show that for any real constants a and b, where b > 0,
             
                  (n + a)^b = Θ(n^b).
  

• 3.1-3 - Explain why the statement "The running time of algorithm A is at least Ο (n²)" is content-free.  Also, why is saying W (1) content-free?

• 3-1  Let
  
  where ad > 0, be a degree-d polynomial in n, and let k be a constant.  Use the definitions of the asymptotic notations to prove the following properties:
  a. If k >= d, then p(n) = Ο (n^k)
  b. If k <= d, then p(n) = Ω (n^k)
  c. If k = d, then p(n) =  Θ (n^k)

• Let f(n) = 7n³ and g(n) = 21n²+9n.  Formally prove (mathematically) that g(n) = Ο (f(n)).
   

Program Description: In this assignment,

Program Requirements: The program should calculate the total number of winning paths for a given board.  Note, the program does not need to be graphical!

Example:

Program Turnin: Use WebSubmit to submit your written assignment.  Programs will be demonstrated in class.