=========================preview======================
(COMP171)midterm2006fall (1).pdf
Back to COMP171 Login to download
======================================================
COMP171 Data Structures and
Algorithms
Fall 2006

Midterm Examination

L1: Dr Qiang Yang
L2: Dr Lei Chen

Date: 6 Nov 2006
Time: 6-8p.m.
Venue: LTA

November 2, 2006

Question Marks
1 /12
2 /8
3 /25
4 /5
5 /17
6 /15
7 /18
Total /100

1. (12 marks) Recursion
Consider the following recursive program.
//n is any positive integer
//m is a positive integer between 2 and 9
void fun(int n, int m)

{
if (n<m)
cout << n;
else {
fun(n/m, m);
cout << n%m;
}
}

(a)
(3 marks) What is the output for fun(15, 2)?

(b)
(3 marks) Given the following recursive code. Point out the possible errors in the code.


//num is a positive integer
int fac(int num)
{
if (num1)
return 1;
else {return num*fac(num+1);
}
}

(c) (6 marks) Given the following function which computes .-bonacci numbers using recursive function, write a non-recursive version of function fib.
//num is a positive integer int .b(int num)
{
if (num==0) return 0;
if (num==1) return 1;
return (.b(num . 1)+.b(num . 2));

}
2. (8 marks) Merge Sort and Insertion Sort
(a)
(4 marks) Draw a binary tree to show step by step how Merge Sort sorts {142, 543, 123, 65, 453, 879, 572, 434}.

(b)
(4 marks) Show under what order of input, the insertion sort will have worst-case and best-case situations for sorting the set {142, 543, 123, 65, 453, 879, 572, 434 }.


Worst Case:
Best Case:
4
3. Big-Oh
(a) What is the time complexity of the equation T(n) given below?Please give the tightest possible bound in big-Oh notation. Assume n is a power of 2 (that is n =2k for some k).
. T (n)=2T (n/2) + n log n T (1) = 1
Results without derivations do not receive any points.
(b) Give a tightest possible bound for the Big-Oh runtime com-plexity of the following function in terms of the value of the input parameter n. Results without derivations do not receive any points. (Hint: The complexity of easy(n) is T (n).)
1 int easy(int n){
2 int a, b, c;
3 if(n<=1)
4 return 0;
5 else {
6 a = easy(n-1);
7 b = easy(n % 2);
8 c = easy(n-2)/2;
9 returna+b+c;
10 }
11 }

(c) Multiple Choice: Circle the best answer for each question. If you circle two answers, you will receive zero for that question.

. T (n)= T ( 3 n)+1 n> 2
i. The recurrence
T (n)=1 n 2 solves to:
A. O(n)

B. O( n)
C. O(log n)
D. O(log log n)
E. O(log log log n)
F. O(1)
ii. If f(n)= n + n log n,which of the following is/are true? 1) O(n) 2) O(n2) 3) (n2) 4) (n log n) 5) (n log n) 6) (n)
A. 1) only.
B. 1) & 6).
C. 2) only.
D. 2) & 3).
E. 2) & 4) & 5).
F. 4) & 5).
G. 2) & 3) & 4) & 5).
4. In the following code for a stack machine, PUSH X means push X onto the stack, POP X means pop the top of the stack into X, and an operator without an operand (ADD, MULT) means pop the top two items o. the stack, perform the indicated operation on them, and push the result bac