Computer Science 3650
Spring 2012
Solutions to Practice Questions for Quiz 4

1. After sorting, what is the amortized time per step of Graham's algorithm?

   The amortized time is O(1), since n steps take O(n) time.

2. Let p₁, ..., p_n be a list of points in the plane whose y-coordinates are all positive. The polar angle of point (x, y) is the angle formed with the x-axis by the vector from the origin (0,0) to point (x,y). For example, the polar angle of point (1,1) is 45 degrees (or π/4 radians).

   Give an O(n log(n)) time algorithm to sort list of points p₁, ..., p_n into counterclockwise order by polar angle.

   It is just a matter of determining how to compare two points p and q. Say that p < q, meaning that q is counterclockwise from p, if going from (0,0) to p then to q involves making a left turn at p. Using cross products, we say that p < q if qxp < 0.

   Now sort the points according to that ordering, using a general (comparison-based) sorting algorithm.

3. How does a dynamic programming algorithm avoid the work associated with recomputation of values?

   You avoid repeating computations by writing down the answers and consulting them later.

4. The fibonacci numbers f₀, f₁, f₂, ... are define by

   f0	=	0
   f1	=	1
   fn	=	fn-1 + fn-2 (for n > 1)

   The following algorithm is based directly on this definition.

     f(n)
        if(n < 2) return n
        else return f(n-1) + f(n-2)
   

   Is that an efficient algorithm? If so, explain why. If not, explain not and describe how to make the algorithm efficient.
   No, this is not an efficient algorithm. Looking at the recursion tree for f(10), you see (forgive the Ascii art)

                     f(10)
                    /     \
                f(9)       f(8)
               /    \     /    \
            f(8)   f(7) f(7)   f(6)
   

   which shows that there are repeated computations.

   To improve the algorithm, just record the answers.

     f(n)
        int[] F = new int[n+1]
        F[0] = 0
        F[1] = 1
        for i = 2,..., n do
          F[i] = F[i-1] + F[i-2]
        return F[n]
   

5. The coin changing problem is as follows. You are given a list of integer coin values v₁, ..., v_k, where v₁ = 1 and v₁ < v₂ < ... < v_k. You are also given a desired amount A of change, where A is a positive integer. The goal is to find out the fewest coins whose values total exactly A, where each coin must have one of the given values. You do not need to list the coins, only say how many are used.

   For a given list of coin values, let C(A) be the smallest number of coins whose total value is exactly A. Then the goal is to determine C(A).

   For example, suppose the coin values are 1, 5, 10 and 25. (So you have pennies, nickles, dimes and quarters.) You can make 30 cents as 25 + 5, so C(30) = 2 (for these coin values), and you can make 52 cents as 25 + 25 + 1 + 1, so C(52) = 4 (again, for these coin values).

   1. Write recurrences for C(A). What is C(1)? What is C(A) for A > 1? You can make use of the coin values v₁, ..., v_n.

      C(1)	=	1
      C(A)	=	minj = 1k[where vj ≤ A](1 + C(A - vj))

   2. Give an efficient algorithm to compute C(A) for a given positive integer A. If must work for any list that satisfies the requirements of the problem.

        C(A)
          int[] CC = new int[A]  (index from 1)
          CC[1] = 1
          for i = 2,...,A do
            least = A
            for j = 1,...,k do
              if vj ≤ i and least > 1 + CC[i - vj]  then
                least = 1 + CC[i - vj]
              CC[i] = least
          return CC[A]