Question 1
----------

We do O(n) insertion and deletion operations, each of which is
O(height of tree). If we use an ordinary binary search tree the
maximum possible height is O(n), while for an AVL tree it is O(log n).
So:

a) O(n^2)
b) O(n log n)

Question 2
----------

Adapting the example code, to store both keys and values in the nodes:

data BSTMap k v = Empty | Node k v (BSTMap k v) (BSTMap k v)

lookup :: Ord k => k -> BSTMap k v -> Maybe v
lookup x Empty = Nothing
lookup x (Node a b left right)
  | x < a = lookup x left
  | x > a = lookup x right
  | otherwise = Just b

update :: Ord k => k -> v -> BSTMap k v -> BSTMap k v
update x y Empty = Node x y Empty Empty
update x y (Node a b left right)
  | x < a = Node a b (update x y left) right
  | x > a = Node a b left (update x y right)
  | otherwise = Node x y left right

Question 3
----------

For G:

Represent the set as e.g. an AVL tree. Implement the operations as follows:
  new: create an empty AVL tree
  insert: use AVL insertion
  member: use binary search tree lookup
  delete: use AVL deletion
  deleteOdd:
    let arr be an empty dynamic array
    for each value in the tree,
      if the value is odd, add it to arr
    for each value in arr,
      delete the value from the tree

Less detail for deleteOdd is also acceptable - as long as the code
first finds all odd elements and then deletes them. A common idea
was to implement deleteOdd like this:
  for each value in the tree,
    if it's odd, delete it
I didn't accept this because it modifies the tree while traversing it,
which is difficult to do correctly because the deletion may rebalance
the tree and the traversal needs to continue afterwards from the
correct point in the rebalanced tree. (Having said that, Java's
Iterator provides a remove method for doing just this, which I didn't
realise at the time...)

For VG:

Represent the set as two AVL trees, one called odds that holds odd
numbers and one called evens that holds even numbers.
Implement the operations as follows:
  new: initialise odds and evens to empty trees
  insert: if the number is odd, insert it in odds, otherwise insert it in evens (using AVL insertion)
  member: if the number is odd, check if it's in odds, otherwise check if it's in evens (using BST lookup)
  delete: if the number is odd, delete it from odds, otherwise delete it from evens (using AVL deletion)
  deleteOdd: initialise odds to an empty tree

Question 4
----------

a)

A is wrong - 4 would have ended up at index 4 in the array.
B is wrong - 18 would have ended up at index 0.
C is OK.
D is OK.
E is wrong - 17 would have ended up at index 6.

b)

Replace 3 with a 'deleted' marker (lazy deletion):

Before:

+---+---+---+---+---+---+---+---+---+
| 9 | 18|   | 12| 3 | 14| 4 | 21|   |
+---+---+---+---+---+---+---+---+---+

After:

+---+---+---+---+---+---+---+---+---+
| 9 | 18|   | 12|XXX| 14| 4 | 21|   |
+---+---+---+---+---+---+---+---+---+

Question 5
----------

a)

One possible answer:

Node  Distance
----  --------
H     0
E     1
G     3
F     6
B     7
C     7
D     9
A     9

b)

e.g. starting at node D:

add edge AD
add edge BD
add edge AC
add edge CF
add edge FG
add edge EG
add edge EH

Starting from another node, you get the same edges in a different order.

Question 6
----------

The problem is that in deleteMin, you need to remove the minimum
element from both minheap and maxheap (likewise for deleteMax).
The following example goes wrong:

  insert(1); // minheap contains 1, maxheap contains 1
  deleteMax(); // minheap still contains 1, but maxheap is empty
  insert(2); // minheap contains 1 and 2, maxheap contains 2
  findMin(); // returns 1, which should not be in the priority queue!

For VG:

Drawing a few min-max heaps you will see that the least element must
be the root (like in a min heap), and the greatest element must be one
of the root's children. A slight complication is that if the heap only
contains one element, then the root is both the least and the greatest
element.

So finding the minimum element is as in a min heap: just return the root's value.

To find the maximum element, look at the root, the root's left child
and the root's right child, and return whichever of the three has the
greatest value.

(More information: http://en.wikipedia.org/wiki/Min-max_heap)