HackMDComplexity 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
- Turing machines
- Decidability
- Time complexity
- P, NP, NP-completeness
- Cook-Levin Theorem
- Decision vs. search
- Hierarchy theorems
- Ladner's Theorem
- Relativization barrier
- Space complexity
- Savitch's Theorem
- PSPACE, PSPACE-completeness
- Logspace computation
- Immerman-Szelepcsényi Theorem
- Polynomial hierarchy
- PH via oracles, alternation
- Time-space tradeoffs
- Circuits, non-uniform computation
- Circuit lower bounds
- Probabilistic algorithms
- Randomized time classes, error reduction
- BPP vs. P/poly, BPP vs. PH
- PromiseBPP, randomized reductions, Valiant-Vazirani Theorem
- Counting, #P, #P-completeness
- Toda's Theorem, approximate counting and sampling
- Interactive proofs
- SAT solving and fine-grained complexity
- Arthur-Merlin classes
- IP = PSPACE
- PCP Theorem, hardness of approximation
- More hardness of approximation, proof of PCP Mini
- Circuit lower bounds (Parity is not in AC0)
- NEXP is not in ACC0
Math you need for CS
- Basics of Boolean Fourier analysis
- BLR test, influence
- More on influence, stability
- Spectral concentration, low-degree learning
- Majority and the Central Limit Theorem
- Introduction to hypercontractivity
- Hypercontractivity continued
- Introduction to pseudorandomness, bounded independence
- Concentration, PRGs, small-bias distributions
- Bounded independence fools AC0
- Polynomial constructions, introduction to extractors
- More on extractors, Nisan's PRG
- Intro to spectral graph theory, Laplacian and its eigenvalues
- Conductance, Cheeger's inequality
- Random walks
- Expanders and applications
- Resistor networks, spectral sparsification
- Error-correcting codes, linear codes
- Existential bounds, Reed-Solomon codes
- Justesen codes, expander codes
- LDPC decoding, linear programming
- Duality, SDPs, Max Cut
- CSPs, Sherali-Adams
- Pseudoexpectations, Sum-of-Squares
Advanced data structures
-
Temporal: Class overview, pointer machine, partial persistence, full persistence, confluent persistence, functional
-
Temporal: Partial retroactivity, full retroactivity, nonoblivious retroactivity
-
Geometric: Point location via persistence, dynamic via retroactive; orthogonal range queries, range trees, layered range trees, dynamizing augmentation via weight balance, fractional cascading
-
Geometric: O(log n) 3D orthogonal range searching via fractional cascading; kinetic data structures
-
Dynamic optimality: Binary search trees, analytic bounds, splay trees, geometric view, greedy algorithm
-
Dynamic optimality: Independent rectangle, Wilber, and signed greedy lower bounds; key-independent optimality; O(lg lg n)-competitive tango trees
-
Memory hierarchy: Models, cache-oblivious B-trees
-
Memory hierarchy: Ordered-file maintenance, list labeling, order queries, cache-oblivious priority queues
-
Memory hierarchy: Distribution sweeping via lazy funnelsort; cache-oblivious orthogonal 2D range searching: batched and online
-
Dictionaries: Universal, k-wise independent, simple tabulation hashing; chaining, dynamic perfect hashing, linear probing, cuckoo hashing
-
Integer: Models, predecessor problem, van Emde Boas, x-fast and y-fast trees, indirection
-
Integer: Fusion trees: sketching, parallel comparison, most significant set bit
-
Integer: Predecessor lower bound via round elimination
-
Integer: Sorting in linear time for w = O(lg2+ε n), priority queues
-
Static trees: Least common ancestor, range minimum queries, level ancestor
-
Strings: Suffix tree, suffix array, linear-time construction for large alphabets, suffix tray, document retrieval
-
Succinct: Rank, select, tries
-
Succinct: Compact suffix arrays and trees
-
Dynamic graphs: Link-cut trees, heavy-light decomposition
-
Dynamic graphs: Euler tour trees, decremental connectivity in trees in O(1), fully dynamic connectivity in O(lg2 n), survey
-
Dynamic graphs: Ω(lg n) lower bound for dynamic connectivity
-
History of memory models: Idealized 2-level, red-blue pebble game, external memory, HMM, BT, (U)MH, cache oblivious.
Graduate algorithms
- Fast Fourier Transform
- Linear programming and its applications
- Network flow – Ford-Fulkerson, MFMC theorem, applications.
- Approximation methods for hard problems
- Basic discrete and continuous optimization methods
- Probabilistic algorithms, including those related to finding cuts in graphs, polynomial identity testing, and maximum matching
- Algorithms for large datasets and graphs, including clustering using k-means and k-median, cuts in graphs, duality, and others
- Pick one: Quantum computing, parallel algorithms, or game-theoretic algorithms - study some implementations. Parallel and distributed will haunt you later anyway.
