**Unformatted text preview:**

CS 570 - HW 2 solutionsDue Sunday, February 16 (by 23:30)1Run Prim’s algorithm from s until t is added to the tree. Then run BFS to finda path from s to t and return it. Runtime is O((|E| + |V |) log |V |).Proof by contradiction:Denote our solution and optimal solution as P and P∗, respectively. Supposethe minimum edge weight in P is smaller than P∗, we find the minimum edgee = (u, v) in P and get the tree T before e is added. Since s and t are connectedin P∗, there exists an edge e0in P∗, where one node of e0is in T and the otherone is not. Because P is not optimal, we< we0. Then e should not be addedto the tree by our algorithm. Thus, our assumption is wrong, P is the optimalsolution.Partial Credit:• Algorithm - 4 points.• Runtime - 2 points.• Proof - 4 points.2Proof by contradiction:If T1and T2are distinct minimum spanning trees, then consider the edge ofminimum weight among all the edges that are contained in exactly one of T1orT2. Without loss of generality, this edge appears only in T1, and we can call ite1.Then T2∪ {e1} must contain a cycle, and one of the edges of this cycle, call ite2, is not in T1.Since e2is an edge different from e1and is contained in exactly one of T1or T2,it must be that w(e1) < w(e2). Note that T = T2∪ {e1} \ {e2} is a spanningtree. The total weight of T is smaller than the total weight of T2, but this is acontradiction, since we have supposed that T2is a minimum spanning tree.Partial Credit: No.13To do this, we apply the Cycle Property nine times. That is, we perform BFSuntil we find a cycle in the graph G, and then we delete the heaviest edgeon this cycle. We have now reduced the number of edges in G by one whilekeeping G connected and (by the Cycle Property) not changing the identity ofthe minimum spanning tree. If we do this a total of nine times, we will havea connected graph H with n − 1 edges and the same minimum spanning treeas G. But H is a tree, and so in fact it is the minimum spanning tree. Therunning time of each iteration is O(m + n) for the BFS and subsequent checkof the cycle to find the heaviest edge; here m ≤ n + 8, so this is O(n).Partial Credit:• Finding the algorithm - 7 points• Runtime - 3 points4Let the sequence S consist of s1, ..., snand the sequence S0consist of s01, ..., s0m.We give a greedy algorithm that finds the first event in S that is the same ass01, matches these two events, then finds the first event after this that is thesame as s02, and so on. We will use k1, k2, ... to denote the match we have foundso far, i to denote the current position in S, and j the current position in S0.Initially i=j=1While i ≤ n and j ≤ mIf siis the same as s0j, thenlet kj= ilet i = i + 1 and j = j + 1otherwise let i = i + 1EndWhileIf j = m + 1 return the sub-sequence found: k1, ..., kmElse return that “s0is not a sub-sequence of S”The running time is O(n): one iteration through the while loop takes O(1) time,and each iteration increments i, so there can be at most n iterations. It is alsoclear that the algorithm finds a correct match if it finds anything. It is harder toshow that if the algorithm fails to find a match, then no match exists. Assumethat S0is the same as sub-sequence sl1, ..., slmof S. We prove by inductionthat the algorithm will succeed in finding a match and will have kj≤ ljfor allj = 1, ..., m.For each j = 1, ..., m the algorithm finds a match kjand has kj≤ lj.Proof: The proof is by induction on j. First consider j = 1. The algorithmlets k1be the first event that is the same as s01, so we must have that kj≤ lj.2Now consider a case when j > 1. Assume that j − 1 < m and assume bythe induction hypothesis that the algorithm found the match kj−1that is thesame as s0j, if such a character exists. We know that ljis such a character andlj> lj−1≥ kj−1. So slj= s0j, and lj> kj−1. The algorithm finds the first suchindex, so we get that kj≤ lj.Partial Credit:• Finding the algorithm - 4 points• Proof - 3 points• Runtime - 3 points5It is clear that when the travel time does not vary, this problem is equivalent tothe classical problem of finding the shortest path in the graph. We will extendDijkstra’s algorithm to this problem:Let S be the set of explored nodes.For each u ∈ S, we store the earliest time d(u) when we can arrive at u and thelast site r(u) before u on the fastest path to u.Initially S = {s} and d(s) = 0.While S 6= VSelect a node v /∈ S with at least one edge from S for which d0(v) = min(u,v )fe(d(u))is as small as possible.Add v to S and define d(v) = d0(v) and r(v) = u.By using priority queue, the time complexity is O(E log(V )).Proof: We prove by induction on the size of S that for all v ∈ S, the value d(v)is the earliest time to reach v.|S| = 1 is trivial because travel starts from s. Suppose this claim holds for|S| = k, we now grow S to size k + 1 by adding the node v. Let P be theoptimal path from s to v. In order to reach v, P must leave S somewhere. Let ybe the first node on P that is not in S. Then by our algorithm, the travel timeto y is at least as large as d(v). Since you cannot travel back in time, this meansthe arrival time by P is not smaller than d(v). Then our solution is optimal.Partial Credit:• Algorithm - 7 points.• Runtime - 3 points.3• Proof is not required. The algorithm only needs to return the optimalarrival time.6Run modified BFS from s in order to find t. The modification is that you keeptrack of the weight needed to reach each node and only enqueue adjacent nodeswhose weight is less than or equal to the known short distance.Once you have found t, you’re done.Proof:We already know that there is at least one path from s to t, so BFS will find apath.Since all weights are non-negative, additional edges can only increase the overallweight of a path. For this reason, we don’t need to enqueue nodes with a weightgreater than the shortest distance, since they cannot be part of the shortestpath.Runtime: The added decision criterion whether to enqueue adjacent nodes adds1 per node expansion. Since BFS expands each node at most once, it adds 1per node, so overall we get O(2V+E) = O(n).Partial Credit:• Algorithm - 7 points.• Runtime - 3 points.7The optimal strategy is the obvious greedy one. Starting with a full tank ofgas, go to the farthest gas station you can get to within n miles. Fill up there.Then go to the farthest …

View Full Document