=========================preview======================
(COMP271)[2010](f)final~=2u622^_56845.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 15 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.
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)


3. Topological Sort (10 points total)
Find the topological ordering of the following directed graph. Please show the status of the queue at each iteration.

4. Minimum Spanning Tree (15 points total)
(a)
If the weights of all edges in a graph are identical, is it possible to .nd a minimum spanning tree in linear time O(|V | + |E|)? If yes, please describe your algorithm. (5 points)

(b)
Find the minimum spanning tree of the following graph using either Prims algorithm or Krushkals algorithm. To get the full marks, please either label the edges of minimum spanning trees in the order they are added to the minimum spanning trees (i.e, put label 1 near the .rst edge added and 2 near the second edge added, and so on) or show the edges that are added in each iteration. (10 points)



5. Shortest Path (10 points total)
The following graph has three shortest paths from C to E (i.e., all with the same total weight).


(a)
Find the three paths and list the sequences of vertices in each p