Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
EL9343 Midterm Exam Solutions
2.5 hours exam; Write all answers in the white space provided under each question, write on the
back of the page if you need more space
1. (8 points) True or False
(a) (2 points) T or F f(n) + g(n) = O(min{f(n), g(n)});
(b) (2 points) T or F log n! = Ω(log nn);
(c) (2 points) T or F Randomized quick-sort has lower worst-case running time than quick-sort;
(d) (2 points) T or F For any array with n elements, one can always find the i-th smallest element
within O(n) time.
2. (6 points) Consider the following sorting algorithms:
A: InsertionSort; B: MergeSort; C: QuickSort; D: HeapSort.
(a) (2 points) Which of the above sorting algorithms run in worst-case time O(n log n)?
Circle all that apply: A B C D None
(b) (2 points) Which of the above sorting algorithms can run even better than O(n log n) in the best case?
Circle all that apply: A B C D None
(c) (2 points) Which of the above sorting algorithms are stable?
Circle all that apply: A B C D None
3. (6 points) Consider the following trees:
5
3
2 4
8
6
Tree A
28
32
30
Tree B
15
5 10
Tree C
(a) (2 points) Which are binary search trees?
Circle all that apply: A B C None
(b) (2 points) Which are the first three items in a post-order traversal of tree A?
Circle one: 2,3,4 5,3,8 2,3,5 5,3,2 2,4,3 2,4,6 None
(c) (2 points) Which are max heaps?
Circle all that apply: A B C None
1
4. (12 points) Solve the following recurrences:
(a) (4 points) Use the iteration method to solve T (n) = 12 (T (αn) + T (βn)) + n, 0.5 < α, β < 1;
(b) (4 points) Use the substitution method to verify your solution for Question 4a.
(c) (4 points) Solve the recurrence T (n) = 4T (n/2) + n2.5 using master method.
Answer:
n
1
2αn
1
4α
2n 14αβn
1
2βn
1
4βαn
1
4β
2n
(a)For the kth level, the computation would be (12(α + β))
kn, with summation formula of geometric pro-
gression,
∑inf
k=0(
1
2(α+ β))
kn = 1
1−α+β
2
= 22−α−βn, since 0.5 < α, β < 1, T (n) = O(n), Recursion Tree (2 pt),
correct T(n) (2 pt)
(b)Suppose T (n) = cn+ b, we substitute T(n) in the original equation, we can get
T (n) =
1
2
(cαn+ b+ cβn+ b) + n
= (
1
2
cα+
1
2
cβ + 1)n+ b
≤ cn+ b
= O(n)
which proves that T(n) = O(n)
(c) As we can see in the formula above, a = 4, b = 2, logba = 2 and f(n) = n
2.5, which is the case 3 of
Master theorem, then we can say T (n) = O(n2.5)