=========================preview======================
(COMP271)2008_fall_final.pdf
Back to COMP271 Login to download
======================================================
COMP 271 Design and Analysis of Algorithms Fall 2008 Final Exam
1. Multiple Choice I (12 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. You do not need tojustifyyour answers. Each correct answer earnsyou3points, anincorrect answer (or no answer)gives you nothing.
n
. n
1.1 What is ?
2i
i=1


1.2 What is the solution of the recurrence T (n)= T (n/2)+n logn, T (1)=1?
1.3 Inthegreatest commondivisor(gcd) problem, we aregiven twopositiveintegers n and m,and thegoalisto .nd thelargestintegerthatdividesboth n and m. Suppose n>m, what is the input size of this problem?
1.4 What is the running time of the fastest possible algorithm to solve Sudoku puzzles? ASudokupuzzle consists of a9 9 grid of squares, partitioned into nine 3 3 sub-grids; some of the squares contain digits between 1 and 9. The goal of the puzzle is to enter digits into the blank squares, so that each digit between 1 and 9 appears exactly oncein each row, each column, and each33 sub-grid. Theinitial conditions guarantee that the solution is unique.


A Sudoku puzzle. Dont try to solve this during the exam!
2. Multiple Choice II (8 pts) Aliens from another world come to Earth and con.rm our conjecture that the 3-SAT
problem cannot be solved in polynomial time. Then what can you say about each of the following statements? Choose your answers from the three below:
(a)True (b)False (c)Unknown
1

For each question, write down the letter that corresponds to your answer. You do not need tojustifyyour answers. Each correct answer earnsyou2points, anincorrect answer (or no answer)gives you nothing.
1.1 P .NP .
=

1.2 Foraproblem X in NP ,if we cangive a reduction that X P 3-SAT, then X cannot be solved in polynomial time.


1.3 No NP-complete problem can be solved in polynomial time.
1.4 Given a graph G with n vertices, deciding whether G has a clique of size 10 cannot be done in polynomial time.
3. (.c, 16 pts) In the midterm you designed an algorithm to .nd a local minimum in a one-dimensional array of size n. Now you are asked to design an algorithm to .nd a local minimum in an n n two-dimensional array(a matrix). A numberin a matrixis alocal minimumifitis smallerthan all ofitsfour neighbors(if there are any). You may assume that all the numbers are distinct. For example, in the matrix below, all the underlined numbersarelocal minima. Youralgorithmjustneedsto .nd only oneofthem.
. 20 30 40 50 60 .
. . . . . . 31 45 66 35 33 36 46 44 25 21 55 37 43 66 56 . . . . . .
99 43 24 75 80

2
For full credits, your algorithm should run in O(n)time. Note that there are nnumbers in the matrix. [Hint: use divide-and-conquer.]
4.
(16 pts) Give a directed, acyclic graph G =(V, E), a source vertex s V and a sink vertex t V ,designand analyzeanalgorithmto .ndthel