CS 325  Algorithms  SPRING 2023
SOLUTIONS for MIDTERM REVIEW PROBLEMS

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

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

2. What's the lowerbound of comparison-based sorting algorithms?

   \Omega (n log n).

   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.

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 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 (see HW4 Q0)
   
   (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 bestcase (balanced BST)
   (f) T(n) =  T(n/2) + O(logn) -- NOT COVERED
   
   (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 (linear-chain BST)
   (i) T(n) =  T(n-1) + O(logn)	 = O(nlogn)   making heap by n heappushes instead of heapify

   Pay special attention to the contrast b/w the two methods for making 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 state being an nbestc instance, e.g., each state is picking top 5 double players. See slides:
   https://classes.engr.oregonstate.edu/eecs/spring2023/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 complexity

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.