CS 514  Algorithms  Fall 2022
MIDTERM REVIEW PROBLEMS

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

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

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?

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 (use the recursion tree method), and name an instance for each:
   (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)

5. Give (at least) two reasons why bubble-up is 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.
   (b) one about HW5 MIS code. Make sure you understand the reference solution.
   (c) one similar to 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.