CIT 5960 Online

Midterm 2 Solutions

1. (a) False. Consider a graph where the vertex n has a single edge incident on it that has weight m. The remaining (n − 1) vertices form a connected graph with(m − 1) edges that have

   distinct weights 1, 2, …, (m − 1). Since (m − 1) ≥ (n − 2), this is always possible. Now, any MST must contain the unique edge incident on vertex n.

   1. True. In the greedy merging sequence, since we always choose to merge two symbols of smallest probability, symbol 1 will be merged for the first time only when there are 2 symbols remaining. The process terminates at this point, and hence symbol 1 is assigned a code of length 1.

2. (a) Algorithm Use BFS/DFS to find the number of connected components in G. If this number is K or larger, we can assign a distinct color to the vertices in each connected component. On the other hand, if this number is less than K, we output that there is no consistent coloring that uses K or more colors.

   Justification. We observe that all vertices in any connected component of G must get the same color in any consistent coloring since any 2 vertices x, y in the same connected component are connected by a path (a sequence of edges). So any consistent coloring of G can not use more colors than the number of connected components in G.

   Runtime. As BFS/DFS runs in O(n + m) time, we get the desired time complexity.

   1. Algorithm Compute the strongly connected components of the graph G. If G is strongly con- nected, then we output “NO” and exit. Otherwise, let GSCC = (VSCC, ESCC) be the acyclic component graph. Perform a topological sort of GSCC, and let c1, . . . , ck be the sequence of topologically sorted vertices, where k = |VSCC|. Let Ci be the strongly connected component in G corresponding to vertex ci in GSCC. Add an edge e from any vertex in Ck to any vertex in C1. Test if the resulting graph G′(V, E ∪ {e}) is strongly connected. If so, output e as the desired edge, else output “NO”.

      Justification. If the addition of some edge e = (u, v) makes G strongly connected, we claim that it must be that u ∈ Ck and v ∈ C1. This follows from the fact that there are no edges going out of component Ck and no edges entering the component C1, and if G′ = G + e is strongly

      connected, then G′ must have at least one edge leaving and entering each Ci. Moreover, if some edge e from Ck to C1 makes G strongly-connected, then any edge e from Ck to C1 must make G strongly-connected. This follows from the fact that C1 and Ck are strongly connected components. Thus, G is almost strongly connected if and only if the candidate edge we add makes G′ strongly connected.

      Runtime. Computing the strongly connected component graph and topologically sorting it take O(|V | + |E|) time each. Adding the edge e takes constant time, and testing if G′ is strongly connected also takes O(|V | + |E|), so the entire algorithm takes O(|V | + |E|) time.

   2. Algorithm: Let the edge e = (u, v). Let G′ be the graph obtained by deleting edge e from the graph. Run Dijkstra’s algorithm on G′ to find the shortest path from v to u. If Dijkstra’s algorithm outputs “no feasible path”, then output “none”. Else, if T is the cost of the shortest path, then output T + cost(e) where cost(e) is the weight of the edge e.

      Justification: Consider any cycle in G in which (u, v) is an edge. Tracing the edges of the cycle starting from v, we see that such a cycle yields a simple path from v to u (which of course does not include the edge (u, v)). In the other direction, given any simple path from v to u, we can add the edge (u, v) to get a cycle. Thus, the cycles containing (u, v) are in one-to-one correspondence with simple paths from v to u. Further, the total weight of the cycle is exactly the same as the weight of the corresponding path + the weight of the edge (u, v). This finishes the proof.

      Running Time: Given the adjacency list representation of G, the adjacency list representation of G′ can be computed in time O(m + n). Subsequently, the cost of running Dijkstra is O(m log n) which gives us total bound on the running time.

      i=1

3. Algorithm: Let H = Σn hi denote the total happiness associated with all n toys; note that H

(

is an integer between 0 and nM . We now define our subproblems. For each integer 0 ≤ i ≤ n and 0 ≤ j ≤ nM , let T [i, j] be 1 if there is a subset of the first i items whose total happiness is exactly j, and 0 otherwise. The base case of this computation is as below:

T [0, j] = 1 if j = 0

1. otherwise.

   Now for the inductive computation, we define as follows:

   T [i, j] =

2. if j ≥ hi and T [i − 1, j − hi] = 1



1 if T [i − 1, j] = 1

0 otherwise.

We will compute the entries in the table T , in increasing order of i, and for each i, we compute it in increasing order of j. It is easy to verify that when we compute T [i, j] in this manner, all subproblems on which it depends, have already been computed.

Finally, we output that an envy-free partition of toys exists if T [n, H/2] = 1, else not.

Proof of correctness: We will prove correctness by induction on i. The base case corresponds to i = 0, and T [0, j] corresponds to achieving a happiness value of j from allocating an empty set. The only achievable happiness value from an empty set is 0.

Now, assume by induction hypothesis that T [i′, j] is computed correctly for all i′ < i, and for all 0 ≤ j ≤ nM . Then, note that T [i, j] should be 1 iff there is a subset of the first i items whose happiness is exactly j. Now if such a subset exists, it either does not include toy i or it does. If such a subset does not include toy i, then it must be that T [i − 1, j] = 1. On the other hand, if such a subset includes toy i, it must be that j ≥ hi, and that there is a subset of the first (i − 1) items that gives the remaining happiness of j − hi. Thus in this case we must have T [i − 1, j − hi] = 1. If neither of the two cases occur, then we know that no subset of first i items gives happiness of j, and we can correctly set

T [i, j] = 0.

Finally, note that there is an envy-free partition iff either there is a subset of the n toys whose happiness is exactly H/2.

Time complexity: The table T has O(n2M ) entries. Note that computing T [0, j] for all 0 ≤ j ≤ nM can be done in O(nM ) time. Further, given T [i′, j] for all 0 ≤ j ≤ n · M and i′ < i, the entry T [i, j] can be computed in O(1) time. Thus, the total cost of computing the entire table T is O(n2 · M ). Finally, the last step of checking if T [n, H/2] = 1 takes only O(1) time. So, the total time complexity

is O(n2M ).