EL9343 Midterm Exam (2020 Fall)
Name: ID:
Oct 25, 2020
Write all answers on your own blank answer sheets, scan and upload answer sheets to
newclasses at the end of exam, keep your answer sheets until the grading is finished.
Multiple choice questions may have multiple correct answers. You will get partial
credits if you only select a subset of correct answers, and will get zero point if you
select one or more wrong answers.
1. (18 points) True or False (3 points each)
(a) T or F: Tree height of a max heap is Θ(logn);
(b) T or F: 2n = Θ(3n);
(c) T or F: By using uniform hashing functions, the number of elements hashed into a
slot is independent from the number of elements in any other slot;
(d) T or F: Bubble sort is stable;
(e) T or F: After inserting n elements into an empty binary search tree, search complexity
is O(logn);
(f) T or F: In QuickSort, if the array has n elements, the running time for the first
partition procedure is Θ(n).
2. (4 points) Which of the following function pairs satisfy f(n) = ω(g(n))?
(a) f(n) = n and g(n) = 3n;
(b) f(n) = n log n and g(n) = 3n + log n;
(c) f(n) = 2n and g(n) = log n;
(d) f(n) = nk and g(n) = kn, where k > 1;
(e) None of the above
3. (4 points) For a given node v in a binary search tree, which of the following node can be its
successor?
(a) Left child of v’s right child;
(b) v’s right child;
1
(c) Right child of v’s left child;
(d) Parent of v;
(e) None of the above.
4. (4 points) Which of the following statements about sorting algorithms are true?
(a) Counting sort is stable;
(b) Quicksort runs in best-case time Θ(n);
(c) The most imbalanced partition generated by Hoare’s scheme is caused by a already
sorted input (without using randomization);
(d) The pivot element in Lomuto’s partition is not included in any of the two subarrays;
(e) None of the above.
5. (4 points) Which of the following statements regarding Divide-and-Conquer algorithms are
true?
(a) In quicksort algorithm, partition takes more time than combine the solutions to the
subproblems;
(b) Divide-and-Conquer algorithms always run faster than iterative algorithms;
(c) The master theorem cannot be used to solve all recurrences;
(d) Insertion sort is a divide-and-conquer algorithm;
(e) None of the above.
6. (4 points) Which of the following statements about max-priority queue of size n are true?
(a) The queue can be stored in an array of size n;
(b) The max element is always at the root of the tree;
(c) Extract-max takes Θ(1);
(d) Find the minimum element takes Θ(log n);
(e) None of the above.
—————————————– continue on the next page ——————————————–
2
7. (6 points) Prove the following properties of asymptotic notation:
(a) (3 points)
√
n = o(n), where o(·) stands for little-o;
(b) (3 points) If f(n) = Ω(g(n)), and h(n) = Θ(g(n)), then h(n) = O(f(n)).
8. (12 points) Solve the following recurrences:
(a) (4 points) Use the iteration method to solve T (n) = T (n6 ) + T (
n
2 ) + 2n;
(b) (4 points) Use the substitution method to verify your solution for Question 8a.
(c) (4 points) Solve the recurrence T (n) = 2T (
√
n) + (log n)2.
9. (8 points) If heap-sort is applied to an array of [16, 23, 12, 15, 8, 21, 11, 6, 19, 25, 7],
(a) (4 points) plot the initial max-heap built from the array;
(b) (4 points) plot the max-heap after the third-maximum is extracted.
10. (12 points) In Randomized Quicksort (with Lomuto’s partition) for an array of n distinct
numbers,
(a) (4 points) after the first call of randomized-partition, what is the probability that the
length of the left partition is m, for any 0 ≤ m ≤ n?
(b) (4 points) suppose the second partition call is for the left partition resulted from the
first partition call, what is the probability that the i-th ranked number is in the same
partition as the (i + k)-th ranked number after the first two partition calls?
(c) (4 points) is it true that the i-th ranked number will always be compared with the
(i + 1)-th ranked number exactly once throughout the sorting process? prove it if it is
true, or disprove it if it is false.
11. (11 points) We have a hash table with m slots and collisions are resolved by chaining.
Suppose n distinct keys are inserted into the table. Each key is equally likely to be hashed
to each slot.
(a) (5 points) When the i-th (1 ≤ i ≤ n) key is inserted to the hash table, let Yi be the
random variable of the length of the list the i-th key will be inserted to, what is the
probability mass function of Yi, i.e., calculate P (Yi = k), ∀k ≥ 0?
(b) (3 points) What is the expected value of Yi?
(c) (3 points) After all the n distinct keys have been inserted, what is the expected number
of elements examined when searching for a new key not from the n inserted keys?
12. (13 points) Let X and Y be two arrays of n real numbers sorted into non-decreasing order.
Design and analyze an algorithm that finds the median of the 2n combined numbers in worst-
case O(log n) time.
(a) (9 points) write down the pseudo-code of your algorithm;
(b) (4 points) analyze its time complexity.
—————————————– end of exam ——————————————–