=========================preview======================
(COMP271)2003Spring_Final_SOL.pdf
Back to COMP271 Login to download
======================================================
COMP 271: Final Exam
2003 Spring Semester
27 May 2003
8:30 am C 11:30 am
solution sketches

You have 3 hours to solve the 6 problems for a total of 100 marks. Answer all problems in the space provided. You may also use the back of the test papers. Good
luck!
Student name:
Problem
1
2
3
4
5
6
Total

Your mark

Student ID:
Maximum
15
15
20
20
10
20
100

Problem 1. (15 points) For n>0, let T(n) be de.ned by
1 if n=1
T(n)=
5T n + n if n>1.
4
Give an asymptotic upper bound for T(n). Make your bound as tight as possible. For the sake of this problem you may assume that nis always a power of 4.
log4 5 5log4 n
The solution is Onor, equivalently O.
Problem 2. (15 points) Recall the selection problem. Given an array of numbers [a1,...,an], and an integer i,1 i n, .nd the ith smallest element. When i = n/2,thisiscalled the median problem.
Example: given [1, 8, 23, 10, 19, 33, 100], the 3rd smallest element is 10. In this case n =7 so n/2= 4 and the median is 19.
Now assume that you are given a black-box worst-case linear-time median-.nding algorithm. That is, you are given a procedure X( ) that takes as input an array A[] with n elements and, in O(n) time, returns the value of the median element in A.
(a)
Using X( ) as a subroutine design a a linear time algorithm that solves the selection problem for an arbitrary i. That is given input array A[] with n elements and input integer i your algorithm should .nd the ith smallest item in the array in O(n) time. For the sake of this problem you may, if you like, assume that all elements in A[ ] are unique.

(b)
Prove that your algorithm runs in O(n)time.

(c)
Argue the correctness of your algorithm.


This was problem 3 from Tutorial 2.
There are at least two very di.erent solutions for this problem. The .rst one is a straightforward divide-and-conquer, the second a clever transformation. We will see both.
I) Solution 1.
nif(i == 2
Let Select(A, n, i) be the procedure that we want to construct. A is an array, n is the size of the array and we want to .nd the ith largest item in A.
Select(A, n, i)
{ med = X(A); O(n) time to .nd median of A


return(med)

Create a matrix B[ ] containing O(n)time tocreate

.1elements of A[]

that are <med.

.1,i)
else


Create a matrix B[ ] containing O(n)time tocreate

elements of A[]

that are >med.


}
Note that this algorithm will always terminate since, in each recursive call, the value of n decreases and no recursion call is made with n< 1 (verify this.
The correctness of this algorithm follows from the fact that there are only three possibilities
. i ==
n 2
: In this case we are looking for the median and get the

correct answer via X().

. i<
n 2
: In this case the ith smallest item in A is also the ith smallest
item in {x, : x A and x<med}which is the set contained in B.
. i>
n 2
: In this case the ith smallest item in A