HW5 SAMPLE ANSWERS

1. add: O(1) since we know where the tail is and can add after that
   remove: O(n) since tail node does not have reference to previous
   node which becomes tail so we still need to traverse the list.

2. 
public E remove(int index) { 
	if (index < 0 || index >= numElements) 
		throw new IndexOutOfBoundsException(); 
	if (numElements == 1) { 
		head = null;
		tail = null;
	} 
	else if (index == 0) {
		head = head.next;
		head.prev = null;
	}
	else if (index == numElements-1) {
		tail = tail.prev;
		tail.next = null;
	}
	else {
		Node<E> nodeRef = head;
		for (int i = 1; i <= index; i++)
 			nodeRef = nodeRef.next;
		nodeRef.prev.next = nodeRef.next;
		nodeRef.next.prev = nodeRef.prev;
	}
	numElements--;
}

3.
(a)
public SinglyLinkedList() { 
	head = new Node<E>(null); 	// dummy node, no data
	numElements = 0; 
}

(b)
public void add(int index, E element) { 
	if (index < 0 || index > size()) 
		throw new IndexOutOfBoundsException(); 
	Node<E> newNode = new Node<E>(element); 
	Node<E> nodeRef = head; 
        for (int i = 1; i <= index; i++)  
		nodeRef = nodeRef.next; 
	newNode.next = nodeRef.next; 
	nodeRef.next = newNode; 
	numElements++; 
} 

public E remove(int index) { 
	if (index < 0 || index >= size()) 
		throw new IndexOutOfBoundsException(); 
	Node<E> nodeRef = head; 
	for (int i = 1; i <= index; i++) 
		nodeRef = nodeRef.next; 
	E result = nodeRef.next.data; 
	nodeRef.next = nodeRef.next.next; 
	numElements--; 
	return result; 
} 

4. 
public void printReverse() {
	Node<E> stopPtr = null;
	while (stopPtr != head) {
		Node<E> nodeRef = head;
	        while (nodeRef.next != stopPtr) {
			nodeRef = nodeRef.next;
		}
		System.out.println(nodeRef.data);
		stopPtr = nodeRef;
	}
}

The runtime complexity of this method is O(n^2) since it traverse n nodes,
then n-1 nodes, then n-2 nodes, etc. This method uses O(1) storage since
it only defines two additional references, no matter what the length of
the list is.

5.
   matrix: 200X200X4 bytes = 160000 bytes
   sparse matrix: 200X8 bytes for row headers + 200X8 for col headers
     + 28*n for nodes
   Solve for n: 28n + 3200 = 160000
   Then, if n is less than that value, sparse matrix uses less memory

6. (a) if data.size()==0 return null;
       else return data.remove(0);
   Runtime: O(n)  (elements have to be shifted)
   (b) data.add(0,element);
   Runtime: O(n)  (elements have to be shifted)


7. LIFOStack<PlayingCard> tempStack = new ListStack<PlayingCard>();
   (or ArrayStack), but students can't make a new LIFOStack)
   while (!s.isEmpty()) {
      PlayingCard p = s.pop();
      if (p.getRank()==1) temp.push(p);
   }
   while (!temp.isEmpty()) {
      s.push(temp.pop());
   }

8.
(a)  4 + 3 + ( 7 - 4 / 2 ) * 5 - ( ( 2 + 1 ) * 6 ) * 9 - 8

   Stack (bottom to top)   Postfix
                           4
   +                       4
   +                       4 3
   +                       4 3 +
   + (                     4 3 +
   + (                     4 3 + 7
   + ( -                   4 3 + 7
   + ( -                   4 3 + 7 4
   + ( - /                 4 3 + 7 4
   + ( - /                 4 3 + 7 4 2
   +                       4 3 + 7 4 2 / -
   + *                     4 3 + 7 4 2 / -
   + *                     4 3 + 7 4 2 / - 5
   -                       4 3 + 7 4 2 / - 5 * +
   - (                     4 3 + 7 4 2 / - 5 * +
   - ( (                   4 3 + 7 4 2 / - 5 * +
   - ( (                   4 3 + 7 4 2 / - 5 * + 2
   - ( ( +                 4 3 + 7 4 2 / - 5 * + 2
   - ( ( +                 4 3 + 7 4 2 / - 5 * + 2 1
   - (                     4 3 + 7 4 2 / - 5 * + 2 1 +
   - ( *                   4 3 + 7 4 2 / - 5 * + 2 1 +
   - ( *                   4 3 + 7 4 2 / - 5 * + 2 1 + 6
   -                       4 3 + 7 4 2 / - 5 * + 2 1 + 6 *
   - *                     4 3 + 7 4 2 / - 5 * + 2 1 + 6 *
   - *                     4 3 + 7 4 2 / - 5 * + 2 1 + 6 * 9
   -                       4 3 + 7 4 2 / - 5 * + 2 1 + 6 * 9 * -
   -                       4 3 + 7 4 2 / - 5 * + 2 1 + 6 * 9 * - 8
                           4 3 + 7 4 2 / - 5 * + 2 1 + 6 * 9 * - 8 -

(b)   8 6 3 4 + * 2 / 5 3 * - +

Stack (bottom to top):

8
8 6
8 6 3
8 6 3 4
8 6 7
8 42
8 42 2
8 21
8 21 5
8 21 5 3
8 21 15
8 6
14 <- final result

(c)  
- try to pop 2 values, but stack only has 1 value (or no value is ok too).
  Example: 4 + * 6 7 (many examples possible)
- after expression is parsed, there is still more than 1 value on stack
  Example: 2 3 4 +  (many examples possible)