Complexity theory and Math for CS are both by the awesome Prof. Mark Bun @ BU. Prof.Hohmer for Graduate Algorithms, rest is either MIT or Harvard. Compiled from all the sources, plus some experience.

Best results? Pick a language, only use raw Vim, and do a bunch of leetcodes. Leetcode is great for helping with algorithmic thinking.

### Algorithms

*Should take 3-4 days.*

Unit 1: Introduction
- Algorithmic thinking, peak finding

Unit 2: Sorting and Trees
- Insertion sort, merge sort
- Heaps and heap sort
- Binary search trees, BST sort
- AVL trees, AVL sort
- Counting sort, radix sort, lower bounds for sorting and searching

Unit 3: Hashing
- Hashing with chaining
- Table doubling, Karp-Rabin
- Open addressing, cryptographic hashing

Unit 4: Numerics
- Integer arithmetic, Karatsuba multiplication
- Square roots, Newton’s method

Unit 5: Graphs
- Breadth-first search (BFS)
- Depth-first search (DFS), topological sorting

Unit 6: Shortest Paths
- Single-source shortest paths problem
- Dijkstra
- Bellman-Ford
- Speeding up Dijkstra

Unit 7: Dynamic Programming
- Memoization, subproblems, guessing, bottom-up; Fibonacci, shortest paths
- Parent pointers; text justification, perfect-information blackjack
- String subproblems, pseudopolynomial time; parenthesization, edit distance, knapsack
- Two kinds of guessing; piano/guitar fingering, Tetris training, Super Mario Bros.

### Complexity theory

First watch: https://www.youtube.com/watch?v=YX40hbAHx3s

1. Turing machines
2. Decidability
3. Time complexity
4. P, NP, NP-completeness
5. Cook-Levin Theorem
7. Decision vs. search
8. Hierarchy theorems
9. Ladner's Theorem
10. Relativization barrier
11. Space complexity
12. Savitch's Theorem
13. PSPACE, PSPACE-completeness
14. Logspace computation
15. Immerman-Szelepcsényi Theorem
16. Polynomial hierarchy
17. PH via oracles, alternation
18. Time-space tradeoffs
19. Circuits, non-uniform computation
20. Circuit lower bounds
21. Probabilistic algorithms
22. Randomized time classes, error reduction
23. BPP vs. P/poly, BPP vs. PH
24. PromiseBPP, randomized reductions, Valiant-Vazirani Theorem
25. Counting, #P, #P-completeness
26. Toda's Theorem, approximate counting and sampling
27. Interactive proofs
28. SAT solving and fine-grained complexity
29. Arthur-Merlin classes
30. IP = PSPACE
31. PCP Theorem, hardness of approximation
32. More hardness of approximation, proof of PCP Mini
33. Circuit lower bounds (Parity is not in AC0)
34. NEXP is not in ACC0

### Math you need for CS

1. Basics of Boolean Fourier analysis
2. BLR test, influence
3. More on influence, stability
4. Spectral concentration, low-degree learning
5. Majority and the Central Limit Theorem
6. Introduction to hypercontractivity
7. Hypercontractivity continued
8. Introduction to pseudorandomness, bounded independence
9. Concentration, PRGs, small-bias distributions
10. Bounded independence fools AC0
11. Polynomial constructions, introduction to extractors
12. More on extractors, Nisan's PRG
13. Intro to spectral graph theory, Laplacian and its eigenvalues
14. Conductance, Cheeger's inequality
15. Random walks
16. Expanders and applications
17. Resistor networks, spectral sparsification
18. Error-correcting codes, linear codes
19. Existential bounds, Reed-Solomon codes
20. Justesen codes, expander codes
21. LDPC decoding, linear programming
22. Duality, SDPs, Max Cut
23. CSPs, Sherali-Adams
24. Pseudoexpectations, Sum-of-Squares

## Advanced data structures

1. Temporal: Class overview, pointer machine, partial persistence, full persistence, confluent persistence, functional
2. Temporal: Partial retroactivity, full retroactivity, nonoblivious retroactivity
3. Geometric: Point location via persistence, dynamic via retroactive; orthogonal range queries, range trees, layered range trees, dynamizing augmentation via weight balance, fractional cascading

4. Geometric: O(log n) 3D orthogonal range searching via fractional cascading; kinetic data structures

5. Dynamic optimality: Binary search trees, analytic bounds, splay trees, geometric view, greedy algorithm

6. Dynamic optimality: Independent rectangle, Wilber, and signed greedy lower bounds; key-independent optimality; O(lg lg n)-competitive tango trees

7. Memory hierarchy: Models, cache-oblivious B-trees

8. Memory hierarchy: Ordered-file maintenance, list labeling, order queries, cache-oblivious priority queues

9. Memory hierarchy: Distribution sweeping via lazy funnelsort; cache-oblivious orthogonal 2D range searching: batched and online

10. Dictionaries: Universal, k-wise independent, simple tabulation hashing; chaining, dynamic perfect hashing, linear probing, cuckoo hashing

11. Integer: Models, predecessor problem, van Emde Boas, x-fast and y-fast trees, indirection

12. Integer: Fusion trees: sketching, parallel comparison, most significant set bit

13. Integer: Predecessor lower bound via round elimination

14. Integer: Sorting in linear time for w = O(lg2+ε n), priority queues

15. Static trees: Least common ancestor, range minimum queries, level ancestor

16. Strings: Suffix tree, suffix array, linear-time construction for large alphabets, suffix tray, document retrieval

17. Succinct: Rank, select, tries

18. Succinct: Compact suffix arrays and trees

19. Dynamic graphs: Link-cut trees, heavy-light decomposition

20. Dynamic graphs: Euler tour trees, decremental connectivity in trees in O(1), fully dynamic connectivity in O(lg2 n), survey

21. Dynamic graphs: Ω(lg n) lower bound for dynamic connectivity

22. History of memory models: Idealized 2-level, red-blue pebble game, external memory, HMM, BT, (U)MH, cache oblivious.

### Graduate algorithms

1. Fast Fourier Transform
2. Linear programming and its applications
3. Network flow – Ford-Fulkerson, MFMC theorem, applications.
4. Approximation methods for hard problems
5. Basic discrete and continuous optimization methods
6. Probabilistic algorithms, including those related to finding cuts in graphs, polynomial identity testing, and maximum matching
7. Algorithms for large datasets and graphs, including clustering using k-means and k-median, cuts in graphs, duality, and others
8. Pick one: Quantum computing, parallel algorithms, or game-theoretic algorithms - study some implementations. Parallel and distributed will haunt you later anyway.