=========================preview======================
(COMP271)2006Fall_Midterm_SOL.pdf
Back to COMP271 Login to download
======================================================
THE HONG KONG UNIVERSITY OF SCIENCE & TECHNOLOGY
COMP 271 Design and Analysis of Algorithms
Fall 2006
Midterm Examination
6:00pm C 9:00pm, Thursday, 26 October 2006

Name: Student No:
Department: Tutorial Section:
This is a closed book exam. You should put everything o. your desk except for stationeries and your student ID.
There are 7 questions. You need to answer all questions in 180 minutes. You should use the back of the pages for rough work and, if necessary, for your .nal answers. There is one blank page at the end in case you need more space. Write legibly.
Question Grade
1 2 3 4 5 6 6 7 Total
1. (20 Points: 5 points for eachsub-question) What are the input and output of each of the following algorithms? What are their worst-case and average-case running times?
(a)
The divide-and-conquer algorithm for MCS.

(b)
Randomized-Select.

(c)
DFS.

(d)
Prims Algorithm.


Algorithm Input (1 point)
MCS An array A[1. . . N]
RS DFS An arrayA[1. . . N]and an integer i where 1 i N An graph G=(V,E)
Prims A connected and weighted undirected graph G=(V,E) and w is a real-valued weight function de.ned on E

Output(2 points)
maximum continuous sub-array of A the i-th smallest element in the array The time stamp arrays: d[v],f[v];Thepredecessor array pred[v] A minimum spanning tree of G
Worst case (1 point) O(N logN) Average case (1 point) O(N logN)
(N2) (N)
(|V|+ |E|) (|V|+ |E|)
O(|E|log|V|) O(|E|log|V|)

2. (5 Points)

Consider two complex numbers a +bi and c +di where i = .1. How to compute their product with only 3 numerical multiplications? (Note that there is no requirement on the number of additions and subtractions.)
Solution:
Since(a +bi)(c +di)=(ac .bd)+(ad +bc)i, what we really needed are(1) ac .bd and(2) ad +bc (2 points). These two terms can be computed from the following numerical multiplications: (3 points)
.
X =(a + b)(c + d)= ac +(ad + bc)+bd

.
Y = ac


. Z = bd
Therefore

.
ac .bd = Y .Z

.
ad + bc = X .Y .Z


3. (10 Points) Consider running DSelection on the following sequence of numbers. Which number is selected as the pivotinthe .rstpass?Justifyyouranswer.
8 9 10 14 3 20 15 12 11 7 5 16 4 25 2 19 14 17 6 18 22 13 1 23 26 21
Solution: (3 points for the idea.)
. (2 points)Divide the 26 items into .26 . sets in which each, except the last, contains 5 items.
5
8 9 10 14 3 20 15 12 11 7 5 16 4 25 2 19 14 17 6 18
. (3 points)Find the median of each of the .26 . sets
5
22 21 13
1 23 26

8 9 10 14 3 20 15 12 11 7 16 4 25 2 19 14 17 6 18

22 21 13
1 23 26
These medians are 9, 12, 5, 17, 22, 21.
. (2points)Themedianof thesemediansis12 whichisthepivotinthe .rstpass.
4. (20 Points) Supposeyou aregiven a sorted array A of n numbers thathas been circularly shifted k positions to the right. For example, {5,6,1,2,3,4}is a sorted array that has been circularly shifted k = 2 positions, wh