SOLUTIONS to MIDTERM REVIEW PROBLEMS
The Midterm will cover HWs 16 and Quizzes 12 (with a focus on HWs 3, 5, 6).
If there is any discrepancy between the review problems and this doc, trust this doc.
1(a). Give reallife examples of queue, stack, priority queue, hashtable, and binary search.
Answer:
priority queue: emergency room
hashtable & binary search: index at the end of each textbook.
Note that you need both binary search and hash to use the index:
first, do binary search in the index pages (sorted alphabetically)
to find the term you're looking for, and then use hashmap to go to
the page containing that term.
1(b). How do you use a priority queue to simulate (a) a queue and (b) a stack?
Which one is used in DFS, and which one in BFS?
Answer:
Use the arriving timestamp or its negative value as the key of this unit
to simulate a queue or stack, respectively.
DFS uses stack; BFS uses queue; Dijkstra (an extension of BFS) uses priority queue.
2. What's the lowerbound of comparisonbased sorting algorithms?
\Omega (n log n). See Course Notes 1.8 (just updated).
Note. Big\Omega is the notation for lowerbound, BigO for upperbound, and Big\Theta for precise bound.
But in most occasions, we just use BigO.
See https://en.wikipedia.org/wiki/Big_O_notation for details.
To see why we need at least ~nlogn comparisons to sort n numbers, consider the number of
all possible orderings: n!. Each comparison (such as a_1 ? a_2) would halve the possibilities.
So you can draw a decision tree like this:
a_1 ? a_2 n! possibile orderings
< / \ >
/ \
a_1 ? a_3 a_2 ? a_3 n!/2 possbile orderings
... ...
How many levels (or comparisons) do you need to reach a unique ordering?
h = log (n!)
Now let's simplify this h. It's obvious that (n/2)^{n/2} < n! < n^n:
****> n
****>  n1
****>  ...
****>  n/2
>  ...
>  ...
>  2
+>+ 1
the triangle represents n!
the small square on the topleft corner (****) is (n/2)^{n/2}
the big square that contains the triangle is n^n
so (n/2)^{n/2} < n! < n^n.
Now take logarithm for the above, we get:
log (n/2)^{n/2} < h = log(n!) < log n^n
n/2 log n/2 < h = log(n!) < n log n
Both sides grow by ~n log n, so h = \Omega(n log n).
3. Rank the growth functions from slowest to fastest:
1, logn, n, nlogn, n^2, 2^n, n!, n^n
Answer: just that order. :)
4. Analyze the complexity for each of the following (use recursion tree method), and name an instance:
 ...O(1)  ...O(logn)  ...O(n)

unary T(n) = T(n/2) + ...  O(logn)  O((logn)^2)  O(n) fastest

binary T(n) = 2T(n/2) + ...  O(n)  O(n)  O(nlogn) 
v
unary T(n) = T(n1) + ...  O(n)  O(nlogn)  O(n^2) slowest
fastest > slowest
(a) T(n) = 2T(n/2) + O(n) = O(nlogn) mergesort; quicksort bestcase; # of inversions
(b) T(n) = 2T(n/2) + O(1) = O(n) balanced binary tree traversal; longest
(c) T(n) = 2T(n/2) + O(logn) = O(n) heapify
(d) T(n) = T(n/2) + O(n) = O(n) quickselect bestcase
(e) T(n) = T(n/2) + O(1) = O(logn) binary search; search in BST bestcase (balanced BST)
(f) T(n) = T(n/2) + O(logn) = O((logn)^2)  NOT COVERED; NOT REQUIRED
(g) T(n) = T(n1) + O(n) = O(n^2) quicksort/quickselsect worstcase; insertion/selection sort
(h) T(n) = T(n1) + O(1) = O(n) linearchain tree traversal; array traversal; longest; search in BST worstcase
(i) T(n) = T(n1) + O(logn) = O(nlogn) build heap by n pushes instead of heapify
Pay special attention to the contrast b/w the two methods for building a heap: (c) and (i).
Note: you need to derive the most accurate (tightest) complexity (i.e., Big\Theta(), even though we write BigO()).
5. Give (at least) two reasons why bubbleup is faster than bubbledown.
Answer:
reason 1: bubbledown needs more comparisons per step
reason 2: bubbledown path is nondeterministic (bubbleup path is deterministic)
Followup: if somebody claims that s/he has invented a datastructure where bubbledown is faster than O(logn), you know for sure s/he is wrong. Why?
Answer: lowerbound. heapify is O(n), and if each heappop (bubbledown) is faster than O(logn), then heapify + n heappops is faster than O(nlogn).
6. The BIG heap question will be a combination of two HW4 problems: teams and nbestc.
Make sure you understand the reference solution for teams and nbestc
(just the basic solutions are enough, but do understand them deeply).
The extension in the midterm would have each US state picking top 5 double players. See slides:
https://classes.engr.oregonstate.edu/eecs/spring2024/cs325001/nbest.pdf
7. On the second page, there will be three DP questions:
(a) one similar to HW5 # of BSTs, but about balanced trees.
Hint: if a balanced tree has h levels, then its subtrees must have ______ levels?
(b) one about HW5 MIS code. Make sure you understand the reference solution (bottomup + recursive backtracing).
understanding __iadd__ is highly recommended.
(c) one similar to (unbounded) knapsack.
Note: a problem similar to 01/bounded knapsack will appear in the Final.
8. Question (c) above will include:
(a) greedy solution
(b) counterexample
(c) subproblem
(d) recurrence
(e) base cases
(f) time and space complexities
(g) graph interpretation  longest path, shortest path, number of paths.
Only questions 6 and 7(b) will involve filling the blanks in code.
Most (if not all) of the extra credit questions are also covered in this review sheet.