課程名稱︰演算法 課程性質︰選修 課程教師︰李建模 開課學院：電資學院 開課系所︰電機系 考試日期（年月日）︰2010/06/20 考試時限（分鐘）：150 min 是否需發放獎勵金：是 （如未明確表示，則不予發放） 試題 : Problem 1( 15 points, 5 point each )<Amortized Analysis> Use the potential method to show the amortized running time of a sequence of insertions and deletions on a red-black tree T of n nodes. A. Prove that Φ(T) is valid potential function, where k is positive constant Φ(T)=0 ,when n=0 n Φ(T)=k Σ lg i ,when n>0 i=0 B. Show the amortized cost of each insertion is O(lg n) C. Show the amortized cost of each deletion is O(1) Problem 2( 15 points, + 5 points bonus)<Maze Generator> Our class wants to start an online game website, call MazeBook, which generate a random maze each time a player login. An n x n maze can be viewed as a n x n array of cells, where the entrance is cell 0, upper left corner, and the exit is cell ( n x n ) - 1, lower right corner. We start with an n x n array with walls around each cell, except the entrance and exit. We them randomly knock down walls between two neighbor cells until there is a unique path from the entrance to every cell in the maze. That means, (1) no cell is isolated, and (2) exactly one path from entrance to each cell. The left figure is the initial 4 x 4 maze and the right figure is the finished maze. ┌─┬─┬─┬─┐ ┌───┬───┐ 0 │1 │2 │3 │ 0 1 │2 3 │ ┌─┼─┼─┼─┤ ┌─┐ └─ │ │4 │5 │6 │7 │ │4 │5 6 7 │ ├─┼─┼─┼─┤ │ └─ │ │8 │9 │10│11│ │8 9 10│11│ ├─┼─┼─┼─┘ │ ─┐ └─┘ │12│13│14│15 │12 13│14 15 └─┴─┴─┴─┘ └───┴───┘ A. As the chief p programmer of MazeBook, you are asked to fill-in the following algorithm to generate a random maze. You can call the disjoint set functions decined in the textbook. ( 10 points ) ┌─────────────────────────────────┐ │GENERATE-MAZE(n) │ │ generate n x n array of cells; │ │ knock down left wall of cell 0; // entrance │ │ knock down right wall of cell n^2 -1; // exit │ │ foreach cell i │ │ __________________; // initialize each cell │ │ while ( number of set is greater than 1 ) │ │ randomly pick two neighbor cells x,y; │ │ if ( ______________________ ) │ │ knock down wall between cell x and y; │ │ _________________________; │ │ return n x n maze; │ └─────────────────────────────────┘ B. Use the algorithm in A. Suppose that we randomly choose (x,y) pairs in the following order, show the finished 4x4 maze. ( 5 points ) (9,10) (5,6) (13,14) (4,5) (10,11) (14,15) (15,11) (0,4) (6,2) (3,7) (13,12) (4,8) (9,13) (2,3) (2,1) (8,9) C. Prove that there is one and only one path from the entrance to each cell. (bonus) Problem 3 ( 10 points ) <NP Complete> Professor McCluskey wants you to find a polynomial-time algorithm to solve the two-level logic minimization problem. Please prove to him that the set-covering problem is NP complete so there is no known polynomial-time algorithm available (yet). Hint: we already know that vertex covering is NP-complete. Problem 4 ( 15 points )<All pairs shortest paths> Our MazeBook company is very successful and we have five branch offices all over the world. The traveling costs between five branches are given in the flowing graph. As the CEO of this company, you need to travel between branch offices very often. To save your traveling cost, please find the shortest paths between all pairs of branch offices. 3 (1)────→(2) ↑↖7 ╱│ ╲3 │ ╲ ╱ │ ↘ 5│ ╳ │2 (5) │ ╱ ╲ │ ↗ │↙4 ╲↓ ╱-2 (4)←────(3) 1 A. Use the FASTER-ALL-PATHS-SHORTEST-PATHS algorithm in the textbook. Show all your intermediate results: L(1) L2)... ( 5 points ) B. Use the Floyd-Warshall algorithm. Show all your intermediate results: D(0) Π(0) D(1) Π(1)... ( 10 points ) Problem 5 ( 15 points, 5 points each) <Maximum Flow> Given the following flow network G. 5 (1)────→(2) ↑↖1 ↗│ ╲9 │ ╲ ╱ │ ↘ 2│ ╳ │2 (t) │ ╱ ╲ │ ↗ │╱3 ╲↓ ╱1 (s)←────(3) 5 A. What is the mincut c(S,T) of this flow network? B. For your answer in A, what is the maximum flow? C. Use the Edmonds-Karp method to find the maximum flow from s to t. Show all of your flow network G in each iteration. When two paths are of the same length, always choose the smaller vertex number first. Problem 6 ( 15 points )<Minimum Spanning Tree> Given the following graph where each edge is associated with a weight. 2 2 (b)───(e)───(h) 13 ╱ ╲3 ╲ ╲4 ╱ 7 ╲ 5 ╲15 ╲ (a)───(d)───(g) (j) ╲ ╱ ╲ ╲ ╱ 11 ╲ ╱7 ╲2 2 ╲ ╱9 (c)───(f) (i) 1 A. Find the minimum-weight spanning tree by Kruskal's algorithm. Show your answer step by step. ( 7 points ) B. Find the minimum-weight spanning tree by Prim's algorithm starting from vertex a. Show your answer step by step. ( 8 points ) Notes: 1. Please write down the edge added into the MST in each step. e.g. (a,c)→ (c,d)→(g,i). No need to draw al graphs. 2. If two edges tie, choose the edge that comes first in dictionary order. e.g. choose (b,e) before (d,f) Problem 7 ( 10 points )<greedy algorithm on MST> Suppose you gave an undirected graph with weighted edges. You perform a depth-first search, such that the edge going out of each vertex are always explored in increasing order of their weights, smallest first. Is the resulting depth first search tree guaranteed to be a minimum spanning tree? If so, please explain why. If it isn't, please provide a counterexample, showing the greedy DFS tree ( with starting vertex ) and the MST. Problem 7 ( 5 points ) Please give two things that should be improved for the class. What is the most valuable thing that you have learned from the class? What is your favorite topic? What is the worst topic? end --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.250.13 ※ 編輯: ji394vul3m6 來自: 140.112.250.13 (06/20 19:50)