SOLUTIONS to MIDTERM REVIEW PROBLEMS The Midterm will cover HWs 1-6 and Quizzes 1-2 (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 real-life examples of queue, stack, priority queue, hash-table, and binary search. Answer: priority queue: emergency room hash-table & 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 comparison-based sorting algorithms? \Omega (n log n). See Course Notes 1.8 (just updated). Note. Big-\Omega is the notation for lowerbound, Big-O for upperbound, and Big-\Theta for precise bound. But in most occasions, we just use Big-O. 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 |****--> | n-1 |****-> | ... |****> | n/2 |---> | ... |--> | ... |-> | 2 +>-------+ 1 the triangle represents n! the small square on the top-left 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(n-1) + ... | O(n) | O(nlogn) | O(n^2) slowest fastest ----------------> slowest (a) T(n) = 2T(n/2) + O(n) = O(nlogn) mergesort; quicksort best-case; # 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 best-case (e) T(n) = T(n/2) + O(1) = O(logn) binary search; search in BST best-case (balanced BST) (f) T(n) = T(n/2) + O(logn) = O((logn)^2) -- NOT COVERED; NOT REQUIRED (g) T(n) = T(n-1) + O(n) = O(n^2) quicksort/quickselsect worst-case; insertion/selection sort (h) T(n) = T(n-1) + O(1) = O(n) linear-chain tree traversal; array traversal; longest; search in BST worstcase (i) T(n) = T(n-1) + 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 Big-O()). 5. Give (at least) two reasons why bubble-up is faster than bubble-down. Answer: reason 1: bubble-down needs more comparisons per step reason 2: bubble-down path is non-deterministic (bubble-up path is deterministic) Follow-up: if somebody claims that s/he has invented a datastructure where bubble-down is faster than O(logn), you know for sure s/he is wrong. Why? Answer: lowerbound. heapify is O(n), and if each heappop (bubble-down) 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/cs325-001/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 (bottom-up + recursive backtracing). understanding __iadd__ is highly recommended. (c) one similar to (unbounded) knapsack. Note: a problem similar to 0-1/bounded knapsack will appear in the Final. 8. Question (c) above will include: (a) greedy solution (b) counter-example (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.