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 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= 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.