EXAM 2 SAMPLE ANSWERS (+ version)

1. 
(a) for (String s: list)
        if (s.length() > 6)
            System.out.println(s);

(b) Iterator iter = list.iterator();
    while (iter.hasNext()) {
        String s = iter.next();
        if (s.length() > 6)
            System.out.println(s);
    }

(c) 5, CARNEGIE

2.
(a) Queue (front to rear): 3 5 2 8 4 9 1 6
    Dequeue 3
    Then dequeue/enqueue 3 times:
    Queue (front to rear): 4 9 1 6 5 2 8
    Dequeue 4
    Then dequeue/enqueue 4 times:
    Queue (front to rear): 2 8 9 1 6 5
    Dequeue 2
    Then dequeue/enqueue 2 times:
    Queue (front to rear): 1 6 5 8 9

(b) FIFOQueue<String> q2 = new ListQueue<String>();
    while (!q.isEmpty()) {
        String s = q.dequeue();
        if (s.length() != 4) q2.enqueue(s);
    }
    while (!q2.isEmpty()) 
        q.enqueue(q2.dequeue());

3.
(a)
public class Battery extends PowerCell {
    public Battery() {
        powerInMinutes = 40;
    }
    public void charge(int minutes) {
        powerInMinutes += minutes;
        if (powerInMinutes > 200)
             powerInMinutes = 200;
    }
}

(b) 
public class SpecialBattery extends Battery {
    private boolean ledIsOn;
    public SpecialBattery() {
        super();   // optional in this case
        ledIsOn = false;
    }
    public void charge(int minutes) {
        super.charge(minutes);
        if (getPower() >= 20) ledIsOn = false;
    }
    public void discharge(int minutes) {
        super.discharge(minutes);
        if (getPower() < 10) ledIsOn = true;
    }
}

(c) VALID, INVALID

4. (a) s.length() <= 1
       s.charAt(0) != s.charAt(s.length()-1)
       isPalindrome(s.substring(1,s.length()-1))

   (b) row == 0 && col == 0
       row < 0 || col < 0 || maze[row][col] == 'O'
       pathExists(maze, row-1, col) || pathExists(maze, row, col-1)

   (c)             g(6)
                 /      \
               g(5)      g(3)
              /    \
            g(4)   g(2)
           /    \
         g(3)  g(1)

         g(6) = 9

5. (a)          6
            /       \
           3         9
          / \       /
         2   4     8
              \   /
               5 7
          
         

   (b)         46            OR           71
             /    \                     /    \
           24      88                 24      88
          /  \    /  \               /  \    /  \
        11    30 71   96           11   46  79  96
                  \                     /
                   79                 30

   (c)  O(log n), O(n), O(n), O(n)
   
   (d)  preorder  IDCABHEGF
        inorder   ACBDIEHFG
        postorder ABCDEFGHI

6. (a)          2
              /   \
             3     5
            / \   / \
           6   4 9   8
          /
         7

   (b)         69
             /    \
           53      55
          /  \    /  \
        42   16  40  28
        /
      31

   (c) (int)(i/2), 2*i, 2*i+1

   (d) Since y is a parent of x in the maxheap, y > x.
       Thus, since z > y and y > x, then z > x already so the maxheap
       property is satisfied already.

7. (a) 21 34 85 72 63 90 58      OR  90 34 85 72 21 63 58
       (if sorting low to high)      (if sorting high to low)

   (b) 21 34 58 63 72 90 85
       (partition includes swap of pivot into correct position in this answer)

   (c) insertion, merge, Google, merge

   (d) (i) 36, 36    (ii) 8, 36

   (e) This merge is stable since if left[i] == right[j], the left
       element is picked first before the right element, so the relative
       order of the equal elements will not change in the final table.

   (f) Use bucket sort, one bucket per grade, since there are only 4
       categories to sort into. This sort takes O(n) time.
 
8. (a)

public E getMaximum() {
    if (root == null) return null;
    return getMaximum(root);
}
private E getMaximum(BTNode<E> localRoot) {
    if (localRoot.right == null)
        return localRoot.data;
    return getMaximum(localRoot.right);
}

(b)

public E getMinimum() {
    if (root == null) return null;
    BTNode<E> nodeRef = root;
    while (nodeRef.left != null) {
        nodeRef = nodeRef.left;
    return nodeRef.data;
}