[開課學院]: 資電學院 [開課系所]: 資訊系 [課程名稱]: 計算機演算法 [老師名稱]: 黃秀芬 老師 [開課學期]: 97-2 [類型]: 97-2期末考 1. (40%) True or False (1) The Huffman algorithm for constructing an optimal prefix code is a greedy algorithm. (2) In a depth-first search of an undirected graph G , every edge of G is either a tree edge or a back edge. (3) Kruskal's algorithm for finding a minimum spanning tree of a weighted , undirected graph is an example of a dynamic programming algorithm. (4) One can give an O(V + E) time algorithm for the single-source shortest paths problem when the weights of all edges are equal. (5) The Bellman-Ford algorithm (for single source shortest paths) cannot work when there exist negative edges in the graph. (6) The running time of Bellman-Ford algorithm is O(|VE|). (7) The halting problem ε NP-complete. (8) The fractional knapsack problem ε NP. (9) If L ε NP-hard and L'α(reduces to) L then L' ε NP-hard. (10) 2SAT ε P and 3SAT ε NP. 2. (10%) Describe how to perform a topological sort in linear time. 3. (10%) Construct an optimal binary search tree for the following keys A(weight=5), B(weight=4) and C(weight=2). 4. (10%) Give an O(n^2)-time algorithm to find the longest montonically increasing subsequence of a sequence of a n numbers. 5. (10%) (1) Give an algorithm to solve the minimum-spanning-tree problem. (2) What is the running time of your algorithm ? 6. (10%) We are given a directed graph G=(V,E) on which each edge (u,v) ε E has an associated value r(u,v) , which is a real number in the range 0 ≦ r(u,v) ≦ 1 that represents the reliability of a communication channel from vertex u to vertex v. We interpret r(u,v) as the probability that the efficient algorithm to find the most reliable path between two given veritices. 7. (10%) State Cook theorem. 註: ε是屬於 --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 118.170.88.122