Homework SourseAlgorithms Bottom up longest paths Dynamic Programming Here
Algorithms: Bottom up longest paths - Dynamic Programming
Here you will solve the same problem in theta (V + E) using a bottom-up dynamic programming approach. Write the pseudocode for Longest-Path-Bottom-Up. Explain why it works; in particular, why topological sort is useful. Analyze its asymptotic run time.Solution
!a) PSEUDOCODE:-
procedure longestPathLength(T : Tree) = helper(T)[2]
(b)
We perform a depth-first search in post order and aggregate results on the way, that is we solve the problem recursively.
For every node vv with children u1,…,uku1,…,uk (in the search tree) there are two cases:
In the second case, we have to combine the one or two longest paths from vv into one of the subtrees; these are certainly those to the deepest leaves. The length of the path is then H(k)+H(k1)+2H(k)+H(k1)+2 if k>1k>1, or H(k)+1H(k)+1 if k=1k=1, with H={h(Tui)i=1,…,k}H={h(Tui)i=1,…,k} the multi set of subtree heights.
TOPOLOGICAL SORTING:
Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge uv, vertex u comes before v in the ordering. Topological Sorting for a graph is not possible if the graph is not a DAG.
We use topological sorting in longest path because , if we don\'t sort it, we don\'t know which adjacent vertex to choose first and it may lead to a situation where we use distance of a vertex v to update distances of its adjacent vertices adj[v], but after that, the distance of vertex v gets updated, so vertices from adj[v] could also get bigger distances, but we won\'t visit them anymore.
(C) Time Complexity: Time complexity of topological sorting is O(V+E). After finding topological order, the algorithm process all vertices and for every vertex, it runs a loop for all adjacent vertices. Total adjacent vertices in a graph is O(E). So the inner loop runs O(V+E) times.
Therefore, overall time complexity of this algorithm is O(V+E).
| We perform a depth-first search in post order and aggregate results on the way, that is we solve the problem recursively. For every node vv with children u1,…,uku1,…,uk (in the search tree) there are two cases:
In the second case, we have to combine the one or two longest paths from vv into one of the subtrees; these are certainly those to the deepest leaves. The length of the path is then H(k)+H(k1)+2H(k)+H(k1)+2 if k>1k>1, or H(k)+1H(k)+1 if k=1k=1, with H={h(Tui)i=1,…,k}H={h(Tui)i=1,…,k} the multi set of subtree heights. TOPOLOGICAL SORTING: Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge uv, vertex u comes before v in the ordering. Topological Sorting for a graph is not possible if the graph is not a DAG. We use topological sorting in longest path because , if we don\'t sort it, we don\'t know which adjacent vertex to choose first and it may lead to a situation where we use distance of a vertex v to update distances of its adjacent vertices adj[v], but after that, the distance of vertex v gets updated, so vertices from adj[v] could also get bigger distances, but we won\'t visit them anymore. (C) Time Complexity: Time complexity of topological sorting is O(V+E). After finding topological order, the algorithm process all vertices and for every vertex, it runs a loop for all adjacent vertices. Total adjacent vertices in a graph is O(E). So the inner loop runs O(V+E) times. Therefore, overall time complexity of this algorithm is O(V+E). |
