=========================preview======================
(COMP171)cs171mdf03.pdf
Back to COMP171 Login to download
======================================================
THE HONG KONG UNIVERSITY OF SCIENCE & TECHNOLOGY
Department of Computer Science

COMP171: Data Structures and Algorithms
Fall 2003

Midterm Examination


Date: October 16th, 2003 Time: 7:00 C 8:30pm
Place: Rm 2407



. Your answers will be graded according to correctness, efficiency, precision and clarity.

. This is a closed book examination. You should put aside your calculators, mobile phones, PDAs, etc.

. This booklet has 11 singled-sided pages. Please check it.

. You may use the reverse side of the pages for your rough work.










Student name: KEY Student ID:


Students email address:


Tutorial Session: T1 Wed (Skiller) T2 Fri (Calvin)



Question
Score
Maximum Score

1

5

2

10

3

10

4

10

5

15

6

10

TOTAL

60



1. (5 marks)


Consider the following functions and loops.

int algorithm1(int n)
{
int sum = 0;
for(int i=0; i < n*n; i++)
for(int j=1; j < 3; j++)
sum++;

return sum;
}

int algorithm2(int n)
{
int sum = 0;
for(int i=0; i < n/2; i++)
sum++;

return sum;
}


int algorithm3(int n)
{
int sum = 0;
for(int i=n; i >= 2; i = i/2)
sum += algorithm2(i);

return sum;
}

int algorithm4(int n)
{
int sum=0;
for(int i=n; i >= 2; i=i/2)
sum += algorithm1(n);
}




Algorithm1() -> O(n2)
Algorithm2() -> O(n)
Algorithm3() -> O(nlogn)
Algorithm4() -> O(n2logn)

Give running time in Big Oh(..)? (1 mark each)

(a) int sum = algorithm4(n);

O(n2logn)

(b) int sum =0; for(int i=0; i < n; i++) algorithm3(i);


O(n2logn)


(c) int sum =0;
for(int i=0; i < 30; i++) for(int j=0; j < i; j++) for(int s=0; s < j; s++) for(int t=0; t < n; t++) sum++;

O(n)


(d) int sum=0; for(int i=1; i < n; i = i*2)
algorithm1(2);

O(logn)

(e) int sum=0; for(int i=0; i < n; i++)
{
sum += algorithm1(i);
sum += algorithm2(i);
}
O(n3)




2. (10 marks) HEAPS
(a) (5 marks) Using the following numbers, construct a valid max-heap in tree-format (i.e. draw the tree with the data in the nodes. Note, there is not a unique solution, but your result must be a valid max-heap).



14, 15, 8, 5, 19, 20, 12, 23, 2








(b) (5 marks) Given the following min-heap of size 10 (in array form):



0
1
2
3
4
5
6
7
8
9

5
10
15
12
13
37
16
18
14
19



Delete the minimum node and give the resulting min-heap:

0
1
2
3
4
5
6
7
8

10
12
15
14
13
37
16
18
19



3. (10 marks) Recursion


Consider the following recursive program.

// n is any positive integer