HW7  SAMPLE ANSWERS

1. Whole tree not shown due to size.
                      f(9)
            /          |          \
          f(8)        f(7)         f(6)
         /    \   /    |   \      /    \
       f(6) f(4) f(6) f(5) f(4) f(4)  f(3)
     etc.

     f(9) = 21


2. (a) 3, 4, 0
   (b) Computes the quotient of a divided by b (or a/b using integer
   division, no remainder)

3. (a) 
   3^8 = 3 * 3^7 = 3 * 3 * 3^6 = ... = 3 * 3 * 3 * 3 * 3 * 3 * 3 * 3
   which is 8 multiplies (n multiplies in general --- O(n))
   (b) 
                  3^8
              /         \
          3^4             3^4
        /     \         /     \
      3^2     3^2     3^2     3^2
     /   \   /   \   /   \   /   \
    3     3 3     3 3     3 3     3

   Total number of multiplies is n-1 = O(n)

   (c) 
   3^8:  Compute 3^4 and store. Multiply by itself (no 2nd recursive call)
   3^4:  Compute 3^2 and store. Multiply by itself (no 2nd recursive call)
   3^2:  Compute 3^1 and store. Multiply by itself (no 2nd recursive call)
   3^1 = 3
   So there are 3 multiplies for n = 8. In general O(log n).

4. (a) 
   If you add one disk, say from n to n-1 disks, then to solve that
   problem you have to move n disks first (x moves), move largest disk (1),
   and then move n disks (x moves). Answer: 2x+1
   (b) 
   The maximum number of activation records is n since you have at most
   n subproblems to solve at any given time.

5. 
   public static int sumDigits(int n) {
      if (n < 10) return n;
      else return sumDigits(n/10) + (n%10);
   }

6. 
   public static int numStrings(int n) {
      if (n == 1) return 2;
      if (n == 2) return 3;
      return numStrings(n-1) + numStrings(n-2);
   }

7. 
public static ArrayList<String> getStrings(int n) {
        ArrayList<String> list = new ArrayList<String>();
        if (n == 1) {
                list.add("0");
                list.add("1");
        }
        else {
                ArrayList<String> list2 = getStrings(n-1);
                for (String s: list2) {
                        list.add("0" + s);
                        if (s.charAt(0) != '1')
                                list.add("1" + s);
                }
        }
        return list;
}

8. 
   public void remove(E element) {
       head = remove(head, element);
   }
   private Node<E> remove(Node<E> nodeRef, E element) {
       // remove element from list starting at nodeRef and return
       // reference to this part of list once element is removed
       if (nodeRef == null)
           return null;
       if (nodeRef.data.equals(element))
           return nodeRef.next;
       else {
           nodeRef.next = remove(nodeRef.next, element);
           return nodeRef;
       }
   }