Fw: [試題] 104上 蕭旭君 演算法設計與分析 期末考
※ [本文轉錄自 NTU-Exam 看板 #1OUo7WsY ]
作者: rod24574575 (天然呆) 看板: NTU-Exam
標題: [試題] 104上 蕭旭君 演算法設計與分析 期末考
時間: Sun Jan 15 15:16:45 2017
課程名稱︰演算法設計與分析
課程性質︰必修
課程教師：蕭旭君
開課學院：電資學院
開課系所︰資工系
考試日期（年月日）︰2016.01.12
考試時限（分鐘）：180分鐘
試題 :
┌─────────────────────────────────────┐
│CSIE 2136: Algorithm Design and Analysis (Fall 2015) │
│ Final │
│Time: 14:20-17:20 (180 minutes) January 12, 2016 │
└─────────────────────────────────────┘
Instructions
˙ This is a 3-hour close-book exam.
˙ There are 6 questions worth of 100 points plus 35 bonus points. The
maximum of your score is 100, so you can allocate your time and select
problems based on certain optimal strategies of your own.
˙ Please write clearly and concisely; avoid giving irrelevant information.
˙ Please print your name, student ID, and page number on every answer page.
Problem 1: Short Answer Questions (25 points)
Answer the following questions and briefly justify your answer.
(a) (3 points) True or False: If P ≠ NP, then there is no polynomial-time
algorithm to solve any NP-complete problem.
(b) (3 points) True or False: If A can be reduced to B in O(n^2) time and there
is an O(n^3) algorithm for B, then there is an O(n^3) algorithm for A.
(c) (3 points) True or False: Every computational problem is decidable.
(d) (3 points) True or False: It is more efficient to represent a sparse graph
using an adjacency matrix than using adjacency lists.
(e) (3 points) True or False: If the amortized cost for every operation on a
data structure is O(1), the running time for performing a sequence of
n operations is O(n) in the worst case. (Assuming the data structure is
empty at the beginning.)
(f) (3 points) True or False: If there is a randomized algorithm that solves a
decision problem in time t and outputs the correct answer with probability
0.5, then there is a randomized algorithm for the problem that runs in
time Θ(t) and outputs the correct answer with probability at least 0.99.
(g) (3 points) Provide a counterexample to show that the following
divide-and-conquer algorithm may not correctly find a minimum
spanning tree:
˙ Divide: Given a graph G, partition G into two parts by using a cut.
˙ Conquer: Find a MST for each part.
˙ Combine: Combine the two MSTs using the minimum edge of the cut.
(h) (4 points) Please write down up to three of your peers who help you most
for the ADA class. Anything else you would like to say to your instructor
or any suggestions to help improve next year's class?
Problem 2: Basic Graph Problems (25 points)
(a) (5 points) Given a pre-order traversal list {A, B, D, E, F, C} and a
post-order traversal list {D, F, E, B, C, A}, please reconstruct a legal
binary tree. (There can be more than one solution.)
(b) (5 points) Given a BFS traversal list {A, B, C, E, D, F} and a DFS
traversal order {A, B, C, F, D, E}, please reconstruct a legal undirected
conntected graph. (There can be more than one solution.)
(c) (5 points) Consider the graph in Figure 1. What is the shortest path
distance from s to t computed by Dijkstra's algorithm (Figure 2)? What is
the actual shortest path distance from s to t?
-5
╭─────╮
│ ↓
╭─╮ -1 ╭─╮ 5 ╭─╮ 6 ╭─╮
│ｓ│←─→│ｂ│←─→│ｄ│←──│ｆ│
╰─╯ ╰─╯ ╰─╯ ╰─╯
│ ↑ ↖ ↗ │
10│ 3│ ╲ 6 3 ╱ │2
↓ ↓ ╲ ↙ ↓
╭─╮ ╭─╮ ╭─╮ ╭─╮
│ａ│──→│ｃ│←──│ｅ│←─→│ｔ│
╰─╯ 8 ╰─╯ 3 ╰─╯ 4 ╰─╯
│ ↑
╰───────────╯
1
Figure 1: Find the shortest path distance from s to t
(d) (10 points) Given the path relaxation property, please explain why
Bellman-Ford algorithm (Figure 3) can correctly compute the shortest path
distance from the source s to another vertex t when there is no negative
cycle.
Hint: Path relaxation property: If p = ＜v_0, v_1, …, v_k＞ is a
shortest path from s = v_0 to v_k, and we relax the edges of p
in the order (v_0, v_1), (v_1, v_2), …, (v_(k-1), v_k), then
(v_k).d = δ(s, v_k). This property holds regardless of any other
relaxation steps that occur, even if they are intermixed with
relaxations of the edges of p.
Problem 3: Approximation Algorithms (20 points)
In Homework 5, we learned how to reduce 3-CNF-SAT to k-CNF-SAT for any integer
k > 3 in polynomial time. Answer the following related questions:
(a) (10 points) The MAX-k-CNF-SAT problem is similar to the k-CNF-SAT
problem, except that it aims to return an assignment of the variables
that maximize the number of satisfied clauses (i.e., clauses that
evaluate to 1). Design a randomized ((2^k)/(2^k - 1))-approximation
algorithm for k-CNF-SAT (k > 3). The ((2^k)/(2^k - 1)) approximation
ratio means that Pr[a clause is satisfied] = ((2^k - 1)/(2^k)).
Your algorithm should run in polynomial time with respect to the number
of variables. To simplify this question, you can assume that no clause
contains both a variable and its negation.
(b) (10 points) Your friend Ada claimed that, for any k, Ada can design a
((2^k)/(2^k - 1))-approximation algorithm for the MAX-3-CNF-SAT problem.
Given a k and a formula in the 3-CNF form, her algorithm first converts
the formula into the k-CNF form, and then solves the MAX-k-CNF-SAT problem
(as described in part (a)). Do you agree with Ada? Justify your answer.
Problem 4: Independent Set (20 points)
An independent set of a graph G = (V;E) is a subset V' ⊆ V of vertices such
that each edge in E is incident on at most one vertex in V'. In other words,
no two vertices in V' are joined by an edge.
The independent set problem is to find a maximum-size independent set V' in G.
We denote by IND-SET the decision version of the independent set problem:
Given a graph G and a value k, determine whether there is an independent set
of size k in G.
Suppose we know 3-CNF-SAT is NP-Complete. To prove IND-SET is NP-Hard, your
friend Ada constructs a polynomial-time algorithm to reduce 3-CNF-SAT to
IND-SET as follows:
1. Let ψ = C_1 Λ C_2 Λ C_3 Λ … Λ C_k be a Boolean formula in 3-CNF
with k clauses, and each C_r has exactly 3 distinct literals (l^r)_1,
(l^r)_2, (l^r)_3,
2. For each C_r = ((l^r)_1 Ｖ (l^r)_2 Ｖ (l^r)_3) in ψ, introduce a triple
of vertices (v^r)_1, (v^r)_2, (v^r)_3) in V .
3. Build an edge between (v^r)_i and (v^s)_j for the following two cases:
(1) (v^r)_i and (v^s)_j are in the same triple (i.e., r = s);
(2) (v^r)_i and (v^s)_j are in different triples but (l^r)_i is the
negation of (l^l)_j.
(a) (10 points) Given an instance of the 3-CNF-SAT problem
ψ = (x1 Ｖ ﹁x2 Ｖ ﹁x3) Λ (﹁x1 Ｖ x2 Ｖ x3) Λ (x1 Ｖ x2 Ｖ x3),
please draw the instance of the IND-SET problem according to the proposed
reduction.
(b) (10 points) Please justify the correctness of this reduction. That is,
please show that ψ is satisfiable if and only if G has an independent
set of size k.
Hint: The proof is very similar to the proof of 3-CNF-SAT (≦_p) CLIQUE.
What is the relationship between clique and independent set?
Problem 5: Election Day (10 points + 15 bonus points)
The election day is coming. As a devoted citizen to the Great Pirate Kingdom,
Ada signs up to be a poll worker to help validate and count election votes.
Ada would like to apply techniques learned in the algorithm class to analyze
and improve the election process.
(a) (10 points) Ada is assigned to operate a Binary Counter that displays one
candidate's vote count in the binary form. If it costs 2^d to flip the
d-th bit, please justify that the amortized cost per increment is O(log n)
and the total amortized cost is O(n log n) for counting n votes.
Hint: Recall that we learned in the class that when it costs 1 to flip
a bit, the amortized cost per increment is O(1) and the total
amortized cost is O(n) in a sequence of n increments.
(b) (5 bonus points) Given the citizen ID list of the Great Pirate Kingdom,
Ada needs to ensure that only citizens on the list can vote. If the n IDs
are sorted, determining whether one ID is indeed on the list takes O(log n)
time. To speed up, Ada proposes to use a Bloom filter to store the IDs.
Please provide one advantage and one disadvantage of using Bloom filters
for this purpose.
(c) (5 bonus points) Ada claims to be able to accurately predict the election
result. However, making a prediction right before the election is
prohibited. To convince others, Ada computes and publishes H(winner, r)
where r is a random value and H(·) is a cryptographic hash function. Ada
will reveal winner and r after the election. Please explain why Ada cannot
cheat.
(d) (5 bonus points) The election decides the winner using the plurality
rule. That is, each voter awards one point to his/her top candidate, and
the candidate with the most points wins. Please construct an example
demonstrating that plurality is not strategyproof when there are more than
two candidates. Recall that a voting rule is strategyproof if a voter can
never benefit from lying about his or her preferences.
Problem 6: More Independent Set (20 bonus points)
Now let us consider a variant: The maximum weighted independent set problem
is to find an independent set V' in G such that the total weight of V' is
maximized. Although finding a weighted maximum independent set in general is
NP-hard, it can be done in polynomial time on certain special graphs. Consider
a weighted line graph G = {V, E} of n vertices V = {v_0, v_1, v_2, …, v_n}
and n - 1 edges E = {(v_0, v_1), (v_1, v_2), …, (v_(n-1), v_n)}. The weight
of v_i is w_i.
(a) (5 points) Provide a counterexample to show that the following greedy
algorithm may not find an independent set of maximum total weight.
─────────────────────────────────────
Algorithm 1 The heaviest-first greedy algorithm
─────────────────────────────────────
1: V' ← ψ, S ← V
2: while S ≠ ψ do
3: Pick a node v_i of maximum weight in S
4: Add v_i to V'
5: Remove v_i and its neighbors from S
6: end while
7: Return V'
─────────────────────────────────────
(b) (15 points) Please design a polynomial-time algorithm to find an
independent set of maximum total weight. You will get at most 10 points
if your algorithm runs in O(n^2) and at most 15 points if your algorithm
runs in O(n). Please briefly justify the correctness and the running time
of your algorithm.
Appendix
DIJKSTRA(G, w, s)
1 INITIALIZE-SINGLE-SOURCE(G, s)
2 S = ψ
3 Q = G.V
4 while Q ≠ ψ
5 u = EXTRACT-MIN(Q)
6 S = S ∪ {u}
7 for each vertex v ∈ G.Adj[u]
8 RELAX(u, v, w)
Figure 2: Dijkstra's algorithm
BELLMAN-FORD(G, w, s)
1 INITIALIZE-SINGLE-SOURCE(G, s)
2 for i = 1 to |G.V| - 1
3 for each edge (u, v) ∈ G.E
4 RELAX(u, v, w)
5 for each edge (u, v) ∈ G.E
6 if v.d > u.d + w(u, v)
7 return FALSE
8 return TRUE
Figure 3: The Bellman-Ford algorithm
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 59.115.46.186
※ 文章網址: https://www.ptt.cc/bbs/NTU-Exam/M.1484464608.A.DA2.html
※ 編輯: rod24574575 (59.115.46.186), 01/15/2017 15:19:46
→
01/15 15:20,
6年前
, 1F
01/15 15:20, 1F
※ 發信站: 批踢踢實業坊(ptt.cc)
※ 轉錄者: dyadi (118.169.35.48), 01/04/2018 22:20:31