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 HW3/quiz2 problems: teams and nbestc.

   (a) Review the teams problem in Quiz 2.
   (b) Make sure you understand the reference solution for nbestc.
   (c) Make sure you understand the alternative solution for 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. backtracing.
   (c) one similar to HW6 knapsack (not sure which type though).

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

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 subproblems per divide)
   (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.

Other Review Tips:

10. Review the KT slides for DP (knapsack part: pages 31--41).

11. Understand why top-down might be (a lot) faster than bottom-up for knapsack problems (esp. 0-1).
    For the table on KT slide page 37, work out the top-down version, and see how many subproblems are needed.

12. Understand these correspondences:

    subproblem == node in DP graph == cell in DP table
    for each subproblem: the incoming edges == divides
    space complexity == # of subproblems == # of nodes in DP graph == size of DP table
    time complexity == (# of subproblems) * (# of divides per problem) == # of edges in DP graph
    backpointer == recording which divide (incoming edge) is the best for each subproblem

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