CS 514  Algorithms  FALL 2022
SOLUTION for MIDTERM REVIEW PROBLEMS

The Midterm will cover HWs 1-6 and Quizzes 1-2 (with a focus on HWs 4-6).

1. 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)

2. 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 pushing index itself/its negative value as the key of this unit
to simulate a stack/queue.

DFS uses stack; BFS uses queue; Dijkstra (an extension of BFS) uses priority queue.


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:
   (a) T(n) = 2T(n/2) + O(n)
   (b) T(n) = 2T(n/2) + O(1)
   (c) T(n) =  T(n/2) + O(n)
   (d) T(n) =  T(n/2) + O(1)
   (e) T(n) = 2T(n/2) + O(logn)
   (f) T(n) =  T(n-1) + O(n)  
   (g) T(n) =  T(n-1) + O(logn)
   (h) T(n) =  T(n-1) + O(1)     <-- added

Note: you need to derive the most accurate (tightest) complexity (i.e., Big-\Theta(), even though we write Big-O()).

Answer:
(a) O(nlogn)  -- quicksort bestcase, mergesort
(b) O(n)      -- traversing a *balanced* binary tree
(c) O(n)      -- quickselect bestcase
(d) O(logn)   -- binary search, find in balanced binary search tree
(e) O(n)      -- heapify (see HW4 problem 0)
(f) O(n^2)    -- quicksort/quickselect worst-case, insertion/selection sort
(g) O(nlogn)  -- n heappushes instead of heapify
(h) O(n)      -- traversing an array or a *linear-chain* binary tree

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)

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).
   

7. On the second page, there will be three DP questions:
   (a) one similar to HW5 # of BSTs.
   (b) one about HW5 MIS code. Make sure you understand the reference solution (the basic one, also on slides).
   (c) one similar to (unbounded, 0-1, or bounded) knapsack.

8. Question (c) above will include:
   (a) greedy solution
   (b) counter-example
   (c) subproblem
   (d) recurrence
   (e) base cases
   (f) time and space complexity

Only questions 6 and 7(b) will involve filling the blanks in code.