Question 1: Parallel Minimum Spanning Tree (30 points)

Suppose that we are given a graph G = (V, E), with V = {v1 , v2 , . . . , v n} where n = 2c  for some integer c > 0, and every edge e ∈ E has a distinct edge weight w(e) > 0.  For any X ⊆ V , let G(X) = (X, EX ) where EX  = {(u, v) | (u, v) ∈ E ∧ u, v ∈ X}.  Consider my proposed algorithm to compute the minimum spanning tree of G:

Divide-and-Conquer-MST (G)

if E = {e}, return {e};

X := {v1 , v2 , . . . , v|V |/2};

Find the minimum weight edge e between X and V − X;

T1  := MST (G(X));

T2  := MST (G(V − X));

return T1 ∪ T2 ∪ {e};

(a)  (10 points)  Suppose that in each recursive call, we find the minimum edge e by searching sequentially through the list of edges for each vertex in X; what is the work of my algorithm?

(b)  (10 points)  What is the span of my algorithm?

(c)  (10 points)  Does my algorithm always compute a minimum spanning tree?  Give a proof of correctness, or provide a counterexample.

Question 2: Dynamic Task Scheduling (30 points)

We considered a greedy algorithm for unit task scheduling in class. For that problem, we were given a set of jobs A = {a0 , a1 , . . . , an−1} with start and finish times. The goal was to find the largest set of nonoverlapping jobs, which we accomplished with a greedy algrithm.

Let’s consider a generalization of this problem that we call weighted task scheduling.  Here, each a i = (si, fi, wi) now has a weight wi. Our goal now will be to find X ⊂ A so that the jobs in X are nonoverlapping, as before, but also so that w(X) =：a i∈X wi  is maximized.  As before, we can assume that the jobs are indexed by finish time (i.e., fi  ≤ fi+1  for 0 ≤ i < n).

(a)  (10 points)  Our greedy algorithm for unit task scheduling will not work for this problem. Prove this by giving a counterexample.

(b)  (10 points)  A greedy approach doesn’t seem to suffice here, so let’s consider a dynamic programming approach. Devise an optimal substructure property for an optimal solution to this problem, and prove that it is correct.

(c)  (10 points)  How many distinct subproblems must ever be solved in your optimal substruc- ture property? If we devised an algorithm that computed these once and stored solutions for later use, how much work is required?

(d)  (5 points)  What is the work and span of the DAG?

Question 4: Bounded Shortest Paths (30 points)

In many real-world graphs, the shortest paths between vertices include no more than a few  edges. Suppose we know we’re only looking at graphs where the shortest path between any two  vertices has t or fewer edges. That is, any path with more than t edges is not a shortest path. We can assume the graph can contain negative edges, but will not contain negative cycles.

(a)  (10 points)  Describe an algorithm to solve the single-source shortest path problem for a graph in which the shortest path between any vertices has t or fewer edges.  Your algorithm should be efficient with cost bounds that depend on t (and other graph parameters).

(b)  (10 points)  Argue that your algorithm is correct.

(c)  (10 points)  Suppose G is a directed graph with n vertices and m edges.  What is the work and span of your algorithm? Justify your answer, in a few words.

Question 5: Adding it all up (25 points)

Suppose we are given a set of positive integers V = {v1 . . . v n}.  We want to know if there is some S 己 V such that：v∈S v = K, for some integer K.  E.g., for input V = {4, 3, 8, 5} and K = 15, the answer is True because 4 + 3 + 8 = 15.

(a)  (10 points)  To formulate a dynamic programming approach, first devise an optimal sub- structure property for an optimal solution to this problem, and prove that it is correct.

(b)  (10 points)  Draw a bottom-up dynamic programming table showing how to solve this problem for the example provided above.