# ADA 104 期中考古
###### tags: `Exams`
###### tags: ADA
# Problem 1: Short Answer Questions (25 points)
Answer the following questions and briefly justify your answer.
___
(a) (3 points) True or False: The 0/1 knapsack problem can be solved in polynomial time with respect to the size of the input, when the knapsack as well as every object has an integer weight.
False, need pseudo-polynomial time, exponential to the size of w (in bits)
___
(b) (3 points) True or False: To prove the correctness of a greedy algorithm,
we must prove that every optimal solution contains our greedy choice.
False, we just need to prove that one particular optimal solution contains a greedy choice using exchange argument on an OPT
___
(c\) (3 points) True or False: When proving correctness using an exchange
argument, we want to transform an optimal solution into the greedy solution
without hurting its quality.
True, we want to make sure OPT' is equal or better
___
(d) (3 points) True or False: Any dynamic programming algorithm that solves n
subproblems must run in Ω(n) time.
True, we need to solve each subproblem with at least O(1) time
___
(e) (3 points) Given the recurrence relation A(i,j) = F(A(i-2,j+1),A(i+1,j-2)),
provide a valid traversal order to fill the DP table or justify why no valid
traversal exists.
Order all the input by i+j, since each call will call something with value i+j-1.
___
(f) (3 points) Your friend implemented Merge Sort based on the following
pseudocode, in which A is an array and MergeSort(A,p,r) should sort the
elements in A between indices p and r. However, the running time of
MergeSort(A,1,n) seems to be Θ(n^2) in worst case, higher than O(n log n).
Please help your friend debug the code by explaining which one of these four
steps should be modified.
MergeSort(A,p,r)
if p=r //step 1
return
randomly select q between p and r //step2
MergeSort(A,p,q) //step 3
MergeSort(A,q+1,r) //step 4
Combine the two sorted array in linear time
Step 2 should be modified. Merge sort should split into 2, else worse case may be splitting into 1 + n-1.
___
(g) (7 points) Describe a real-world problem that you have solved or have
thought about solving using technique learned in the class. Make an educated
guess about how fast your algorithm might be and how much time it would take to
solve the same problem using a brute-force approach instead.
??? 現場掰一下吧
# Problem 2: Asymptotic Notations (15 points)
___
(a) (7 points) Rank the following functions by an increasing order of the
growth rate:
$$n^{(3/4)}, n^n, log (2n), n log n, e^{(ln n)}, 3^n, 2^{\sqrt{log n}}.$$
$$
log(2n) < 2^{\sqrt{log n}}
< n^{3/4} < e^{lnn} < nlogn < 3^n< n^n$$
___
(b) (8 points) Solve the following recurrence by giving a tight Θ-notation
bound:
$$T(n) = 2T(\sqrt n)+(log n)^2 log log n
$$
Answer: $$\theta (log(n)^2loglogn) $$
___
# Problem 3: Maximum Subarray of a Circulat Infinite Sequence (30 points)
Recall that a maximum subarray of A is a contiguous subarray a_s,...,a_t of A such that $$\sum_{s ≦ i ≦t} a_i$$ is maximized over all s and t, 0≦s≦t.
Given a circular infinite sequence $A = \{a_0,a_1,a_2,...\}$ in which $a_i = a_j$
if i = j mod n, please answer the following questions.
___
(a) (5 points) Suppose $\sum_{0≦i<n} a_i$ > 0. What is the length of the maximum
subarray of A? Briefly explain your answer.
Length is infinite, since this is circular, and each segment has >0 sum, we can sum up infinitely to get a length of infinity
___
(b) (5 points) Suppose $\sum_{0≦i<n} a_i < 0$. Please briefly explain why the
length of any maximum subarray is at most n.
Since the sum over the entire repetitive sequence is negative, we can view this sequence as one unit a with a negative value. It becomes very obvious why the first and last element won't choose to include this value, as the maximum subarray (using DC approach) of the first 2 nodes and the last 2 nodes definitely do not contain this segment
___
(c\) (10 points) Please design an algorithm to find a maximum subarray of the
circular infinite sequence A in O(n log n) time. Please justify the correctness
and running time of your algorithm.
> Hint: we learned how to find a maximum subarray of a finite sequence in O(n log n) using divide and conquer. Can you modify it to solve this similar
problem?
Basically find the max subarray over 2n, just so that anything that circles back is considered. Then use the same algorithm
___
(d) (10 points) Can you reduce the running time of your algorithm to O(n)? If
you have designed a O(n) algorithm in (c), then you will get full credits for
(c) automatically.
> Hint: use dynamic programming. How to represent a maximum subarray ending at a certain position?
https://www.geeksforgeeks.org/largest-sum-contiguous-subarray/
最下面有DP作法
___
# Problem 4: SimCity (20 points)
You are a mayor of a virtual city. The city has n districts located along a
line [0,n-1], and the ith district is located at i with a population p_i > 0.
As a mayor, you need to decide where to build power plants such that every
citizen can enjoy electricity while minimizeing their complaints about
pollution.
Each power plant is built at an integer location and can provide
electricity to citizens living within an integer range R. For example, if
R = 2, a power plant in District 3 can provide electricity to citizens living
in Districts 1 to 5.
The compliant (complaint?) level is qualified by the totaln population living
in the districts with power plant. For example, if R = 2, n = 6, then we can
build power plants in District 2 and 5 for a full coverage, and the cost of
pollution is p_2 + p_5.
___
(a) (10 points) Given R, n and p_i for all 0≦i<n, please design a O(nR)
dynamic programming algorithm to find an optimal allocation of power plants
such that every citizen can enjoy electricity while minimizing their
compliant (complaint?) level. Please prove that the problem has optimal
substructure and justify the running time of your algorithm.
Answer:
Make 2 arrays, dp[n] and end[n]. dp[i] stores the optimal pollution (min) up until i, and you must add a power plant at i.
$$dp[i] = P_i + min(dp[i-2r-1], dp[i-2r], ... dp[i-1])
$$
//start from n-r-1 as that is the first one not covered
Correctness: Since we assume we have a plant at each i, we need to consider how to overlap that with everything before it. In the end, we just need to examine the last r cities to find the minimum.
The running time of this should be O(nR) because, firstly, there will be n entries in the array. For each entry, we will test for R places and see whether adding this city would be better. We will min it with the result of dp[i-1] if dp[i-1] does reach i.
==檢查一下 不是非常確定==
___
(b) (10 points) Like in every city, your citizens love to live nearby schools,
subway stations, etc., which result (results?) in an uneven geographical
distribution of population. Particularly, in your city, p_i≧p_{i+1} for all
0≦i≦n-2. Knowing this skewed distribution, please design a greedy algorithm
to find an optimal allocation of power plants. Your greedy algorithm should be
asymptotically faster than the one in (a). Please explain the running time of
your algorithm and prove the greedy-choice property.
Answer:
Greedy choice = go to the rightmost and place it there. Easy to prove with exchange argument. Should take time of O(n/R).
___
# Problem 5: Pirates of the Caribbean (20 points)
You are a happy pirate sailing on the Caribbean Sea. Your captain, Jack,
recently obtains a new ship and asks you to design an inter-ship communication
system that can encode and broadcast his commands. Luckily you have taken an
algorithm class!
(a) (10 points) You have been on the ship long enough to know that Jack uses the
following seven commands most frequently:
|Command|accelerate|stop|left|right|ack|attention|fire|
|-------|:---------|:---|:---|:----|:--|:--------|:---|
|Occurrences per day|10|8| 6 | 6 | 4 | 2 | 1 |
Please create an optimal code using Huffman coding so as to minimize the
expected length of binary codewords per command. Please also calculate the
expected length of codewords.
Answer:
Expected length = 96/37? (我數學真的不好)
//24 應該是22, 39 應該是 37, 數學不好
//不過順序跟code不變
(b) (10 points) The initial testing was successful, so now the captain asks you
to extend your system to cover n commands he uses daily. Since there is no
computer on the ship, computing an optimal code by hand can be pretty tiring
for a large n. Another pirate suggests the following divide-and-conquer
approach:
Given n commands and their occurrences f_i (0≦i<n),
‧Divide Sort the n commands by their occurrences from left to right, and
then divide them into two groups, G_l and G_r, such that the sum of
occurrences in the left group is as close to the sum in the right as
possible (ties may be broken arbitrarily). For example, if the sorted
frequencies are 30,25,20,20,5, then G_l = {30,25} and G_r = {20,20,5}.
‧Conquer Assign G_l and G_r to two different pirates and ask them to
compute an optimal code for their respective group. If one thinks the
group is still too large to solve, he or she can further divide the work
by repeating the first step.
‧Combine To combine, prepend 0 to the codewords in G_l, and prepend 1 to
the codewords in G_r.
Do you agree that this divide-and-conquer approach can also produce an
optimal code? If yes, please justify the correctness of this algorithm. If not,
please provide a counterexample with its codewords.
Answer:
False: 2 2 2 1 1 1 1 1 1
If you construct this, you would realize that 1 on the right should be changed with 2 on the left since the top level 1 is above a 2.
# Problem 6: HH-code Again (10 points)
HH-code is a kind of string with 0 and 1. For a given HH-code H, any
subsequence of H is called a hidden HH-code of H. For example, if there is an
HH-code H = 1011, then 1, 0, 10, 11, 101, 111, 011, 1011 are all the different
hidden HH-codes of H.
When analysing time complexity, assume every basic arithmetic operation
(i.e. addition, subtraction, multiplication, and division) takes O(1) time.
If the length of HH-code is N, and we want to know the number of different
hidden HH-code with a specific length K. Please design an algorithm to
calculate the number in O(KN) time.
Answer:
==不會ㄝ 大神求救~~==
考慮 $dp[i][j]$ 的狀態，代表現在考慮字串的前 $i$ 個字元，並選擇長度為 $j$ 的 HH-code (且最後一個選的字元是 $i$)有幾種方法。DP 轉移式為 $$dp[k_0][j + 1] += dp[i][j]$$$$dp[k_1][j + 1] += dp[i][j]$$，其中 $k_x$ 代表大於 $i$ 的 index 中滿足 $s[k_x] = x$ 的最小 index。
# Problem 7: Counting Significant Inversions (10 points)
We have learned how to count inversions in class. Now let's consider a
slightly different problem.
Given a sequence of unique numbers $B = b_1, b_2, ..., b_n,$ a significant
inversion is a pair of numbers $b_i$ and $b_j$ in this sequence such that $i < j$ and
$b_i > 2b_j$. Let SI(B) be the set of significant inversions in B. For example,
if B = {1,3,5,2}, SI(B) = {(5,2)}, and the number of significant inversions
|SI(B)| is 1.
Given a sequence B with n unique numbers, please design an algorithm to
calculate the number of significant inversions |SI(B)| in O(n log n) time.
Please briefly explain why your algorithm indeed runs in O(n log n).
Answer:
Similar to a mergesort algorithm like we did in homework, we can count the inversion when we are recombining the sorted arrays. However, instead of +1 to the inversion everytime right > left, we need to make sure right > 2left. We can do this by maintaining a pointer that points to the smallest value larger than 2l in r. This pointer will only go to the right, and at most n times, so in the end should add O(n) to each merge which doesn't change the complexity
Sign in with Wallet
Connect another wallet