Embedded Files
Algorithm Design Using
Lecutre 1 . Review of Probability [MU05, Har23] Basics of Probability, Basics of Randomization.
Lecture 2. Review of Linear Programming [Vaz01, Rou16] Linear Programming with Applications, Max Flow and Min s-t Cut Problem.
Lecture 3. Basics of Randomized Algorithms [Rou17] Quicksort Analysis, Randomized Median Selection.
Lecture 4. Basics of Approximation Algorithms [Vaz01] Approximation Ratio, Integrality Gap, Vertex Cover Problem via Maximal Matching.
Lecture 5. Vertex Cover Problem via LP [Vaz01] LP Rounding Based Algorithm for Vertex Cover, Integrality Gap Examples.
Lecture 6. Graph Partitioning via LP [Che21] Graph Min s-t Cut and Multicut Problems using Linear Programming.
Lecture 7. Concentration Inequalities [Ver18, OD20] Gaussian Tail Bounds, Markov Inequality, Moment Method, Chernoff-Hoeffding Inequality, Applications: Coin Tossing, Polling.
Lecture 8. Curse of Dimensionality [Ver18, Rot24] Properties of High Dimensional Spaces, Random vectors, Rotational Invariance of Gaussians..
Lecture 9. JL Lemma [Gup20, Rot24] Metric Spaces and Metric Embeddings, Dimension Reduction via JL Lemma, Applications of JL Lemma.
Lecture 10. Streaming Algorithms [Che22, Har23] The Streaming Model, Sampling Random Objects, Reservoir Sampling.
Lecture 11. Approximate Counting [Che22] Morris Counter, Mean Estimation Problem, Medians of Mean Estimator.
Lecture 12. Estimating Frequency Moments of Stream [Che22, Rot24] Distinct Elements Problems, Heavy Hitters Problems.
Lecture 13. Basics of Linear Algebra [Axl24, Rot24] Fundament Spaces, Projection, Least Squares Solution, Gram-Schmidt Orthogonalization.
Lecture 14. Spectral Theory of Matrices [Rot24] Eigenvalues and Eigenvectors, Variational Characterization of Eigenvalues, Matrix Norms.
Lecture 15. Principal Component Analysis [Rot24] Data Analysis and Visualization, Characterizing top k Principal Components, Applications.
Lecture 16. Spectrum of Classic Graphs [Lau25]. Compute Spectrum for: Complete Graph, Complete Bipartite Graph, Cycles, Hypercubes, Random Graphs.
Lecture 17. Combinatorial Properties via Eigenvalues [Lau25] Maximum/Average Degree Bounds, Largest Eigenvalue of Trees/Bounded Arobricity Graphs, Wilf's Theorem, Graph Coloring.
Lecture 18. Combinatorial Insights via The Graph Laplacian [Lau25], The Graph Laplacian and Normalized Laplacian, Characterizing Bipartiteness and Connectedness, Hall's Drawing.
Lecture 19. Cheeger's Inequality [Lau25] Robust Connectivity: Graph Expansion and Cousins, Spectral Relaxation, Easier side of Cheeger's Inequality.
Lecture 20. Cheeger's Inequality [Lau25] Proof of Cheeger's Inequality, Fiedler's Algorithm, Tight Examples.
References
[Axl24] Linear Algebra Done Right by Sheldon Axler, Springer, 2024
[Che21] Course on Approximation Algorithms by Chandra Chekuri, UIUC, 2021
[Che22] Course on Algorithms for Big Data by Chandra Chekuri, UIUC, 2022
[Gup20] Advanced Algorithms by Anupam Gupta, CMU, 2020
[Har23] A First Course in Randomized Algorithms by Nick Harvey, University of British Columbia, 2023
[MU05] Probability and Computing by Michael Mitzenmacher and Eli Upfal, Cambridge University Press, 2005
[Lau25] Notes on Algorithmic Spectral Graph Theory by Lap Chi Lau, University of Waterloo, 2025
[Lee24] Course on Toolkit for modern algorithms by James R.Lee, University of Washington, 2024
[OD20] TCS Toolkit by Ryan O'Donell, CMU, 2020
[Rot24] Design and Analysis of Algorithms by Thomas Rothvoss, University of Washington, 2024
[Rou16] Second Course in Algorithms by Tim Roughgarden, Stanford University, 2016
[Rou17] Algorithms Illuminated by Tim Roughgarden, Cambridge University Press, 2017
[Sar21] Course on Expanders and Fast Graph Algorithms by Thatchaphol Saranurak, University of Michigan, 2021
[Vaz01] Approximation Algorithms by Vijay V.Vazirani, Springer-Verlag, 2001
[Ver18] High Dimensional Probability by Roman Vershynin, Cambridge University Press, 2020
Page updated
Google Sites
Report abuse