What I learned from you:

(please suggest additional points or corrections on canvas discussion board)

1. TSP with python sets is O(2^n n^3). -- Fengfei, Liqiang
   Using bit-operations or union-find (inverse ackerman)
   can reduce it to the theoretical value (2^n n^2).

2. one-liners for opt and back, e.g., in TSP:  -- Zeyu, Alex
   goal, goalj = min((best[n][full, j] + cost, j) for j, cost in edges[0])

3. @memoize decorators -- Alex

4. memory profiler (esp. in ipython) -- Jeff

5. The KT version for RNA structure is disjoint, -- many 
   which can be used for counting.
   

What you should have learned from me (take-home messages):


0. Overall: complexity analysis is real, and easily verifiable empirically.
   "Microscopic" view of complexity: per-step evaluation.

1. quicksort builds a BST implicitly; connections to in-order traversal
   quickselect is expected linear time
2. return two things in divide-n-conquer (e.g., longest path, number of inversions)
3. two-pointers method for sorted array (---> --->,  <--- --->, ---> <---)
4. recursion-tree method to analyze time complexity

5. heapify is linear time
6. k-way mergesort is nlogn
7. baby Dijkstra in nbest is klogk
8. datastream: use max-heap for min to discard most elements

9. Amortized analysis (e.g., python list append)

10. DP is just memoized divide-n-conquer (perspective 1)
11. Fibonacci is the simplest DP model, and
    max-independent-set and number-of-bitstrings are variants of Fibonacci

12. bounded knapsack: add a dimension

<---- MIDTERM ---->

13. LIS: subproblems can be defined differently from the whole problem
14. TSP: powerset of subproblems (as opposed to permutation): 2^n << n!

15. DP is just shortest/longest/number_of paths on a DAG (perspective 2)
    (often you construct a new graph based on input graph, as in TSP)

    space complexity: V (number of subproblems, i.e., nodes)
    time complexity: E (number of updates, i.e., edges)

16. Bottom-up DP (Viterbi) just updates along a topological order found by BFS;
    Top-down DP is similar to running DFS from the sink to find topological order.

17. Dijkstra needs decrease-key(), and a combo of hash+heap
18. Viterbi only works on DAGs, but do not care about edges weights;
    Dijkstra only works with non-negative edge weights, but do not care about graph structure.

19. hypergraph vs. graph problems in DP. 
    the former has tree-structured solutions, 
    and includes: number of BSTs, RNA structure, 
    matrix-chain multiplication, optimal triangulation, CFG parsing, optimal BST, etc.
    
    the latter has chain-structured solutions, 
    and includes everything else.
    
    Generalized Viterbi works on hypergraphs. (there is still topological order)

20. k-best solutions in DP, reusing nbest above (baby Dijkstra)