EXAM 2 SAMPLE ANSWERS (* version)

1. 
(a) for (String s: list)
        if (s.length() > 0 && s.charAt(0) == 'A')
            System.out.println(s);

(b) Iterator iter = list.iterator();
    while (iter.hasNext()) {
        String s = iter.next();
        if (s.length() > 0 && s.charAt(0) == 'A')
            System.out.println(s);
    }

(c) 6, MELLON

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

(b) FIFOQueue<String> q2 = new ArrayQueue<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 = 20;
    }
    public void charge(int minutes) {
        powerInMinutes += minutes;
        if (powerInMinutes > 100)
             powerInMinutes = 100;
    }
}

(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() >= 10) ledIsOn = false;
    }
    public void discharge(int minutes) {
        super.discharge(minutes);
        if (getPower() < 10) ledIsOn = true;
    }
}

(c) INVALID, VALID

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(5)
                 /      \
               g(4)      g(2)
              /    \
            g(3)   g(1)
           /    \
         g(2)  g(0)

         g(5) = 5

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

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

   (c)  O(n), O(log n), O(n), O(n)
   
   (d)  preorder  IDBACHFGE
        inorder   ABCDIFHEG
        postorder ACBDFEGHI

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) 29 34 72 85 61 90 58      OR  90 34 72 85 29 61 58
       (if sorting low to high)      (if sorting high to low)

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

   (c) insertion, merge, bubble, merge

   (d) (i) 28, 28    (ii) 7, 28

   (e) This merge is not stable since if left[i] == right[j], the right
       element is picked first before the left element, so the relative
       order of the equal elements will 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 getMinimum() {
    if (root == null) return null;
    return getMinimum(root);
}
private E getMinimum(BTNode<E> localRoot) {
    if (localRoot.left == null)
        return localRoot.data;
    return getMinimum(localRoot.left);
}

(b)

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