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≠0Example 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