=========================preview======================
(COMP171)midterm2006fall_solution.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 7, 2006

Question Marks
1 /12
2 /8
3 /25
4 /7
5 /15
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)?

Answer: 1111

(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);

}
}

Answer: The recursive function will never converge to the base case (ie. num1) as the value passed to the function is always increasing (ie. 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));

}
Answer:
int fib(int n) {
int f[n+1];
f[0] =0;f[1] =1;

for (int i=2; i<= n; i++)
f[i] = f[i-1] + f[i-2];
return f[n];
}

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}.

{142, 543, 123, 65, 453, 879, 572, 434} || {142, 543, 123, 65} {453,879, 572, 434}
|| || {142, 543} {123, 65} {453, 879} {572, 434} || |||| ||
{142} {543} {123} {65} {453} {879} {572} {434} || |||| || {142, 543} {65, 123} {453, 879} {434,572} || || {65, 123, 142, 543} {434, 453, 572, 879}
|| {65, 123, 142, 434, 453, 543, 572, 879}
(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:the element always gets inserted at the front, so
all the sorted elements must be moved at each insertion. The
ith insertion requires (i-1) comparisons and moves.
sorting in ascending order: {879, 572, 543, 453, 434, 142, 123,
65 }
sorting in descending order: {65, 123, 142, 434, 453, 543, 572,
879 }

Best Case: the element always gets inserted at the end, so we
dont have to move anything, and only compare against the last
sorted element. We have (n-1) insertions, each with exactly one
comparison and no data moves per insertion.
sorting in ascending order: {65, 123, 142, 434, 453, 543, 572,
879 }
sorting in descending order: {879, 572, 543, 453, 434, 142, 123,
65 }

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