1. E  (A and F are O(n^3), C and D are O(n), B and G are O(log n)

2. O(log n), O(n), O(1), O(1), O(1), O(n), O(1), O(1), O(1), O(1)
	(removeLast for singly linked is O(n))

3.        6
     38       34
   41  50   40  42
 47
 
         34
    38        40
  47  50    42 

4. O(n), O(2^n), O(n^2), O(n), O(log n)   
[b and d are harder than I'd ask on the exam]

5. 
a) if there aren't different priorities, a queue would be O(1) first-come, 
first-serve.  if different priorities, then a priority queue implemented 
by a binary heap would be O(log n) for retrieving the next task and would 
allow different priorities and even priorities to be changed (if the 
processes know their locations inside the pq)

b) HashSet<URL>.  O(1) add, contains is the fastest performance possible
 
c) the classic algorithm uses a stack

d) HashSet<String>.  O(1) contains.  if a word is not in hashset, then it 
is misspelled.

e) TreeSet<String> (or TreeMap<String,DictionaryEntry>).  we want sorted 
order so users can browse.  O(log n) to find an entry.

6. 
a. String has a .equals that sees if two objects have equivalent content.
The hashcode for Object does not assess content, so two equivalent Strings
may produce different hashcodes.  This could cause all sorts of crazy 
stuff to happen.

b. Only looks at 16 characters at the most inside a string.  Adversarial
strings, such as long URLs, may differ at characters other than the ones
being checked, causing collisions and slow performances.  (btw - this is 
similar to how Java originally implemented String.hashCode 

c. Looks at every character, but abc and cba will be the same, as will
ac and bb.  A polynomial using the characters would be better.  Results
in lots of collisions.

7. a.  If you didn't keep a marker and left a hole there, you would never 
find items lying past there that had been placed there as a result of 
several successive collisions.

b. repeatedly creating new objects as part of the chained linked lists

c. all rows are full, possibly except for bottom row, which has all its 
entries as far left as possible.  using this, L-child = 2*me, 
R-child = 2*me+1 lets us encode the tree as contiguous entries in an array

d. equals: return false.  compareTo: throw an exception

8. 
  if (head==null) return null;
  Node current1 = head;
  Node current2 = head;
  while(current2!=null) {
    current1 = current1.next;
    current2 = current2.next;
    if (current2 != null) current2 = current2.next; 
    // if we don't check current2 here, we get null pt ex for odd lengths
  }
  return current1;

9.

while(ia<a.length && ib<b.length) {
  if (a[ia]<b[ib]) ia++;
  else if (a[ia]>b[ib]) ib++;
  else {
    result[k++]=b[ib++]; ia++;
  }
}