課程名稱︰演算法設計與分析
課程性質︰必修
課程教師：蕭旭君
開課學院：電資學院
開課系所︰資工系
考試日期（年月日）︰2016.11.10
考試時限（分鐘）：
試題 :
Midterm Solutions
Contact TAs: ada01@csie.ntu.edu.tw
Problem 1: Short Answer Questions (20 points)
(a) (3 points) True or False: To prove the correctness of a greedy algorithm,
we must prove that every optimal solution contains our greedy choice.
Answer: False. We need to prove that our solution (with greedy choice) is
as good as other optimal solutions that may or may not contain the
greedy choice.
(b) (3 points) True or False: Any dynamic programming algorithm that solves n
subproblems must run in Ω(n) time.
Answer: True. It must take Ω(1) time to solve a subproblem, so the total
time is Ω(n).
(c) (4 points) Please explain why the 0/1 knapsack problem may not be solved in
O(nW) time (where n is the number of items and W is an integer representing
the knapsack's capacity) when items have non-integer weights.
Answer: When items have non-integer weights, there may not be overlapping
subproblems (the number of possible sum of weights can be as large
as 2n).
If it can be solved in O(nW) time, we can divide the knapsack's
capacity and all the weights of items by W, obtaining an equivalent
new problem which can be solved in O(n · 1) = O(n) time. That will
imply P = NP, as 0/1 knapsack is NP-Complete.
(d) (5 points) Recall that in the interval scheduling problem, we want to find
the maximum number of compatible jobs given n job requests and their start
times s[i] and nish times f[i] for all 1 ≦ i ≦ n. Please provide a
counterexample showing that a shortest-interval-first greedy strategy does
not always lead to an optimal solution.
Answer: ┌─┬──┬──┬───┐
│ i│s[i]│f[i]│length│
├─┼──┼──┼───┤
│ 1│ 1 │ 5 │ 4 │
│ 2│ 3 │ 6 │ 3 │
│ 3│ 5 │ 10 │ 5 │
└─┴──┴──┴───┘
Optimal solution: Select job 1 and 3 (2 jobs).
Shortest-interval-first: Can only select job 2 (1 job), which is
suboptimal.
(e) (5 points) You're working on a dynamic programming problem that has a
recurrence relation A(i, j) = F(A(floor(i/2), j), A(i, floor(j/2))),
where F is a known function that can be evaluated in constant time, and
A(i, j) = 0 when i = 0 or j = 0. To compute A(m, n) for some m and n,
you can use either a top-down or a bottom-up method. Which one is more
efficient in solving this problem?
Answer: Top-down method is more efficient.
Top-down method only calculates the needed subproblems, which are
of the form A(floor(m/(2^i)), floor(n/(2^j))). There are only
Θ(log(m) log(n)) such subproblems, hence its time complexity is
only Θ(log(m) log(n)).
Buttom-up method will require computing every subproblem,
resulting in time complexity Θ(mn).
(In this problem, the indices of needed subproblems can be easily
predicted, so one can achieve Θ(log(m) log(n)) if you only
calculate these needed subproblem in bottom-up method. If your
answer is "The same" because of this reason, you will get full
credit.)
Problem 2: Asymptotic Notions (10 points)
(a) (5 points) Three divide-and-conquer algorithms are proposed to solve the
same problem. Suppose they are all correct, what are their running time
(in big-O notation) and which one is more efficient? Please justify your
answer.
˙ Algorithm A divides the problem of size n into three subproblems of
size (n / 2) and combines the solutions in linear time.
˙ Algorithm B divides the problem of size n into two subproblems of
size (n - 1) and combines the solutions in constant time.
˙ Algorithm C divides the problem of size n into nine subproblems of
size (n / 3) and combines the solutions in O(n^2) time.
Answer: ˙ For algorithm A, T(n) = 3T(n/2) + n. So
2 lg n k
T(n) = n + (3/2)n + (3/2) n + … = Σ (3/2) n
k=0
And
╭ lg n k ╮ ╭ (3/2)^(lg n) - 1 ╮ ╭ 3^(lg n) ╮
O│ Σ (3/2) │ = O│ ──────── │ = O│ ──── │
╰ k=0 ╯ ╰ 1/2 ╯ ╰ 2^(lg n) ╯
╭ n^(lg 3) ╮
= O│ ──── │
╰ n ╯
Hence T(n) = O((n^(lg 3))/n)O(n) = O(n^(lg 3)).
˙ For algorithm B, T(n) = 2T(n - 1) + 1. Then
T(n) + 1 = 2(T(n - 1) + 1) = 4(T(n - 2) + 1) = …
= O(2^n)(T(1) + 1) = O(2^n)
So T(n) = O(2^n).
˙ For algorithm C, T(n) = 9T(n/3) + n^2. Then
T(n) = n^2 + n^2 + n^2 + … = (log_3 n)(n^2) = O(n^2 (lg n))
(b) (5 points) Does f(n) = O(g(n)) imply 2^(f(n)) = O(2^(g(n)))? Please
justify your answer.
Answer: No, for example, let f(n) = 2n, g(n) = n. Since f(n) = 2g(n) so
f(n) = O(g(n)). But 2^(f(n)) ≠ O(2^(g(n))), since if exists c, N
s.t. n > N => c(2^n) ≧ 2^(2n). Then c shall be greater than 2^n
for all n > N. But 2^n → ∞ as n → ∞ which leads to a
contradiction, so 2^(f(n)) ≠ O(2^(g(n))).
Problem 3: Integer Multiplication (10 points)
Given two n-bit integers x and y, please write pseudocode to solve integer
multiplication by dividing the original n-bit problem (xy) into three (n/2)-bit
subproblems, recursively. Your algorithm should run in O(n^(lg 3)) time.
Answer: See the solution of HW1. Your solution must
˙ {Discribe, Give a pseudocode} of a correct algorithm. [7 points]
˙ Justify the running time is T(n) = 2T(n) + O(n)
=> T(n) = O(n log(n)). [3 points]
Problem 4: Christmas Again (20 points)
Christmas is approaching. You're helping Santa Clauses to distribute gifts to
children.
For ease of delivery, you are asked to divide n gifts into two groups such
that the weight difference of these two groups is minimized. The weight of
each gift is a positive integer.
(a) (10 points) Please design an algorithm to find an optimal division
minimizing the value difference. The algorithm should find the minimal
weight difference as well as the groupings in O(nS) time, where S is the
total weight of these n gifts.
Hint: This problem can be converted into making one set as close to S/2
as possible.
Answer: We consider an equivelant problem of making one set as close to
W = floor(S/2) as possible.
Define FD(i, w) to be the minimal gap between the weight of the
bag and W when using the first i gifts only. WLOG, we can assume
the weight of the bag is always less than or equal to W.
Then fill the DP table for 0 ≦ i ≦ n and 0 ≦ w ≦ W in which
F(0, w) = w for all w, and
FD(i, w) = min{FD(i - 1, w - w_i) - w_i, FD(i - 1, w)}
if FD(i - 1, w - w_i) ≧ w_i
= FD(i - 1, w) otherwise
This takes O(nS) time. FD(n, W) is the minimum gap.
Finally, to reconstruct the answer, we backtrack from (n, W).
During backtracking, if FD(i, j) = FD(i - 1, j) then i is not
selected in the bag and we move to F(i - 1, j). Otherwise, i is
selected and we move to F(i - 1, j - w_i).
We show that this problem has optimal substructure.
Proof by contradiction.
￣￣￣￣￣￣￣￣￣￣￣
Case 1 (i is not selected): Let OPT be an optmal solution to
FD(i, w) but OPT is not optimal for
F(i - 1, w). Then there exists another
OPT' that is optimal for F(i - 1, w).
However, OPT' will be a better solution
for FD(i, w) too.
Case 2 (i is selected): Let OPT be an optmal solution to FD(i, w)
but OPT\i is not optimal for
F(i - 1, w - w_i). Then there exists
another OPT' that is optimal for
F(i - 1, w_i). However, OPT' ∪ i will be
a better solution for FD(i, w) too.
(b) (5 points) Please write down the recurrence relation you derived in (a),
and use it to complete a DP table for solving the following problem
instance.
┌─────┬─┬─┬─┬─┐
│ Gift i │ 1│ 2│ 3│ 4│
├─────┼─┼─┼─┼─┤
│Weight w_i│ 2│ 2│ 4│ 3│
└─────┴─┴─┴─┴─┘
Answer: The range of DP table are 0 ≦ i ≦ n and 0 ≦ w ≦ W.
FD(0, w) = w for all w
FD(i, w) = min{FD(i - 1, w - w_i) - w_i, FD(i - 1, w)}
if FD(i - 1, w - w_i) ≧ w_i
= FD(i - 1, w) otherwise
┌┬─┬───────────┐
│i╲w│ 0 1 2 3 4 5│
├─┴┼───────────┤
│ 0 │ 0 1 2 3 4 5│
├──┼───────────┤
│ 1 │ 0 1 0 1 2 3│
├──┼───────────┤
│ 2 │ 0 1 0 1 0 1│
├──┼───────────┤
│ 3 │ 0 1 0 1 0 1│
├──┼───────────┤
│ 4 │ 0 1 0 0 0 0│
└──┴───────────┘
(c) (5 points) You are now asked to divide n gifts into 2^k groups such that
the sum of the pairwise weight differences (i.e., Σ_(∀i>j) |s_i - s_j|,
where s_i is the weight of group i) is minimized. k is a positive integer.
You come up with a divide-and-conquer algorithm that recursively divides
gifts into two groups while minimizing the weight difference of these two
groups. The algorithm stops when the recursion depth reaches k.
Please provide a counterexample to show that this approach is not always
optimal.
Answer: Divide {3 3 4 1 1 1 1 1 1 1 1 1 1} into four groups.
˙ Step1: {3 3 4}, {1 1 1 1 1 1 1 1 1 1}
˙ Step2: {3 3}, {4}, {1 1 1 1 1}, {1 1 1 1 1}
However, the best way to separate is {1 1 3}, {1 1 3}, {1 4},
{1 1 1 1 1}.
Problem 5: Zoologist (20 points)
As a zoologist, you're interested in studying how to communicate with Pokemons.
Since most Pokemons can make sound, the length of sound can be used to encode
1-bit of information. We will use a long sound to represent 1 and a short sound
to represent 0.
(a) (5 points) You want to teach Pokemons seven commands that are frequently
used during training. Please draw an optimal prefix tree for encoding
these commands:
┌─────┬──┬───┬──┬───┬──┬──┬──┐
│ Word │eat │sleep │jump│drink │run │sit │hide│
├─────┼──┼───┼──┼───┼──┼──┼──┤
│ Frequency│0.25│ 0.15 │0.12│ 0.19 │0.07│0.14│0.08│
└─────┴──┴───┴──┴───┴──┴──┴──┘
○
╱ ╲
○ ○
╱ ╲ run
○ ○
sit ╱ ╲
○ ○
jump hide
(b) (9 points) You found a secret training document written by another trainer,
which shows that the trainer encodes four commands using a prefix tree as
follows:
Suppose the prefix tree is constructed using Huffman encoding. For each of
the following statements, please explain whether it is true or false:
˙ The command run must have a frequency higher than 1/3.
˙ The command jump must have a frequency less than 1/8.
˙ The frequency of command run is no less than it of command sit.
(c) (6 points) You observed that making a long sound consumes r times more
energy than making a short one. Please revise the prefix code you came up
with in (a) to minimize the expected energy consumption per word for the
7-word example when r = 100. Please briefly justify your answer.
Answer: (a) ╭──╮
│1.00│
╰──╯
╭──────┴──────╮
╭──╮ ╭──╮
│0.44│ │0.56│
╰──╯ ╰──╯
╭───┴───╮ ╭───┴───╮
╭──╮ ╭──╮ ╭──╮ ╭──╮
│0.25│ │0.19│ │0.26│ │0.30│
╰──╯ ╰──╯ ╰──╯ ╰──╯
eat drink ╭─┴─╮ ╭─┴─╮
╭──╮╭──╮╭──╮╭──╮
│0.14││0.12││0.15││0.15│
╰──╯╰──╯╰──╯╰──╯
sit jump sleep ╭─┴─╮
╭──╮╭──╮
│0.07││0.08│
╰──╯╰──╯
run hide
(b) (i) False ("higher" means ＞, not ≧).
(ii) False.
(iii) True.
(c) See the following table:
┌─────┬───┬───┬──┬───┬───┬──┬───┐
│ Word │ eat │sleep │jump│drink │ run │sit │ hide │
├─────┼───┼───┼──┼───┼───┼──┼───┤
│ Frequency│ 0.25 │ 0.15 │0.12│ 0.19 │ 0.07 │0.14│ 0.08 │
├─────┼───┼───┼──┼───┼───┼──┼───┤
│ Code │000000│ 01 │0001│ 1 │000001│ 001│ 00001│
└─────┴───┴───┴──┴───┴───┴──┴───┘
Problem 6
(a) (4% for algorithm correctness and time complexity, 6% for the proof of
greedy choice property)
Idea: Move as far as possible in each day, and rest the last safety city.
Answer: C style pseudo code:
start = 1;
while (l != n)
{
// find the farthest city within 100 km
r = start;
while (r <= n and L[r] - L[start] <= 100) r += 1;
// r is out of range, minus 1
r -= 1 ;
// find the safe city
while (start < r and z[r] != 0) r -= 1;
assert(start != r); // or no solution
start = r;
rest(start);
}
(You don't need to prove the time complexity of your algorithm,
but you will get some penalties if your time complexity is
incorrect.)
The following is the proof of the greedy choice property.
Proof. Let x is the city chosen by our greedy algorithm and OPT is
the optimal solution.
˙ If x 屬於 OPT, it is done.
˙ If x 不屬於 OPT, assume y is the first rest choice city
in OPT. From the greedy rule, we know that L[y] ≦ L[x].
Let z is the second rest city in OPT. We have
L[z] - L[y] ≦ 100 and also L[z] - L[x] ≦ 100. So the
solution OPT' = OPT \ {y}∪{x} is also a valid solution
and |OPT| = |OPT'|.
(b) (4% for algorithm correctness and time complexity, 6% for the proof of the
correctness of algorithm)
Answer: Let f(x) is the optimal stress from city 1 to city x. Consider all
city that can rest before x, we have
f(x) = min f(k) + (100 - (L[x] - L[k]))^2
1≦k＜x
z[k]=0
f(1) = 0
(You don't need to prove the time complexity of your algorithm,
but you will get some penalties if your time complexity is
incorrect.)
Proof. Let c(S) is the total stress of the solution S. At the
first, let OPT_i is the optimal solution of f(i) and x is
the last city rested in the OPT_i.
Suppose OPT' = OPT_i \ {i} is not the optimal to f(x).
Let s is the solution of f(x). We know that
c(s∪{i}) = f(x) + (100 - (L[i] - L[x]))^2
< c(OPT') + (100 - (L[i] - L[x]))^2 = c(OPT_i)
Then we have a solution s∪{i} which is better than OPT_i.
Contradiction.
Now, we know that OPT_i is optimal if all OPT_j are optimal
for all j < i. We already prove the boundary case.
(f(1) = 0), then the correctness is proved by induction.
Problem 7
Answer:
(a) find_majority(A[1 ... n]):
if n == 1:
return A[1]
el = find_majority(A[1 ... floor(n/2)])
er = find_majority(A[floor(n/2) + 1 ... n])
if el == er:
return el
fl = frequency of el in A
fr = frequency of er in A
if fl > ceil(n/2):
return el
elif fr > ceil(n/2):
return er
else:
return NONE
(b) S1: find_majority(A[1 ... n]):
original_A = A
while A.size > 1:
temp = []
pair up the elements in A
for each pair:
if pair[2] == NONE or pair[1] == pair[2]:
temp.append(pair[1])
A = temp
if A.size == 0 or frequency of A[1] in original_A <= ceil(n/2):
return NONE
else:
return A[1]
S2: Moore's Voting Algorithm
find_majority(A[1 ... n]) :
maj_index = 0
count = 0
for i = 1 to n:
if count == 0:
maj_index = i
count = 1
elif A[maj_index] == A[i]:
count++
else:
count--
if frequency of A[maj_index] in A > ceil(n/2):
return A[maj_index]
else:
return NONE
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 59.115.38.138
※ 文章網址: https://www.ptt.cc/bbs/NTU-Exam/M.1485069429.A.550.html
※ 編輯: rod24574575 (59.115.38.138), 01/22/2017 15:18:24