=========================preview======================
(COMP271)[2008](f)midterm~3938^_75057.pdf
Back to COMP271 Login to download
======================================================
COMP 271 Design and Analysis of Algorithms
Fall 2008 Midterm Exam Solutions

1.
Multiple Choice

1.1(d) 1.2(c) 1.3(c) 1.4(e) 1.5(a) 1.6(c) 1.7(d) 1.8(e) 1.9(d) 1.10(a)

2.
If n 3 we can solve the problem trivially. Let m = .n/2.. We look at the three elements A[m .1],A[m],A[m +1]. There could be the following cases:

(a)
If A[m .1] >A[m]and A[m]<A[m +1], then A[m]is a local minimum and we are done;

(b)
If A[m .1] <A[m]<A[m +1], then by the boundary condition there must be at least one local minimum between A[1]and A[m], so we recursivelysolve the problem on A[1..m];

(c)
If A[m .1] >A[m]>A[m +1], similar to the case above, we recursively solve the problem on A[m..n];

(d)
If A[m .1] <A[m]and A[m]>A[m +1], we can recurse into either A[1..m] or A[m..n], but not both.




In any case we eitherterminate or reducetheproblem sizeby half. Sothe running time of the algorithm is O(logn).
3. (a)Line . will be executed n times in the worst case. The candidates can arrange themselves such that they send in their applications in the decreasing order of their quality.
(b) Let Xi be de.ned as in the hint. Then Pr[Xi =1] =1/i, since this the i-th candidate is hired if and only if he is the best among the .rst i candidates. Thus the expected number of times line . will be executed is
nnn n
... . 1
EXi = E[Xi]= Pr[Xi =1] = = O(logn).
i
i=1 i=1 i=1 i=1
4. For each edge e in the graph with weight w(e), change its weight to .w(e). Run Prims algorithm on this graph G with the new weights. Since Prims algorithm works with both positive and negative weights, the minimum spanning tree of G is the maximum spanning tree of G.
1