=========================preview======================
(COMP171)[2007](s)final~cs_ymy^_10168.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 2007
Solution
Finalterm Examination Marking Scheme

Instructors
L1: Albert C. S. CHUNG
L2: Long QUAN
L3: Huamin QU

Date: Monday, May 28th, 2007
Time: 12:30pm C 3:30pm
Venue: Sports Hall

Your answers will be graded according to correctness, efficiency, precision and clarity.
This is a closed books, closed notes examination.
You should put aside your cell phones, PDAs, etc.
This booklet has 17 pages, you should check it carefully.


Student Name: _________________ Student ID: _________________
Email Address: _________________ Tutorial Session: _________________

I did not cheat in this examination: _________________ (Signature)

Problem
Marks
Maximum

1

10

2

10

3

15

4

10

5

5

6

15

7

10

8

25 ()()()()1,21,2TnOnTnOn.+>.=...()()1,21,2TnnTnn.+>.=...2kna='na=()1O2loglogakn=()loglogOn'vG'vG()ureverseAdjv





Total

100





1. Analysis of Algorithms (10 marks)

Consider the following recursive algorithm Fun():

double Fun(double n) {
double i, j;
if (n<=2) {
return n;
}
else {
i = 10*Fun(sqrt(n));
j = Fun(n % 2);
return (i + j);
}
}

We assume that , where k is a positive integer and . The function sqrt(n) returns the square root of n, and has a constant time complexity, i.e. O(1).

a.
Let T(n) be the time complexity of Fun, derive the recurrence formula for T(n). Include the boundary conditions for T(n) as well.




Solution (5 marks):

Or




b.
What is the time complexity of the function Fun()? Give the tightest possible upper bound in big-Oh notation. The bound is expressed in terms of n only.




Solution (5 marks):
Let . The recurrence will stop at some and take k steps. Each step takes constant time , and , so the time complexity is .
2. Sorting (10 marks)

Given an input array of numbers, implement the InsertionSort algorithm using TWO stacks. The sorted result should be stored in one stack with the maximum of the numbers on the stack top and the minimum at the stack bottom.

A Stack data structure supports the following four operations:
1) v1 = pop(S1): pop off the top element of the stack S1 and assign that element to v1;
2) v1 = top(S1): assign only the top of the stack S1 to v1 (without popping);
3) push (S1, v1): push the number v1 onto the top of the stack S1;
4) empty(S1): return true if the stack S1 is empty, false otherwise.
Note that the input array is READ-ONLY and you CANNOT use any other data structures to store the temporary/final results exc