=========================preview======================
(COMP271)2008midterm08f.pdf
Back to COMP271 Login to download
======================================================
COMP 271 Design and Analysis of Algorithms
Fall 2008 Midterm Exam

1. Multiple Choice (50 pts) Each question below has exactly one of the following answers.
(a)(1) (b)(logn) (c)(n) (d)(n logn) (e)(n2)
For each question, write down the letter that corresponds to your answer, or I dontknow. Youdo not needtojustifyyour answers. Each correct answer earns you 5 points, an incorrect answer gives you nothing. You earn 1 point for each question for which you write I dont know.
n
n

?
i
1.1 What is

i=1 n
i

?
n

1.2 What is

i=1

1.3 How many digits do you need to write 2n in decimal?
1.4 What is the solution of the recurrence T (n)=16T (n/4)+n, T (1)=1(assum-ing n is a power of 4)?

1.5 What is the solution of the recurrence T (n)= T (n . 1)+ 21 n ,T (1)=1?
1.6 Let G beaweighted, undirected, connectedgraph with n vertices and at most 100n edges, where all the edges have the same weight. Given two vertices u and v in G, how fast can you .nd a shortest path from u to v?
1.7 In randomized quicksort, we pick the pivots randomly. If we instead always select the median as the pivot using the deterministic linear-time selection algorithm, what is the running time of quicksort?
1.8 Inanundirectedgraph with n vertices, whatisthemaximumpossiblenumber of edges?
1.9 Suppose you insert n numbersinto aninitially emptypriorityqueue(imple-mented as a heap), what is the worst-case running time?
1.10 What is the running time of the fastest algorithm to sort 100,000,000,000,000 numbers?
2. (15pts)Suppose we aregiven an array A[1..n]of distinct numbers with the special propertythatA[1]>A[2]and A[n.1] <A[n]. We saythatan element A[x]is alocal minimum if it is less than both its neighbors, or more formally, if A[x . 1] >A[x] and A[x]<A[x +1]. For example, there are 2 local minima in the following array:
9372145
1
Wecanobviously.nd alocal minimumin O(n)timeby scanning through the array. Describe and analyze an algorithm that .nds a local minimum in O(logn)time. If there is more than one local minimum, .nding any of them is .ne. [Hint: Withthe given boundary conditions, the array must have at least one local minimum. (You dont need to prove this hint.)]
3. AstheCEOofABNF1,youwouldliketohirea .nancial advisorimmediatelytohelp youdealwiththecurrent .nancial crisis. Youhavereceivedatotal of n applications. These candidates are numbered from 1 to n, in the order their applications have been received. Being a busy CEO, you only have time to interview one candidate every day, but you need an advisor right away. So you decide to use the following greedy hiring algorithm:
for i=1, 2, ..., n do
interview candidate number i; if you dont have an advisor yet, or candidate number i is better than your current advisor then
.re your current advisor;
hire candidate number i (.);
end
end

Since for each hire you will pay the new assistant some sign-on bonus, you would liketoknowhow many timesli