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)