5. (Adapted from K&T 6.3) Here is a suggested greedy algorithm to find the longest path in a DAG (directed acyclic graph): 1. Let u 2. Let 0 (the length of the longest path so far) 3. While there is an edge out of i. Choose an edge (u, )such that j is minimum (in the example below when e is considered it would be u, since 2 is the minimun out of u'2 and4, the outgoing neighbors of r). iii. LL+1 Return L (a) Show that the algorithm above indeed gives the longest path in the DAG below: t'4 (b) Slightly modify the graph in (a) such that this algorithm no longer gives the longest path (you may delete or add edges, as long as the graph is still a DAG and still connected). Explain briefly why the algorithm above doesn't work on your example (c) It is possible to find the longest path in a DAG using dynamic programming. This is done by calculating, for every vertex the longest path that ends in . Notice that any vertex n, extends the longest paths ending at each one of its incoming neighbors by 1 (this is true only in DAGs, of course, due to the fact that paths only go one way). Therefore, the length of the longest path ending at , is the length of the longest path of all of e,'s predecessors +1. The algorithm is given below i. Topologically sort the graph ii. For eaoh v whose in-degree is 0, set LP(v.)0 (this is the kngest pathending at ea). iii. For each of the other vertices , in the topologically sorted order: iv. Return maxe ,v(LP(e) For each vertex in the DAG shown in (a) above, fill the length of the longest path ending in it (d) What is the run time of the algorithm in (c) above as a function of Vi (the umber of vertioes) and/or El (the number of edges)? Explain briefly