=========================preview======================
(COMP271)2007_s_COMP271_by_cs_ywc166.pdf
Back to COMP271 Login to download
======================================================
THE HONG KONG UNIVERSITY OF SCIENCE & TECHNOLOGY
COMP 271 Design and Analysis of Algorithms
Spring 2007
Midterm Examination
7:00pm C 9:00pm, Thursday, 29 March, 2007

Name: Student No:
Department: Tutorial Section:
This is a closed book exam. You should put everything o. your desk except for stationaries and your student ID. You wont need a calculator.
There are six questions. You need to answer all questions in 120 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 and dont use pencils for your .nal answers.
When describing algorithms, you can use either natural language or pseudo code as long as your descriptions are clear.

Question
Grade



1
2
3
4
5
6
Total


1. Partition&SelectionProblems(20Points)
(a) Given a sorted array A[1..n]of n distinctintegers(positive or negative)give a O(lgn)-algorithm that .nds the index i such that A[i]= i, if such an index exists. (10 points)
The algorithm starts from the middle of the array A. If A[mid]= mid, we found it and return YES. If not, check if A[mid] > mid. If A[mid] is greater, then we can con.dently ignore all the values greater than (and including) the mid point; as all array elements are distinct and sorted, .j mid,A[j] (A[mid]+j.mid) j. Similarly, if A[mid]is smaller,then we canignore all the values smallerthan(andincluding) the mid point. This goes on until we either .nd a match or the array size become zero. Since we throw away half of the input array at each iteration, the time complexity is O(lgn).
(b) Give a linear time algorithm which, given a list A[1..n]of distinct numbers, a positive integer k (1 k n)and number X, outputs the k numbers of A that are closest to X in value. (These numbers may be greater than, less than, or equal to X.) (10 points)
.i,A [i]= |A[i]. X|; the smaller the A [i], the closer the distance between A[i] and
X. Now, we can apply DSelection(A ,1,n,k) to .nd the k smallest in A .
At the end, lookup the corresponding indices in the array A for these k smallestitems
in the array A , we .nd the numbers that are closest to X.
Thetimecomplexity to solvethisproblemequalstothat of running DSelection, hence
it is O(n).

2. (10 points) Consider the adjacency matrix given in the table. The graph represents a road network connecting asetof sixtownswheredistancesaregiveninmiles. UseKruskalsalgorithmto .nd aroad network of minimal totallength connecting all thetowns(Nocredit withoutshowing necessary steps).
a b c d e f
abcde f 03 22 3 0 14 2 1 03 1 2 4 301 4 2 10
2 14 0
Sort the edgesin ascending order of thedistance: (b,c),(c,f),(d,e),(a,d),(a,e),(b,f),(a,b),(c,d),(b,d) step1: add (b,c) to A as it does not create cycle
step2: add (c,f) to A as it does not create cycle
step3: add (d,e) to A as it does not create cycle
s