[開課學院]: 資電學院
[開課系所]: 資訊系
[課程名稱]: 計算機演算法
[老師名稱]: 黃秀芬 老師
[開課學期]: 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