=========================preview======================
(COMP271)[2010](f)final~angaa^_52907.pdf
Back to COMP271 Login to download
======================================================
THE HONG KONG UNIVERSITY OF SCIENCE & TECHNOLOGY
Department of Computer Science & Engineering
COMP 271: Design and Analysis of Algorithms
Fall 2010
Final Examination
Instructor: James Kwok (L1) / Huamin Qu (L2)
Date: Friday, 17 Dec. 2010
Time: 16:30 C 19:30
Venue: Sports Hall
.
This is a closed-book examination.
.
Your answers will be graded according to correctness, ef.ciency, precision, and clarity.
.
During the examination, you should put aside your mobile phones, PDAs and all other electronic devices. In particular, all mobile phones should be turned off completely. Calculators are allowed.
.
This question booklet has ?? single-sided pages. Please check that all pages are properly printed before you start working.
Student name: Student ID: Email: Lecture session:
Question Score Maximum Question Score Maximum
1 10 6 10
2 10 7 10
3 10 8 10
4 15 9 15
5 10
TOTAL:
1. Recurrence Equations (10 points total)
Given the following recurrence equation:
T (1) = 0
T (2) = 1
T (3) = 1
T (n)=2T (.n/4.)+ n
Please prove that T (n) c n log n for some c using induction. You should give a lower bound for c.
Solution:
base cases:
n =1: T (1) = 0 c 0 for any c
n =2: T (2) = 1 c 2 log 2 for c 1/2 log 2
n =3: T (3) = 1 c 3 log 3 for c 1/ 3 log 3
induction:
T (n)=2T (.n/4.)+ n
. 2c .n/4. log .n/4. + n
. 2c n/4 log n/4+ n
= cn log n . c log 4 n + n
cn log n for c 1/2 log 2
therefore, T (n) c n log n for c 1/ 2 log 2.
2. Problem Solving (10 points total)
Suppose you are given an array A with n entries, with each entry holding a distinct number. You are told that the sequence of values A[1],A[2],...,A[n] is unimodal: For some index p between 1 and n, the values in the array entries increase up to position p in A and then decrease the remainder of the way until position n. (So if you were to draw a plot with the array position j on the x-axis and the value of the entry A[j] on the y-axis, the plotted points would rise until x-value p, where theyd achieve their maximum, and then fall from there on.)
(a)
Please describe an algorithm on how to .nd the peak entry p in O(logn) time. (6 points)
(b)
Please prove its time complexity. (4 points)
Solution:
The algorithm is similar to binary search. We could probe the midpoint of the array and try
to determine whether the peak entry p lies before or after this midpoint.
From the value A[n/2] alone, we cannot tell whether p lies before or after n/2, since we need
to know whether entry n/2 is sitting on an up-slope or on a down-slope. So we also look
at the values A[n/2 . 1] and A[n/2 + 1]. There are three possibilities:
1).If A[n/2 . 1] <A[n/2] <A[n/2+ 1], then entry n/2 must come strictly before p, and
so we can continue recursively on entries n/2+1 through n.