CSC 321 Spring 2002

Assignment 2

Due: Wednesday, April 17^th (new due date)

Write up solutions to each of the following problems:

1. Prove the following, using the definition of Q (Theta):
   • n³-7n + 12  =  Q(n³ ).
   • 11n²-32n+14  =  Q(n² ).
     
2. Using the definition of big-O, prove that f(n) + g(n) = O(max(f(n), g(n)).  Make no assumptions about the functions f and g.
   
3. Suppose you have 12 coins that are all supposed to be gold coins of the same weight, but you know that one coin is fake and weighs less than the others. You have a balance scale on which you can put any number of coins on each side.  It will indicate whether the two sides are the same or whether one side is lighter than the other.  Outline an algorithm for finding the fake coin. How many times must you use the scale to find the fake coin?  Generalize this to the case where you have n coins.
   
4. Problem 2.3-7 (p. 37 in CLRS).