Test 2 Solution, CompSci 100e Spring 2011 

1. Re
   La So Re    // top of stack on the right
   Do
   Do Me Re    // front of queue on the left

2. A. find(int x): O(log n)
      findMax(int x): O(1)
      findMedian(int x): O(1)

B. find(int x): O(n)
   findMax(int x): O(n)
   findMedian(int x): O(n)

C. find(int x): O(n)
   findMax(int x): O(n)
   findMedian(int x): O(n log n)

D. O(log N + log M)

3.A.public Node doubleSmallOnes(Node list, int value)
   {
      Node current = list;
      while (current != null)
      {
         if (current.info < value)
            current.info = current.info * 2;
         current = current.next;
      }
      return list;
   }

3.A.public Node doubleSmallOnes(Node list, int value)  // alternative soln
   {
      if (list==null)
         return null;
      if (list.info < value)
         list.info = list.info * 2;
      list.next = doubleSmallOnes(list.next, value);
      return list;
   }

B. public Node addSumNodeAtEnd (Node list)
   {
      if (list == null)
      {
         return new Node(0, null);
      }
      Node current = list;
      int sum = list.info;
      while (current.next != null)
      {
         current = current.next;
         sum += current.info;
      }
      current.next = new Node(sum, null);
      return list;
   }

B. public Node addSumNodeAtEnd (Node list)  // Alt Soln
   {
      int sum = 0;
      Node cur = list;
      while (cur != null)
      {  
         sum += cur.info;
         if (cur.next == null)  // last node
         {
            cur.next = new Node(sum, null);
         ]
         cur = cur.next;
      }
      return list;
   }

B. // Alt 2 Recursive Soln
// if you want to use recursion, many times you will call another
//   method and make that method the recursive one. Then you can setup 
//   parameters and return value so they will work well for what you want to do
public Node addSumNodeAtEnd (Node list)  
{
   if (list == null)
       return null;
   addSumNodeAtEndHelper(list,0);
   return list;
}
// calls this recursive method
public void addSumNodeAtEndHelper(Node list, int total)  // helper
{
   total += list.info;
   if (list.next == null)
   {
       list.next = new Node(total, null);
   }
   else
   {
      addSumNodeAtEndHelper(list.next, total);
   }
}

C1. list -> 4 -> 8

C2. The mystery method removes negative numbers from the list. 

C3. T(n) = T(n-1) + O(1)    this is O(n).

4.A. Note: For the standard binary search tree insert, once a node is
placed into the tree, it does not move when other nodes are inserted into
the tree. 

       21
    /      \
   10       32
      \    
       15
     /    \
    12    18

4B. preorder: 21, 10, 15

4C. postorder: 12, 18, 15

4D. Note: When another number is added to a heap, it is always added on the
last level of the tree in the next spot from left to right. If that level
is full it is added as the leftmost node on the next new level. 

1. 21

2.  21
   /
  32

3.  10
   /  \
  32   21

4.   10
   /    \
  15     21
 /
32

5.   10
   /    \
  15     21
 /  \ 
32  18

6.   10
   /    \
  15     12
 /  \    /
32  18  21

4E.  12
   /    \
  15     21
 /  \    
32  18  

4F  Note: Your tree shape may look different but here is the order things
are put together. First b and d with a root with value 3. Next e with
them for a root with value 6. Next i and k together with root value 9. Then
L with the root 6 for a new root with value 12. Then s and u together for
root value 15. Then the two roots 9 and 12 are put together with root value
21. Then the 15 and 21 roots joined together. 

Here is a possible trie. 

          36
       /      \
     15        21
   /   \     /    \
   s   u    9      12
           / \    /   \
          i   k   6    L
                 / \ 
                3   e
               / \
              b   d

G. 11001 01 101 1101  (spaces would not be there - show the code for each
letter)

5.A

   public int weight(TreeNode root)
   {
      if (root == null)
         return 0;
      return root.info + weight(root.right) 
          + weight(root.left);      
   }

5.B.
A. mysteryTree returns the number of nodes in the tree whose
info field is greater than the sum of all the info fields of 
its children and descendants. 

5.C. First you need to figure out the running time of the weight function. 
The recurrence for it is T'(n) = 2T'(n/2) + O(1) = O(n).
T'(n) is the time it takes to solve weight when you have n nodes in the
tree. 
I used T' to distinquish between T.

Now let T(n) be the time to solve NumNoRC when there are n nodes. 

T(n) = 2T(n/2) + O(n)  which is O(n log n).
This is the correct anser. 

NOTE: DO NOT WRITE 
T(n) = 2T(n/2) + 2T(n/2) + O(1) = 4T(n/2) + O(1). 
THIS IS WRONG! The T's are being used for two different methods. 
Only one is the recursive call. 
The correct answer is 
T(n) = (2 recursive calls) plus (the two calls to the the weight method each
       with n/2 nodes) plus (time to put the answer together)
     = 2 T(n/2) + O(n/2) + O(n/2) + O(1)
     = 2 T(n/2) + O(n)  (simplified)


5.D.
   public int NumNoRC(TreeNode root)
   {
      if (root == null)
      {
         return 0;
      }
      if (root.right == null)
      {
         return 1 + NumNoRC(root.left);
      }
      return NumNoRC(root.left) + NumNoRC(root.right);
   }
   
6 A. false
  B. false
  C. squares visited should be marked with some value so they are not visited again. When
  there are no more squares to visit, the recursion will end.    
 
  D. 
    public boolean accessChest(int xPos, int yPos, int size)
    {
       if (xPos<0 || xPos >= size || yPos < 0 || yPos >= size)
          return false;
       if (castle[xPos][yPos]== 'C')
          return true;
       if (castle[xPos][yPos] == 'X')
          return false;
       // mark a spot with 'v' when visited
       if (castle[xPos][yPos] == 'v')
          return false;
       //otherwise must be a '.'
       castle[xPos][yPos] = 'v';   // mark the spot visited
       // try other spots
       return accessChest(xPos, yPos+1, size) ||
       accessChest(xPos,yPos-1, size) ||
       accessChest(xPos+1,yPos, size) ||
       accessChest(xPos-1,yPos, size);    
    }