EL9343 Midterm Exam Solutions (Fall, 2016)
Name: ID: Session: Online or In-Person
March 15, 2021
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)
5. (11 points) For an unsorted array of [19, 13, 8, 26, 12, 7, 6, 25, 16, 30, 11],
(a) (5 points) If heap-sort is applied, plot the initial max-heap built from the array
Answer: Max-heap array is [30, 26, 8, 25, 13, 7, 6, 19, 16, 12, 11]
(b) (3 points) If quick-sort with Hoare’s partition is applied, show the result of the first partition call
Answer: Pivot= 19, [11, 13, 8, 16, 12, 7, 6, 25, 26, 30, 19], iterators: j = 7 and i = 8
(c) (3 points) If quick-sort with Lomuto’s partition is applied, show the result of the first partition call
Answer: Pivot= 11, [8, 7, 6, 11, 12, 13, 19, 25, 16, 30, 26], iterator: i = 4
6. (13 points) Design an iterative algorithm to find the k-th smallest element in an array of n distinct elements
(k is a given constant, does not grow with n) with worst-case running time of O(n), you are not allowed to
use partition and recursive call,
2
(a) (8 points) write down the pseudo-code of your algorithm
Answer: Since k = O(1), possible solutions include but are not limited to:
i. pass through the whole array once, maintain a set of the k smallest elements seen so far
ii. Use selection sort or bubble sort, but stop at the kth iteration of the outer loop: O(kn) = O(n)
iii. Create min-heap from all elements and extract the min value k times: O(n+ k log n) = O(n)
(b) (5 points) what is the maximum number of comparisons your algorithm will make (exact number, not
just in the asymptotic sense), under what situation it will happen?
Answer: For (i), the worst case is that each new element has to be compared with all k smallest
elements, so (n− k)k.
For (ii), there will be exactly n− 1 + · · ·+n− k = kn− k(k+ 1)/2 comparisons regardless of the initial
array (selection sort and bubble sort have this problem in general).
7. (13 points) For Radix sort:
(a) (8 points) prove that it is correct;
(b) (5 points) prove or disprove that it is stable.
Answer:
(a) (8 points) if x = x1x2 · · ·xb > y = y1y2 · · · yb, let j be the first bit where xj > yj (automatically
xi = yi, ∀1 ≤ i < j), then when Radix sort works on bit j, x will be placed after y; since xi = yi,
∀1 ≤ i < j, and sorting algorithm for each bit is stable, then the relative position of x and y won’t
change for the rest of operations (bits j − 1 to 1), so x and y finishes with the right ordering.
(b) (5 points) if x = x1x2 · · ·xb = y = y1y2 · · · yb, and x is in front of y before sorting, when we sort each
bit, x will be always in front of y (stable sort), so x is still in front of y after sorting.
8. (11 points) An array of n distinct keys were inserted into a hash table of size m sequentially over n time
slots, suppose chaining was used to resolve collisions, let Xk be the random variable of the number of elements
examined when searching for the k-th inserted key (the key inserted in the k-th time slot, 1 ≤ k ≤ n),
(a) (5 points) what is the probability mass function of Xk, i.e., calculate P (Xk = i), i ≥ 0?
(b) (3 points) what is the expected value of Xk?
(c) (3 points) what is the expected number of elements examined when searching for a key randomly
selected from the array?
Answer:
(a) There were n − k keys inserted after the k-th key, each of them has a probability of 1/m (1pt) to be
inserted into the same chain as the k-th key. Let Yk be the number of keys positioned before the k-th key
in its chain, it is a Bernoulli trial of n − k experiments, and success probability of each trial is 1/m, so Yk
follows a binomial distribution of (n− k, 1m), and Xk = Yk + 1, the p.m.f. of Yk is
P (Yk = i) =
(
n− k
i
)
1
mi
(
1− 1
m
)n−k−i
, n− k ≥ i ≥ 0(2pt)
The p.m.f of Xk
P (Xk = i) = P (Yk = i− 1) =
(
n− k
i− 1
)
1
mi−1
(
1− 1
m
)n−k−i+1
, n− k + 1 ≥ i ≥ 1 (2pt)
(b) The average of Xk is
n−k
m + 1
3
(c) The average of searching for a random key is:
1 +
1
n
n∑
k=1
n− k
m
=
n− 1
2m
+ 1
9. (20 points) A k-way merge operation. Suppose you have k sorted arrays, each with n elements, and you
want to combine them into a single sorted array of kn elements.
(a) (5 points) Here’s one strategy: Using the merge procedure, merge the first two arrays, then merge in
the third, then merge in the fourth, and so on. What is the time complexity of this algorithm, in terms
of k and n?
Answer:
2n+ 3n+ · · · kn = (k + 2)(k − 1)
2
n = Θ(k2n)
(b) (8 points) Design and analyze a more efficient algorithm, using divide-and-conquer, that solves this
problem in O(knlogk) time.
Answer: Recursive Pairwise Merge
T (k) = 2T (
k
2
) + kn, in terms of just k, not kn
Complexity is O(knlogk), not O(knlogkn)
(c) (7 points) Design and analyze another efficient algorithm, using min-heap, that solves this problem in
O(knlogk) time.
Answer: Take the smallest element from each sorted array, form a min-heap with k elements, do
extract-min, that will be the minimum of all k arrays, insert the next larger element from the array
will the minimum is taken into the min-heap, do extract-min, get the second minimum of all k arrays,
repeat kn times to get all sorted.
Total complexity: O(k) + nkO(log k) = O(nk log k).