Problem 0: Review Homeworks #1 through #3, relevant exercises from the textbook, especially solved exercises.
Problem : Recall the squash scheduling problem from Homework #1. Characterize the skill orders for which there are stable schedules and prove that your characterization is correct.
Problem : Write a function that, given two sorted arrays of integers $L$ and $R$, both of size $n$, outputs a sorted array $A$ containing the elements of $L$ and $R$. Use a loop invariant to prove that your implementation is correct.
Problem :
Consider the problem of merging $n$ sorted arrays of lengths $s_1, \ldots, s_n$
into a single sorted array. This can be done by using a two-way merge
function repeatedly. For example, for three lists $A$, $B$, and $C$ of
sizes $10, 20, 30$, you can merge $A$ and $B$ then then merge the result with $C$,
you can merge $A$ and $C$ and then merge the result with $B$, or you can merge
$B$ and $C$ and then merge $A$ with the result. If the time to merge two lists
is equal to the total number of items in the list then those three sequences
of operations will take time $(10 + 20) + (30 + 30) = 90$, $(10 + 30) + (40 + 20) = 100$,
and $(20 + 30) + (50 + 10) = 110$ respectively. Find an efficient algorithm for
determining the order in which to merge the lists that minimizes the
total time taken by merge and prove that your algorithm outputs
an optimal solution.
Problem : A vertex-weighted undirected graph is an undirected graph in which each vertex is has a weight. The weight of a path in such a graph is the total weight of all the vertices along the path, including the endpoints. Describe an efficient algorithm for finding minimum-weight paths in a vertex-weighted graph in which all the vertices have non-negative weight and prove that your algorithm is correct. (Hint: if you transform the input into an input suitable for a standard algorithm, you need only show that your transformed problem is equivalent to the original.)
Problem :
Devise an efficient algorithm for updating a minimum spanning tree when a new
edge is added to the graph. The input should be the original graph $G$, the
graph induced by the minimum spanning tree $T$, and the new edge $(u, v)$, where
$u$ and $v$ are vertices in $G$ such that $(u, v)$ was not already an edge in $G$,
and the weight of $(u, v)$. The output should be the edge to remove from $T$ if
$(u, v)$ should be added, or NIL if the original minimum spanning tree
is still optimal.