=========================preview======================
(comp271)[2009](s)mid~PPSpider^_10196.pdf
Back to COMP271 Login to download
======================================================
COMP 271 Design and Analysis of Algorithms
Spring 2009 Midterm Exam

1.
Print your name and student ID at the top of every page (in case the staple falls out!).

2.
This is a closed-book, closed-notes, open-brain exam.

3.
Time limit: 120 minutes.

4.
You should answer all the questions on the exam. At least you should read all the questionsthey are not ordered by their di.culty!

5.
You dont have to give the fastest algorithm required by the problem. You can still earn partial credits if you give a slower algorithm.

6.
You can write on the back of the paper if you run out of space. Please let us know if you need more scratch paper.

7.
The background sheets are provided at the end of the exam paper.

8.
Relax and breathe.


1. Multiple Choice (4 5 = 20 pts) Each question below has exactly one of the following answers.
(a) (1) (b) (log n) (c) (n) (d) (n log n) (e) (n2)
For each question, write down the letter that corresponds to your answer, or I dont know. You do not need to justify your answers. Each correct answer earns you 4 points, an incorrect answer gives you nothing. You earn 1 point for each question for which you write I dont know.
n
1
1.1 What is ?
i
i=100
1.2 What is the solution of the recurrence T (n)=8T (n/8) + (n),T (1)=1? Youcan assume that n is a power of 8.
1.3 Suppose that one day you got a magic priority queue that supports insertion, decrease-key, and extract-min operations all in O(1) time per operation. If you plug in this magic priority queue into Dijkstras algorithm, what is its running time on a graph with n nodes and 10n edges?
1.4 In an undirected graph with n vertices, what is the maximum possible number of edges?
1.5 In an initially empty union-.nd data structure, suppose you .rst issue n Create-Set operations, then n/4 Union operations, then n/10 Find-Set operations, then another n/4 Union operations, and .nally n/20 Find-Set operations. Assume that we use union-by-height, but not path compression. What is the total running time?
2. (20 pts) You are given an array A[1..n], which stores a sequence of 0s and then followed by a sequence of 1s.
(a)
(10 pts) Design an O(log n)-time algorithm to .nd the location of the last 0, i.e., .nd the k such that A[k]=0 and A[k +1] = 1.

(b)
(10 pts) Suppose you dont know the value of k but you know that it is much smaller than n. Can you improve the running time of your algorithm to O(log k) instead of O(log n)? Explain your algorithms correctness and derive its running time.


3. (20 pts) We showed in class that the randomized selection algorithm has an expected running time of O(n). Since generating random numbers is quite expensive, often people also want to minimize the number of random number generations. In this problem, you will prove that the algorithm draws only O(log n) random pivots in expectation. You will follow the steps below to obtain