CS 325 Algorithms Spring 2023
MIDTERM REVIEW PROBLEMS

The Midterm will cover HWs 1-6, Quizzes 1-2, and all lectures before the Midterm.

1. (a) Give real-life examples of queue, stack, priority queue, hash-table, and binary search.

   (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?

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

3. Rank the growth functions from slowest to fastest:
   1, logn, n, nlogn, n^2, 2^n, n!, n^n

4. Analyze the complexity for each of the following (e.g., using the recursion tree method), and name as many instances for each case (in the midterm you only need to give one instance).

   All recurrences we've seen so far can be organized as a 3x3 table (only 1 cell is not covered):
   
                            |  ...O(1)  | ...O(logn)  | ...O(n)   
       ---------------------+-----------+-------------+---------
binary T(n) = 2T(n/2) + ... |           |             |
unary  T(n) =  T(n/2) + ... |           | not covered |  
unary  T(n) =  T(n-1) + ... |           |             |


   (a) T(n) = 2T(n/2) + O(n)
   (b) T(n) = 2T(n/2) + O(1)
   (c) T(n) = 2T(n/2) + O(logn)
   
   (d) T(n) =  T(n/2) + O(n)
   (e) T(n) =  T(n/2) + O(1)
   (f) T(n) =  T(n/2) + O(logn) -- NOT COVERED
   
   (g) T(n) =  T(n-1) + O(n)  
   (h) T(n) =  T(n-1) + O(logn)
   (i) T(n) =  T(n-1) + O(1)

5. Give (at least) two reasons why bubble-up is (a little) faster than bubble-down.

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.

7. On the second page, there will be three DP questions:
   (a) one similar to HW5 # of BSTs, but about balanced trees.
   (b) one about HW5 MIS code. Make sure you understand the reference solution, esp. backtracking.
   (c) one similar to HW6 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

9. The three DP questions might also ask you (but rather minor):
   (a) type of problem: optimization or counting?
   (b) type of divides: binary or unary? (# of conquers / recursions / children)
   (c) number of divides: two or multiple? (# of choices)
   (d) summary operator (\oplus) and combination operator (\otimes)

   problem      | type   | dim. |    divides     | \oplus | \otimes
   ----------------------------------------------------------------
   Fibonacci    | count. |  1   | unary | two    |   +    |    *
   # bitstrings | count. |  1   | unary | two    |   +    |    *
   MIS          | optim. |  1   | unary | two    |  max   |    +
   # of BSTs    | count. |  1   | binary| multi. |   +    |    *

   knapsack
   unbounded    | optim. |  1   | unary | multi. |  max   |    +
   0-1          | optim. |  2   | unary | two    |  max   |    +
   bounded      | optim. |  2   | unary | multi. |  max   |    +

   *dim.: dimensionality of subproblem.

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