=========================preview======================
(COMP271)2007Fall_Midterm_SOL.pdf
Back to COMP271 Login to download
======================================================
THE HONG KONG UNIVERSITY OF SCIENCE & TECHNOLOGY
COMP 271 Design and Analysis of Algorithms
Fall 2007
Midterm Examination
2:00pm C 5:00pm, Saturday, 20 October 2007

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 are two blank pages at the end in case you need more space. Write legibly.

Question
Grade



1
2
3
4
5
6
6
7
Total


1. (7 Points) What is the running time of Randomized-Quicksort on an array of N equal elements? Explain your answer.
Solution:
ConsiderrunningRandomized-Quicksort onanarray. It .rstrandomlypicksapivotelementand then partitions the array according to the pivot: (1). the LessEqual subarray contains elements less than orequal tothepivot;(2). the Greater subarray contains elementsgreater than thepivot. Recursively run Randomize-Quicksort on both subarrays.
Inthespecial case,all theN elementscontainedinthearray areequal. Therefore,every timepartition is done, the LessEqual subarray contains all elements except the pivot while the the Greater subarray contains no element.(5 points so far)
SupposeT (N)is the runningtime onthe specialarray of size N. Wehave,(2pointsfor thederivation)
T (N)= T (0)+T (N .1)+(N) = T (0)+[T (0)+T (N .2)+(N .1)]+(N) =2T (0)+T (N .2)+((N .1)+(N)) = = NT (0)+T (0)+((1)+ +(N .1)+(N)) = (N2)
Q.E.D.
2. (13 Points) Consider running Randomized-Select on an array of N distinct elements. Whatistheprobability that thelargestelementiscompared withthesmallestelementatleastonce?Explainyouranswer.
Solution: Consider the .rst step. In Randomized-Partition, the pivot can be any elements in the array with equal probability.
.
When pivot is the smallest elements, i.e. Min, the two elements Max and Min are compared with each other in Randomized-Partition.(P robability of this case =1/N.) (2+1 points)

.
Whenpivotis the largestelements, i.e. Max, the two elements Max and Min are compared with each other in Randomized-Partition.(P robability of this case =1/N.) (2+1 points)

.
When the pivot is neither Max nor Min, the two elements are never compared with each other (2 points for mentioning the fact). The reason is that (1) They are not compared in Randomized-Partition at the .rst step. (2)Max and Min are in di.erent paritions. Therefore they are never compared with each other after the .rst step. (4 points for the explanation)


In summary, Max and Min are compared with each other in two of all the N cases. The probability is then 2 .(1 point)
N

3. (15 Points) LetA[]be an arrayofdistinctintegers. A subarray A[i..j]ismonotonically increasing ifA[i]<A[i+1] < ... < A[j]. The length of the subarrayisde.ned tobe j .i +1. Design an e