Assignment Task
Problem-1: Number of paths in DAG
Give a linear-time algorithm that takes as input a directed acyclic graph G (V, E) and two vertices s and t, and returns the number of simple paths from s to t in G. For example, the directed acyclic graph of Figure 22.8 contains exactly four simple paths from vertex p to vertex v: pov, poryv, posryv, and psryv. (Your algorithm needs only to count the simple paths, not list them.)
Problem-2: Kruskal and Prim (Exam: Dec 2011, Dec 2012)
2a. In which situations, you prefer Prim’s algorithm over Kruskal’s, and vice versa?
2b. Let us assume that the graph represents the inter-city bus network in the Rogaland district: the vertices represent the cities and the weights of the edges represent the distant between cities. Assuming that vertex “f” represents Stavanger, explain how you can force Kruskal’s algorithm to make most connections through “f”.
2c. Using a Depth-First-Search or otherwise, propose an algorithm for listing all the cycles in a directed graph. Find the running time of the algorithm.
Problem-3: Dijkstra’s algorithm for single-source shortest paths
Find the shortest paths between the vertex A and the rest, using Dijkstra’s algorithm.
Problem-4: Maximum-Flow
- Given the flow network G above, find a flow of maximum value from source s to sink t, using the Ford-Fulkerson method.
- Suggest any improvement in this approach.
