=========================preview======================
(COMP271)2000Spring_Midterm_SOL.pdf
Back to COMP271 Login to download
======================================================
The Hong Kong University of Science & Technology
Department of Computer Science

COMP271: Design & Analysis of Algorithms
Spring 2000


Mid-term Examination

Date: 18:00-20:00pm, April 20, 2000
Room 2302

Problem 1
Please justify if the following statements are true. You need not to give the reasons.
3 32
(1) If f1 = ( n + 3) , f 2 = 2 n + n log n , then f1 = ( f 2) , f = ( f 2 ) and f1 = ( f 2
1)
Answer:True
(2)
We can sort any six integers by 9 comparisons.

Answer:False A decision tree of 9 comparisons can only distinguish at most 512 kinds of permutation of six integers, but the number of possible permutation is 6!=720, so we cant sort them by only 9 comparisons.

(3)
A graph may have many minimum spanning trees. Answer: True



Problem 2
(a) Explain why we can not use master method to solve recurrence equation T ( n ) = 2T ( n / 2) + n log n
Answer:
log ba
In master method, for this case, n is n, f(n) is nlogn, Obviously we can not apply case 1 and case 2 on it.
1 +
If we apply case 3, we need to find an > 0, let n log n = ( n ),
thats impossible.
So we cant apply any of the three cases, thus cant use master method on the recurrence
equation.

(b) Solve the following recurrence equation: .1, if n = 1,2
T ( n ) =.
3T ( n / 3) + n , if n > 2
.
You can use any method you wish.
Answer:
log ba
Use master method, n is n, f(n) is n, there are the same, so we can apply case 2 on it, and directly get the answer T (n) =(nlog n). We can also use iteration method, the result is the same. But some students get a result as T (n) =(n + nlog n), or ( n log 3 n ) , in fact, thats just T (n) =(nlog n).
Problem 3
MAXMIN problem is to find the maximum element and the minimum element from n integers. The following is the pseudo code for the MAXMIN problem by using the divide & conquer method. Please evaluate the time complexity of this algorithm.
MAXMIN(L, max, min)
If |L|=1 then begin max:= the only element in L; min:=max;
end
else begin divide L into two parts L1 and L2 in the middle; MAXMIN(L1,max1, min1); MAXMIN(L1,max2, min2); max:=max(max1,max2); min:=min(min1,min2);
end;
Answer:
In the pseudo code, all codes except the recursive function call cost only constant time, So we can built a recurrence equation as T(n)=2T(n/2)+O(1). Use master method, n log ba is n, f(n) is O(1), so we can apply case 1, the result is O(n).
Problem 4 The following pseudo code outputs the prefix expression of the expression represented by syntax tree G. Revise the code to transform the output sequence to the infix expression. Note that in infix expression, we need add brackets in the expression, while in postfix and prefix expression we do not need add brackets. A sample output of infix expression is (3+((5-3)*(4-2)).
Prefix(G, u){ Output the symbol stored in u; if ( left_child(u) != NIL )
Prefix(G, left_child(u) ); if ( right_child(u) != NIL ) Prefix(G, ri