Problem 1.

(a)  Suppose G = (V, E) is any undirected graph and (S, V _ S) is a cut with zero cut edges in G.  Prove that if we pick two arbitrary vertices u e S and v e V _ S, and add a new edge (u, v), in the resulting graph, there is no cycle that contains the edge (u, v).                                                        (12.5 points)

(b)  Suppose G = (V, E) is an undirected graph with weight we  on each edge e.  Suppose f is an edge in G with weight strictly smaller than all other edges. Prove that every minimum spanning tree (MST) must contain f .               (12.5 points)

Problem 2. You have m dollars and a group of n friend.  For each friend 1 < i < n, you know the price P [i] of the piece of candy that would make your friend happy. You want to find a way to distribute the m dollars such that as many of your friends as possible are happy. Design an O(n log n) time greedy algorithm to find how much money you will allocate each friend.                                                                   (25 points)

A complete solution consists of three parts: the algorithm or reduction (10 points), the proof of correctness (10 points), and the runtime analysis (5 points).

Example:   An example with m = 11 and n = 6 is as follows.

● Input: The array of candy prices for each friend is P = [6, 3, 5, 2, 8, 7].

●  Output: A list of pairs with first elements chosen from P to identify the friend and the second elements denoting the amount of money allocated to them:

[(5, 5), (3, 3), (2, 3), (6, 0), (8, 0), (7, 0)].

This means that the friends who want pieces of candy that cost 5 , 3, and 2 dollars, each received 5, 3, and 3 dollars respectively, while the remaining friends received zero dollars.

Problem 3. You are given a directed graph G = (V, E) and two vertices s and t.  Moreover, each edge of this graph is colored either blue or red.  Your goal is to find whether there is at least one path from s to t such that all red edges in this path appear after all blue edges (the path may not contain any blue edges or any red edges, but if it has both types of edges, all red edges should appear after all blue edges).

Design and analyze an algorithm for solving this problem in O(n + m) time.                              (25 points)

A complete solution consists of three parts: the algorithm or reduction (10 points), the proof of correctness (10 points), and the runtime analysis (5 points).

Problem 4.  Assume that G = (V, E) is an undirected, connected graph.  The weights we  on each edge e e E are distinct. A similar concept to a minimum spanning tree, a maximum spanning tree is a spanning tree that maximizes  the total weight of its edges.  Design an algorithm that in O(m log m) time, finds the

maximum spanning tree for a given graph, G.                                                                                 (25 points)

A complete solution consists of three part: the algorithm or reduction (10 points), the proof of correctness (10 points), and the runtime analysis (5 points).

Note:  As stated in the class, you are not allowed to assign negative weights to the edges of a graph.

Problem 5 (Extra Credit).  Consider the following different (and less efficient) algorithm for computing an MST of a given undirected and connected graph G = (V, E) with edge weight we  on each e e E:

1.  Sort the edges in decreasing (non-increasing) order of their weights.

2.  Let H = G be a copy of the graph G.

3.  For i = 1 to m (in the sorted ordering of edges):

(a) If removing ei  from H does not make H disconnected, remove ei  from H .

4.  Return H as a minimum spanning tree of G.

Prove the correctness of this algorithm, i.e., that it outputs an MST of any given graph G (we ignore the runtime of this algorithm in this problem).                                                                                   (+10 points)