Hints/solutions for old 3101 exam:

1.  Easy to prove it is O(log n).

2. 
   1------3   
    \
     \   
6-----2-------4
             /
            /
           /
          5-------7
          
3a.  The interesting part of the proof is proving that the last part of the invariant
is preserved when $i$ increases.  To do this, use the fact that T[i,j-1]<k and T[i,j]>k 
and row i is sorted.

3b.  If T[i,1]=k, then clearly the output is correct.  If T[i,1] is not k, we have to show
that k does not appear anywhere in T.  It doesn't appear above row i (by invariant).  
By the invariant, T[i,1] > k.  Use the fact that T is a Young tableau to show k does not appear
in row i or any row below it.

3c.  Theta(m + n)

4a.  Theta(m + n^2)

4b.  When m is Theta(n^2) (i.e., very dense), this implementation gives a total running
time of Theta(n^2), while a heap implementation has total running time Theta(n^2 log n).

5a.  Mergesort or heapsort (or quicksort with a well-chosen pivot) will make this run in
Theta(n log n) time.

5b.  Theta(n + k log n)

5c.  Select the kth smallest element in O(n) time, pull out all the elements that are
less than or equal to it into an array of size k and then sort that smaller array
using mergesort.

5d.  If we use counting sort, we can solve the problem in O(n) time.

6a.  You can use the following recurrence equations to build the algorithm.
P[i,j] = 0 if j<i
P[i,i] = infinity
P[i,j] = max( b(v_i, v_j), max { min ( P[i,k], P[k,j] ) : i < k < j } )

6b.  Theta(n^3)

7a.  Sort so that p_1 >= p_2 >= p_3 >= ... >= p_n.  Schedule each job in the latest 
available timeslot before its deadline.

7b.  A schedule can be defined as a function
Q : {1..n} -> {0,1,2,3} x {1..n}
where Q(i) = (j,k) means that worker j does job i in time slot k.  (If j=0, it means no worker
is assigned to do job i.)
Then, an optimal solution Q* extends partial solution Q_i if for all x<=i, Q_i(x) = Q*(x).

7c.  Suppose Q*(i) = (j,k) while Q_i(i) = (j',k) and j != j'.
Create Q^ from Q* by swapping the jobs done by workers j and j' in time slot k.
Argue that it is Q^ is still a legal, optimal solution and that it extends Q_i.

8a.  DFS

8b.  Hint:  Before leaving an intersection, use a pebble in the middle of the intersection to 
indicate which direction you last left the intersection.  When you arrive at an intersection, 
determine (using the pebble you find there, if any) what to do next.