CS 570 HW 2 solutions Due Sunday February 16 by 23 30 1 Run Prim s algorithm from s until t is added to the tree Then run BFS to find a 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 Suppose the minimum edge weight in P is smaller than P we find the minimum edge e u v in P and get the tree T before e is added Since s and t are connected in P there exists an edge e0 in P where one node of e0 is in T and the other one is not Because P is not optimal we we0 Then e should not be added to the tree by our algorithm Thus our assumption is wrong P is the optimal solution Partial Credit Algorithm 4 points Runtime 2 points Proof 4 points 2 Proof by contradiction If T1 and T2 are distinct minimum spanning trees then consider the edge of minimum weight among all the edges that are contained in exactly one of T1 or T2 Without loss of generality this edge appears only in T1 and we can call it e1 Then T2 e1 must contain a cycle and one of the edges of this cycle call it e2 is not in T1 Since e2 is an edge different from e1 and is contained in exactly one of T1 or T2 it must be that w e1 w e2 Note that T T2 e1 e2 is a spanning tree The total weight of T is smaller than the total weight of T2 but this is a contradiction since we have supposed that T2 is a minimum spanning tree Partial Credit No 1 3 To do this we apply the Cycle Property nine times That is we perform BFS until we find a cycle in the graph G and then we delete the heaviest edge on this cycle We have now reduced the number of edges in G by one while keeping G connected and by the Cycle Property not changing the identity of the minimum spanning tree If we do this a total of nine times we will have a connected graph H with n 1 edges and the same minimum spanning tree as G But H is a tree and so in fact it is the minimum spanning tree The running time of each iteration is O m n for the BFS and subsequent check of 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 points 4 Let the sequence S consist of s1 sn and the sequence S 0 consist of s01 s0m We give a greedy algorithm that finds the first event in S that is the same as s0 1 matches these two events then finds the first event after this that is the same as s02 and so on We will use k1 k2 to denote the match we have found so far i to denote the current position in S and j the current position in S 0 Initially i j 1 While i n and j m If si is the same as s0j then let kj i let i i 1 and j j 1 otherwise let i i 1 EndWhile If j m 1 return the sub sequence found k1 km Else return that s0 is 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 also clear that the algorithm finds a correct match if it finds anything It is harder to show that if the algorithm fails to find a match then no match exists Assume that S 0 is the same as sub sequence sl1 slm of S We prove by induction that the algorithm will succeed in finding a match and will have kj lj for all j 1 m For each j 1 m the algorithm finds a match kj and has kj lj Proof The proof is by induction on j First consider j 1 The algorithm lets k1 be the first event that is the same as s01 so we must have that kj lj 2 Now consider a case when j 1 Assume that j 1 m and assume by the induction hypothesis that the algorithm found the match kj 1 that is the same as s0j if such a character exists We know that lj is such a character and lj lj 1 kj 1 So slj s0j and lj kj 1 The algorithm finds the first such index so we get that kj lj Partial Credit Finding the algorithm 4 points Proof 3 points Runtime 3 points 5 It is clear that when the travel time does not vary this problem is equivalent to the classical problem of finding the shortest path in the graph We will extend Dijkstra 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 the last site r u before u on the fastest path to u Initially S s and d s 0 While S 6 V Select 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 the optimal path from s to v In order to reach v P must leave S somewhere Let y be the first node on P that is not in S Then by our algorithm the travel time to y is at least as large as d v Since you cannot travel back in time this means the 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 optimal arrival time 6 Run modified BFS from s in order to find t The modification is that you keep track of the weight needed to reach each node and only enqueue adjacent nodes whose 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 a path Since all weights are non negative additional …