Advanced algorithms
Graduate · CS / Programming
Syllabus focus
Theoretical / proof-based
Pricing
Graduate-level rates are set on consultation. See the pricing page for K–12 and undergraduate rates.
Topics typically covered
Theoretical / proof-based
Advanced analysis
- Amortized analysis: accounting and potential methods
- Randomized algorithms: expectation and concentration (intro)
- Network flow: max-flow min-cut and algorithms
- Matching theory and blossom algorithm (intro)
- Linear programming duality in algorithm design (intro)
Hardness and approximation
- NP-completeness reductions in depth
- Approximation algorithms and inapproximability (intro)
- Parameterized complexity and FPT (intro)
- Online algorithms and competitive analysis (intro)
- Exponential-time algorithms and branching (intro)
Specialized topics
- Advanced dynamic programming on trees and graphs
- Sublinear algorithms and property testing (survey)
- Streaming algorithms (intro)
- Hardness of approximation for canonical problems
- Research paper presentations
Notes
Expect proof-heavy homework and familiarity with graduate-level discrete math and probability.