=========================preview======================
(COMP271)[2009](f)final~tm_clh^sol_10191.pdf
Back to COMP271 Login to download
======================================================
1.
2.
3.
4.
5.
6.
1.3
(n logn)
2.4
false. ToprovesomeproblemtobeNP-complete,wealsoneedtoshowthatitbelongs
toNP.UNSATisnot knowntobeinNP,sowecannot concludethatUNSATisNPC.
(a) Using binary search from 1 to n .oors, we have T (n)= T (n )+1. T (n)= O(logn).
2
(b) Divide the .oors into n groups of n layers. Test the highest .oor in each group
bottom-up until the .rst bottle breaks. This needs n trials. After this we know
which group k belongs. Then we test each .oor in this group bottom-up to .nd
out the exact value of k. This also costs n trials. So totally, the complexity is of
O(2 n)= O( n).
Thisproblemcanbe solvedby dynamicprogramming. Let Pi denotethe optimalpenalty of reaching hotel ai. We set a0 =0. Then we have
0 if i =0
Pi =
min{Pj +(ai .aj .200)2 } if 0 j <i
We can compute P1,P2 ,...,Pn in this order. Computing each Pi takes O(n)time, so the
complexity of O(n2). The .nal optimal penalty will be Pn. In order to construct our optimal solution, we need an auxiliary array A[i] to record optimal result in each step. A[i]= k records the value k which denotes the last stop ak before reaching hotel ai. Then A[n] records the last stop before reaching an. Then we recursively .nd the last before reaching aA[n]. This takes at most O(n)time.
Thisproblemis similartotheproblem of chain matrix multiplication. Itis also solvedby dynmaicprogramming. Let Ti,j denotethe optimal tree which containsthe nodesfrom ai to aj . The recursive rule is
0 if i = jB(Ti,j )= minik<j {B(Ti,k )+B(Tk+1,j )+f (ai)+ + f (aj )} if i<j
We can compute all the B(Ti,j ),i j, row by row in the order i = n, n .1,..., 1. Within each row, we computefromleft to right j = i,... ,n. Computingeach B(Ti,j )naively takes O(n2)time: we need to try O(n)di.erent choices and each choice involves a summation. But observe that
min {B(Ti,k )+B(Tk+1,j )+f (ai)++f (aj )}= min {B(Ti,k )+B(Tk+1,j )}+f (ai)++f (aj ).
ik<jik<j
Soweonly need tocomputethesummationonceforall thechoices. Thuscomputing each B(Ti,j )takes O(n)time, and the total running time is O(n3).
Compare any optimal solution O and the greedy solution G. We will transform O to G step by step without changing the number of selected vertices. In each step, we look at the lowest vertex in O that is not in G. Let this vertex be u. If no such vertex exists, then by the greedy nature of G, we must have O = G.
Consider all edges below u. All these edges must be already covered by the vertices in G below u, because G didntpick u. These vertices also belong to O because u is the lowest vertex where O and G di.er. Note that because O is optimal, us parent must not be in O, otherwise we can improve O by not selecting u. So we can replace u by itsparent in O without making any edge uncovered. Repeating this step will eventually convert O to G.
1
7. First, we prove DKite is a NP problem. To show that DKite N