=========================preview======================
(COMP171)comp171-midterm-spring-2008-with-answers-v1.pdf
Back to COMP171 Login to download
======================================================
THE HONG KONG UNIVERSITY OF SCIENCE & TECHNOLOGY
Department of Computer Science and Engineering

COMP171: Data Structures and Algorithms
Spring 2008

Midterm Examination

Instructors
L1: Albert C. S. CHUNG
L2: Bo LI
L3: Zhen ZHOU

Date: 8 April, 2008
Time: 19:00 C 21:00


Student Name: _________________ Student ID: _________________

Email Address: _________________ Lecture Session: _________________


Question
Marks


1


/25


2


/25


3

/25


4


/25






Total


/100




Question 1 Analysis of Algorithm (25 marks)

Suppose A[0 ... (n-1)] is an array of n integers. Consider the following recursive function performed on A:

int fun(int A[], int p, int q, int r ){
if (p >= q) 1 9 2 4 8 6 7 1 9 2 4 8 6 7 5 1 9 2 5 8 6 7 1 9 2 6 8 7 5 1 8 2 5 9 6 7 2 8 2 1 8 2 1 8 9 2 1 9 108 8 2 9 107 1 8 2 9 107 1 6 8 2 9 106 1 3 7 178 5281121 11 3 2126178 2681121 11 3 21218 2681121 11 3 128 2681111 3
return p;
else {
int m = (p+q)/2;
int i = fun(A, p, m, r);
int j = fun(A, m+1, q, r);

if ((A[i]-r)*(A[i]-r) < (A[j]-r)*(A[j]-r))
return i;
else return j;
}
}

(a) (3 marks) Suppose A = {30, -15, -19, 50, 3, 81, 66, 48, 31, -7, 5, 6, -1}. What is the returned value of fun(A, 0, 12, 10)?

Ans: 11

(b) (3 marks) What is the purpose of the function fun(A, 0, n-1, x)?

Ans: It returns the array index of the element in array A that is closest to x.

(c) (8 marks) Let T(n) be the time to execute fun(A, 0, n-1, x).
Write down the recursive formula for T(n) in Big-Oh. Please also state the running time of the boundary condition for n = 1 in Big-Oh. Then analyze the running time of the function in terms of Big-Oh using the recursive formula.
Ans:


Let n = 2k, then



Consider another recursive function also performed on A:

int foo(int A[], int p, int q, int r ){
if (p >= q)
return p;
else {
int m = (q-p)/3;
int i = foo(A, p, p+m, r);
int j = foo(A, p+m+1, p+m+m, r);
int k = foo(A, p+m+m+1, q, r);

if ((A[i]-r)*(A[i]-r) < (A[j]-r)*(A[j]-r))
if ((A[k]-r)*(A[k]-r) < (A[i]-r)*(A[i]-r))
return k;
else return i;
else return j;
}
}

(d) (3 marks) What is the purpose of the function foo(A, 0, n-1, x)?

Ans: Same as fun(A, 0, n-1, x).
It returns the array index of the element in array A that is closest to x.

(e) (8 marks) Let T(n) be the time to execute foo(A, 0, n-1, x).
Write down the recursive formula for T(n) in Big-Oh.
Please also state the running time of the boundary condition for n = 1 in Big-Oh.
Then analyze the running time of the function in terms of Big-Oh using the recursive formula.

Ans:




Let n = 3k, then




Question 2 Heapsort (25 marks)

(a) S