课程名称︰算法设计与分析
课程性质︰资工系 大二 必修
课程教师︰蔡欣穆
开课学院：电机资讯学院
开课系所︰资讯工程学系
考试日期（年月日）︰2015/01/15
考试时限（分钟）：180分钟
试题 :
132 points in total
Problem 1. In each of tje following question, please specify if the statement
is true or false. If the statement is true, explain why it is true. If it is
false, explain what the correct answer is and why. (40 points. For each
question,1 point for the true/false answer and 3 points foe the explaination.)
1. If L ∈ NPC and L ∈ P, then P = NP
_
2. If L ∈ NP then L ∈ NP.
_
3. If L ∈ P then L ∈ P.
4. If P = NP then NP = co-NP.
5. NPC ⊆ NP.
6. NP ⊇ P.
For the following 4 questions, please refer to DFS(G) and DFS-VISIT(G,v)
after the problem description.
7. There is no back edge in terms of the depth-first forest produced
by a DFS on an undirected graph.
8. There is no cross edge in terms of the depth-first forest produced
by a DFS on an undirected graph.
9. There is no back edge in terms of the depth-first forest produced
by a DFS on a directed acyclic graph.
10. In DFS, when we visited an edge e = (u,v), if v's color is BLACK
and u.d < v.d, then e is a cross edge.
DFS(G)
1 for each vertex u ∈ G.V
2 u.color = WHITE
3 u.pi = NIL
4 time = 0
5 for each vertex u ∈ G.V
6 if u.color == WHITE
7 DFS-VISIT(G,u)
DFS-VISIT(G,u)
1 time = time + 1
2 u.d = time
3 u.color = GRAY
4 for each v ∈ G.Adj[u]
5 if v.color == WHITE
6 v.pi = u
7 DFS-VISIT(G,v)
8 u.color = BLACK
9 time = time + 1
10 u.f = time
Problem 2. Briefly explain in evidence-based scheduling how you can "simulate
the future" ─ use the past history to estimate the time require to complete
a task. (6 points)
Problem 3. Please answer the following questions related to minimum cost
spanning tree (MST) of connected graph G = (V,E). (24 points)
1. Please write down the pseudo code of Kruskal's algorithm. (4 points)
2. Please show that your algorithm in the previous problem runs in
O(|E|log|E|). You can assume that running m of the following operations:
MAKE-SET(v), FIND-SET(v), and UNION(u,v), takes O(mα(n))-time, where n
is the number of MAKE-SET(v) operations, and α(n) is a very slowly
growing function that α(n) ≦ 4 in all practical situations. (4 points)
3. Suppose that all edge weights in a graph are integers in the range from
1 to |V|. Please give a modified Kruskal's algorithm and show that is
runs in O(|E|α|V|). (4 points)
4. Please write down the pseudo code of Prim's algorithm. (4 points)
5. Please show that your algorithm in the previous problem runs in
O(|E|log|V|). (4 points)
6. Suppose that all edge weights in a graph are integers in the range from
1 to some constant W. Please give a modified Prim's algorithm and show
that it runs in O(|E|). (4 points)
Problem 4. We would like to implement a dynamic table data structure that
supports two operations, TABLE-INSERT and TABLE-DELETE. TABLE-INSERT looks at
the table to check if it is full. If not, then the item is directly inserted
to the table. Otherwise, it doubles the size of the table, moves all data from
the old table to the new table.
TABLE-DELETE will remove the item from the table. If after the removal the
table is less than 25% full, then it halve the table size and move all data
from the old table to the new table.
Assume that allocating the table space takes negligible time. Inserting,
removing, or moving an item takes one unit if time. Show that the amortized
cost of the two operations are both bounded above by a constant using the
potential method. The potential function is given by
2 x T.num - T.size if T.num/T.size ≧ 1/2
Φ(T) = {
T.size / 2 - T.num if T.num/T.size ＜ 1/2
where T.num is the number of items in the table and T.size is the size of the
table. Note that you need to discuss different cases, including the ones that
do not involve table expansion or contraction and the ones that do.(16 points)
Problem 5. In this problem, we ask you to answer the following questions
related to an directed graph G shown in Figure 2. (16 points)
Figure 2. http://imgur.com/i47tCKL
1. Please use the Dijkstra Algorithm to determine the costs of the shortest
path (the number next to the edges in the graph are the costs for
travelling through them) from vertex 1 to all other vertices. Use Table 1
to show how the algorithm is executed in each iteration. (6 points)
2. Please use the Bellman-Ford Algorithm to determine the costs of the
shortest path (the number next to the edges in the graph are the costs
for travelling through them) from vertex 1 to all other vertices. Use
Table 2 to show how the algorithm is executed in each iteration.
(6 points)
3. Explain why Dijkstra Algorithm cannot handle edges with negative weights.
(4 points)
Problem 6. In this problem,we ask you to prove that NODE-COVER is NP-complete.
The problem description is as follows.
Given a graph G = (V,E), we say N ⊆ V, a vertex set, is a node cover for G
if every edge in E has at least one end in N. The problem NODE-COVER is: given
a graph G and a "budget" k, does G have a node cover of k or fewer nodes?
(20 points)
1. Please show that NODE-COVER ∈ NP. (4 points)
2. To show that NODE-COVER is NP-hard, we will construct a reduction
function f(x) that reduces an instance of 3-CNF-SAT to an instance of
NODE-COVER, described as follows.
(a) Create G with the following description. For each clause (xＶyＶz)
in the 3-CNF fornula, construct a "column" of three nodes, all
connected by vertical edges. Add a horizontal edge between nodes
that represent any variable and its negation.
(b) Let the budget k be twice the number of clauses.
Example: (xＶyＶz)Λ(~xＶ~yＶ~z)Λ(xＶ~yＶz)Λ(~xＶyＶ~z) is reduced to
G shown in Figure 1 with k = 8.
Figure 1. http://imgur.com/dXvJvUF
Please show that this reduction is correct, i.e., x ∈ 3-CNF-SAT if and
and only if f(x) ∈ NODE-COVER. (12 points) Please also briefly explain
why the reduction algorithm that calculates f(x) runs in polynomail time.
(4 points)
Problem 7. Out of all the lectures this semester, which one do you enjoy the
most and which one do you want to skip the most? Why? And please also give
constructive suggestion to the style and the content of the homework
assignments. Thanks! (10 points)