课程名称︰算法
课程性质︰电机所选修
课程教师︰陈和麟
开课学院：电机资讯学院
开课系所︰电机所
考试日期（年月日）︰110.1.11
考试时限（分钟）：180
试题 :
Please answer the following questions on the answer sheets provided. Be sure
to write your name and student ID on all answer sheets you use. This is a clo-
sed book exam. No books, notes, or calculators may be used during the exam wi-
th the exception of one double-sided, hand-written A4 note. Read all questions
first. You may not request for clarification after 9:40 am.
You may assume that all pairwise comparisons additions and multiplications take
Θ(1) time. If you want to apply any result or theorem that has been taught in
class (including homeworks), you may do sobut you must state the result or the-
orem clearly before using it.
Problem 1. (15%) Given a connected undirected graph G. A bridge is an edge who-
se removal disconnects the graph.
1. (5%) Given a connected undirected graph G and an edge {u,v} in G, design an
O(V+E)-time algorithm to determine whether {u,v} is a bridge.
2. (10%) Given a connected undirected graph G, design an O(V(V+E))-time algori-
thm to find all bridges. (hint: spanning trees of the graph must have exactly
|V|-1 edges.)
In problem 2 and 3, there are n visitors v_1, v_2, ..., v_n from other countri-
es and m hotels h_1, h_2, ..., h_m that are eligible for quarantine visitors.
Each visitor has exactly 3 hotels that he/she is willing to stay in.
Problem 2. (10%) Given the capacity (maximum number of visitors allowed) of eve-
ry hotel. Design a polynomial-time algorithm that assigns visitors to hotels or
reports that no such assginment is possible. (Each visitor must be assigned to
one of the 3 hotels that he/she is willing to stay in.) Briefly justify the co-
rectness and analyze the running time.
Problem 3. (15%) Assume that hotels have no capacity limits. You must choose a
set of hotels such that every visitor has a hotel that he/she is willing to st-
ay in. The goal is to minimize the number of hotels chosen. Design a 3-approxi-
mation algorithm for this problem. Briefly justify the corectness and analyze
the running time.
Problem 4. (15%) Given an undirected graph G in which all edge costs are disti-
nct. Let C be any simple cycle in G. Probe the following statements or give co-
unterexamples.
1. (8%) The most expensive edge in C does not belong to the minumum spanning t-
ree.
2. (7%) The cheapest edge in C must belong to the minimum spanning tree.
For problem 5 and 6, you must either
1. design a polynomial-time algorithm, briefly justify the correctness.
or
2. prove that the problem in NP-comple. You must describe the reduction in det-
ail and briefly explain the correctness of your reduction. (Hint: One possible
reduction is similar to the reduction from HAM. PATH to HAM. CYCLE descrived in
class.)
You may use the fact that SAT, 3-SAT vertex Cover, Set Cover, Independent Set,
Hamiltonian Path, and Hamiltonian Cycle problems are all NP-complete. Also, you
do not need to prove that problems 5, 6 are in NP.
Problem 5. (15%) Given an undirected G. Each edge has a (possibly negative) ed-
ge cost. The problem is to determine whether the graph G has a simple cycle of
total cost 0.
Problem 6. (15%) Given a directed acyclie graph G. The problem is to determine
whether the grapg G has a Hamiltonian path.
Problem 7. (15%) Given a graph G=(V,E). Each edge e has a length a_e ≧ 0 and a
loading b_e ≧ 0. Given two nodes s and t in G. For any path P from s to t, de-
fine the length of the path to be the sum of lengths sum_{e in P} a_e and the
loading of the path to be the minimum loading min_{e in P} b_e. Design an O(E+
VlogV) algorithm to find a path from s to t, which minimizes (loading of the
path * length of the path). Briefly justify the corectness and analyze the run-
ning time. If you cannot manage this problem, find the path which minimize (lo-
ading of the path + length of the path) gives a good partial score (please ind-
icate clearly if you are only solve for this partial credit).