=========================preview======================
(COMP171)[2008](s)final~cs_ymy^_10169.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
Solution
Final Examination
Time: 28 May, 2008, 16:30 C 19:30

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

1. This is a closed-book, closed-notes examination.
2. Before starting, first check that you have all 18 pages (including this cover page).
3. Write your name and student ID on this page above.
4. Answer all questions in the space provided.


Student Name: _________________ Student ID: _________________

Email Address: _________________ Lecture Session: _________________


Question
Marks
1
/10
2
/10
3
/10
4
/15
5
/15
6
/15
7
/10
8
/15



Total


/100
Question 1 Analysis of algorithms (10 marks)

a) Rank the following twelve functions in their increasing order of growth rate.
Write them down on the lines provided below, where the slowest-growing function will be placed on the first line, and so on so forth. If two functions are having the same growth rate, then they should be placed on the same line.

32528 38 41 1417 3717 25 30 17 1121 3BFS and D is bina tre whrunng Ber l
Answer:











b) Suppose T(0) = T(1) = 1 and n 2. Which of the following recurrence function T(.) CANNOT be upper-bounded by a polynomial function of n? (Note: there may be more than one choice. Each incorrect answer will receive deducted marks.)


Answer:





c) Given the following function:

int Fun( int n )
{
if((n==0) || (n==1)) { return 1; }

else { return 2 * Fun(n-2) + 1; }
}

Derive the time complexity T(n) of executing Fun(n) in Big.. form, assuming that n is a non-negative even number. Answer without derivation receives no mark.

Answer:

T(n) = T(n-2) + c
= T(n-4) + 2c
:
:
= T(0) + (n/2)c
= .(n)








Question 2 Sorting (10 marks)

a) Give the tightest bounds on the worst case running time of the following sorting algorithms in Big-O notation, assuming that the input size is n.

Algorithm
Running Time (worst)
Insertion Sort
O(n2)
Merge Sort
O(nlogn)
Heap Sort
O(nlogn)
Quick Sort
O(n2)

b) What is the minimum number of comparisons needed to guarantee to sort any 5 elements?
Answer:
ceiling(log2(5!)) = 7

c) In a Quicksort implementation, suppose that we always select the left-most element of the array as the pivot.
i) In ONE sentence, state under which condition the best case of Quicksort occurs?
Answer:
Each partition is balanced. / Pivot selected is always median of sorting array.

ii) Analyze the time complexity of the best case of Quicksort. Show all steps.
Answer:



Let c be a constant,


Question 3 Trees