Example Answers of Data Structures and algorithms (Software School, Fundan University, winter, 2009-2010) Questions(100 points) 1. Amortized cost PUSH 2 POP O BUCKUPO 2. Topological sort Step 1: Call depth first search algorithm Step 2: Sort by finishing time Run time: O(n/gn) Yes, it can be used to solve the single-source shortest path problem for a DAG with negative edge path costs because DAG is a directed acyclic graph 3. Find the minimum spanning tree for every connected, undirected graph Count the number of edges that appear in the minimum spanning trees, denoted by x. The minimum number of edges that need to be removed from an undirected graph that the resulting graph is acyclic is E-x 4. Two key ingredients Optimal substructure: Dynamic programming builds an optimal solution to the problem from optimal solutions to subproblems. The solutions to the subproblems used within the optimal solution to the problem must themselves be optima using a"cut-and-paste"technique Subproblems should be independent Overlapping subproblems: Recursive algorithm revisits the same problem over and over again. In contrast, a problem for which a divide-and-conquer approach is suitable usually generates brand-new problems at each step of the recursion For greedy algorithm, we should prove that at any stage of the recursion, one of the optimal choices is the greedy choice. Thus, it is always safe to make the greedy choice Greedy-choice property: A globally optimal solution can be arrived at by making a locally optimal choice(a greedy choice at each step yields a globally optimal solution) 5. Write pseudocode for Prim's algorithm MST-PRIM(G, w, r) for each t∈v[G 2. do keyu 6. while O≠0
Example Answers of Data Structures and Algorithms (Software School, Fundan University, winter, 2009 - 2010) Questions (100 points) 1. Amortized cost PUSH 2 POP 0 BUCKUP 0 2. Topological sort Step 1: Call depth first search algorithm. Step 2: Sort by finishing time. Run time: O(nlgn) Yes, it can be used to solve the single-source shortest path problem for a DAG with negative edge path costs because DAG is a directed acyclic graph. 3. Find the minimum spanning tree for every connected, undirected graph Count the number of edges that appear in the minimum spanning trees, denoted by x. The minimum number of edges that need to be removed from an undirected graph that the resulting graph is acyclic is E – x. 4. Two key ingredients Optimal substructure: Dynamic programming builds an optimal solution to the problem from optimal solutions to subproblems. The solutions to the subproblems used within the optimal solution to the problem must themselves be optimal by using a "cut-and-paste" technique. Subproblems should be independent. Overlapping subproblems: Recursive algorithm revisits the same problem over and over again. In contrast, a problem for which a divide-and-conquer approach is suitable usually generates brand-new problems at each step of the recursion. For greedy algorithm, we should prove that at any stage of the recursion, one of the optimal choices is the greedy choice. Thus, it is always safe to make the greedy choice. Greedy-choice property: A globally optimal solution can be arrived at by making a locally optimal choice (a greedy choice at each step yields a globally optimal solution). 5. Write pseudocode for Prim's algorithm MST-PRIM(G, w, r) 1. for each u ∈ V [G] 2. do key[u] ← ∞ 3. π[u] ← NIL 4. key[r] ← Ø 5. Q ← V [G] 6. while Q ≠ 0
7.dol← EXTRACT-MIN(Q) 8 for each∈Ad/al 9 do ifv E O and w(u, v) rankly 2. then ply 3. else p{x]←y then rankb]← rankly]+1 6. Answer quest a. This algorithm will not work for cyclic graph b. The algorithm is equal to DFS .O(+E) 7. Find all-pairs shortest paths 03729 1122 030-45x=5134 471109 -5 5152 8. Fill the blanks (b)q←x{q (c)q←q+1
7. do u ← EXTRACT-MIN(Q) 8. for each v ∈ Adj[u] 9. do if v ∈ Q and w(u, v) rank[y] 2. then p[y] ← x 3. else p[x] ← y 4. if rank[x] = rank[y] 5. then rank[y] ← rank[y] + 1 6. Answer questions a. This algorithm will not work for cyclic graphs b. The algorithm is equal to DFS. c. O(V + E) 7. Find all-pairs shortest paths 0 3 7 29 1 0 8 16 0 3 0 45 4 7 11 0 9 5 2 2 30 D ⎡ ⎤ ⎢ ⎥ − = − ⎣ ⎦ −− − 1122 5 522 51 34 515 4 5152 π ⎡∅ ⎤ ⎢ ⎥ ∅ ⎢ ⎥ = ⎢ ∅ ⎥ ⎢ ⎥ ⎢ ∅ ⎥ ⎢ ∅⎥ ⎣ ⎦ 8. Fill the blanks (a) q > 0 (b) q ← π [q] (c) q ← q + 1 (d) q = m (e) q ← π [q]
9. Minimum cost flow Path:s→2→1→t,fow:5,cost:4, total:20. Path:s→l→t,flow:2,cost:5, total:10 Path:s→2→3→t,flow:3,cost:6, total:18 Total cost 48
9. Minimum cost flow Path: s → 2 → 1 → t, flow: 5, cost: 4, total: 20. Path: s → 1 → t, flow: 2, cost: 5, total: 10. Path: s → 2 → 3 → t, flow: 3, cost: 6, total: 18. Total cost: 48