HW6 - SAMPLE ANSWERS

1.
Queue from front to rear after a knight leaves:
1 2 3 4 5 6 7 8 9 10 (original queue)
7 8 9 10 1 2 3 4 5
3 4 5 7 8 9 10 1
10 1 3 4 5 7 8
8 10 1 3 4 5
8 10 1 3 4
10 1 3 4
3 4 10
3 4
3

(b) 
public ArrayList<Integer> getKnightList(int n, int p) {
    FIFOQueue<Integer> q = new ArrayQueue<Integer>();   // or ListQueue
    ArrayList<Integer> list = new ArrayList<Integer>();
    for (int i = 1; i <= n; i++)
        q.enqueue(i);
    while (!q.isEmpty()) {
        for (int i = 1; i <= p; i++)
             q.enqueue(q.dequeue());
        list.add(q.dequeue());
    }
    return list;
}

2. 
public static void reverse(FIFOQueue<String> q) {
    LIFOStack<String> s = new ListStack<String>();  // or ArrayStack
    while (!q.isEmpty())
         s.push(q.dequeue());
    while (!s.isEmpty())
         q.enqueue(s.pop());
}

3. (a) 
public E dequeue() {
  if (front == -1)   // or rear == -1  or isEmpty()
    throw new NoSuchElementException();
  int max = front;
  int i = front;
  while (i != rear) {
      i = (i+1) % dataArray.length;
      if (dataArray[i].compareTo(dataArray[max]) > 0)
          max = i;
  }
  E element = dataArray[max];
  if (front == rear) {
     front = -1;
     rear = -1;
  }
  else {
     dataArray[max] = dataArray[rear];
     rear = rear - 1;    
     if (rear < 0) rear = dataArray.length-1;
  }

  numElements--;    
  return element;
}

(b) 
O(n) since you have to search for the max which is linear. If we shift
elements instead of just copying the last element into the max position,
there's another linear step, but this doesn't matter.

4.
(a) must use enhanced for loop here
public void printStrings(ArrayList<String> list) {
    for (String s: list)
        if (s.length() > 10)
             System.out.println(s);

}

(b) must use explicit iterator here
public void printStrings(ArrayList<String> list) {
    Iterator<String> iter = list.iterator();
    while (iter.hasNext()) {
        String s = iter.next();
        if (s.length() > 10)
             System.out.println(s);
}

(c) can't use enhanced for loop here since we're removing elements
public void removeStrings(ArrayList<String> list) {
    Iterator<String> iter = list.iterator();
    while (iter.hasNext()) {
        String s = iter.next();
        if (s.indexOf('!') != -1)
             iter.remove();
    }
}

5. 
public boolean equals(Object obj) {
    Worker other = (Worker)obj;
    return this.rate == other.rate;  // remember 'this' is optional
}

public String toString() {
    return name + " " + rate;
}

(b) 
public class HourlyWorker extends Worker [

    private int hoursWorked;

    public HourlyWorker(String workerName, double initRate, int hours) {
        super(workerName, initRate);
        if (hours < 0)
             hoursWorked = 0;
        else
             hoursWorked = hours;
    }

    public double getSalary() {
        double rate = super.getSalary()/40.0;
        if (hoursWorked <= 40)
            return rate * hoursWorked;
        else
            return rate * 40.0 + (hoursWorked-40)*rate*1.5;
    }

    public int getHoursWorked() {
        return hoursWorked;
    }

}

6. 
Explanation: This method calls itself.
Result: Stack overflow exception (or the system stack overflows or exceeds
its capacity).

7. The main idea here is that the instruction s.push calls a different
push method from the first half to the second half even though the
instruction looks the same. 

8. 
Similarities:
can't instantiate them ("new"), have signatures without method body
Differences:
Interfaces don't have fields, Abstract Classes (AC) can have fields.
Interfaces have no method bodies, AC can have method bodies.
Interfaces are implemented by classes, AC's are extended by classes.