=========================preview======================
(COMP271)[2009](f)midterm~ac_ctkae^_10192.pdf
Back to COMP271 Login to download
======================================================
COMP 271 Design and Analysis of Algorithms Fall 2009 Midterm Exam Solutions
1.
Quick AnswerQuestions

1.1 (1) 1.2 (n3)1.3 (n)1.4 (|E|)1.5 (n).

2.
We use divide-and-conquer:


FindLocalMinimal (Node u)
{
if u is aleaf then
return u and stop;
else if us left child < u then
FindLocalMinimal(us left child);
else if us right child < u then
FindLocalMinimal(us right child);
else return u and stop;
}

The initial call is FindLocalMinimal(root). In a recursive call on a node u we maintain the invariant that u is smallerthanitsparent(ifithas one). Soif u is smaller than both its children then it is a local minimum. If we ever reach a leaf then it must be a local minimum because of the invariant.
Since the height of the binary tree is O(logn), the running time of the algorithm is O(logn).
3. Let Xi be number of steps taken in the i-th second towards the dorm. So we have E[Xi ]=1 (1.1/i)+(.1) 1/i =1.2/i. Let X be the total number of stepsbetweenyou
n
and thedorm after n seconds, wehave X = n.(X1 +X2 + +Xn)= n.(1.2/i)=
i=1
n
n .n + (2/i)=(logn).
i=1
4.
Algorithm: Do a DFS starting from s and build the DFS tree. If there is a back edge pointing to s, then output yes; otherwise output no. The running time is the same as that of the DFS, which is O(|E|).

Correctness:The yes case:Lettheback edgebe(u, s). Then the path in the DFS tree from s to u plus the edge(u, s) forms a cycle. The no case: There are no back edges pointing to s, so s has a single edge connecting to each of its subtrees. Also there are no cross edges in a DFS tree, so there cant be any cycles passing through s.

5.
Let T be any MST of G. Suppose that T doesnt contain(u, v). Since T has to connect v to u via apath,it mustinclude some(u, w)and v =.w. Since(u, v)has the smallestweight among all edges connecting u, we have w(u, v) <w(u, w). We add the edge(u, v) to T which creates one and only one cyclein T . We then remove the edge(u, w)which will turn




T back to a tree. Call the new tree T . Wehave w(T )= w(T )+w(u, v).w(u, w)<w(T ). However, this contradicts the hypothesis that T is an MST.
1