CSE 632: Analysis of Algorithms II (Spring 2025)


• Course Syllabus: Detailed course content, including grading policy, academic integrity policy, accessibility resources, etc.

Course Logistics

Lecture Time: Tue, Thu 04:00PM - 05:20PM

Lecture Location: Talbrt 103

Instructor: Kelin Luo

Office Location: 306 Davis Hall

Office Hour: Tue, Thu 12:30PM-13:30PM and by Appointment

Except for the office hours provided, you can also set up an appointment (by email) for additional office hours.

Email: [first name][last name][at][buffalo][dot][edu]

Please sign up for the course on Piazza. You can post all questions related to lectures and assignments on Piazza. Instructor posts announcement on piazza.

References

Course information and lecture notes from previous years

  • UB CSE632 Analysis of Algorithms II : Randomized Algorithms (2019 Fall) by Shi Li

    • Recommended Textbooks

    There are no required textbooks, but most of the contents we will discuss are covered in the following books:

  • Michael Mitzenmacher and Eli Upfal. Probability and Computing. Cambridge University Press, 2nd edition, 2017.

  • Rajeev Motwani and Prabhakar Raghavan. Randomized Algorithms. Cambridge University Press, Cambridge, England, June 1995.

  • Bernhard Korte and Jens Vygen. Combinatorial Optimization: theory and algorithms, 6th edition. Springer, 2018.

  • Sheldon M. Ross. Introduction to Probability Models. Academic Press, Inc., 10th edition, 2009.

  • David P. Williamson and David Shmoys. The Design of Approximation Algorithms. Cambridge University Press, 2011.

  • Vijay Vazirani. Approximation Algorithms. Springer-Verlag, 2001.

    • Other Course References

    Similar courses taught in other universities:

  • CMU: Advanced Algorithms (2024)

  • Princeton: Advanced Algorithm Design(2024)

  • Nanjing University: Advanced Algorithms (2024)

  • Stanford: Randomized Algorithms and Probabilistic Analysis (2023)

  • UT Austin: Randomized Algorithms (2023)

    • News

    [Jan 20, Mon] Course website online.
    [Jan 23, Thu] Quiz 1 on UBlearns. Quiz 1 (Join Piazza, Academic Integrity Quiz, MUST GET 100%) due 11 Feb@ 11:59PM.
    [See News on Piazza]

    Slides and Assignments

    See Piazza -> Resources -> Lecture Notes

    Deadlines for Homeworks and Projects

    HWs/ProjectsReleasing DateDeadline
    HW1Jan 28Feb 11
    HW2Feb 11Feb 25
    HW3Mar 11Apr 01
    HW4Apr 01Apr 15
    Project 1Feb 11Mar 11
    Project 2Mar 25May 06

    Note: (1) Both homeworks and projects deadlines are at 11:59 PM EST. Expectations will be clearly noted when the assignments come out as well as the duration of the assignment. Please pay attention to the amount of time that each assignment provides and begin early. (2) All assignment (homework and project) must be typed in LaTex. For web-based LaTeX editing, you can explore platforms such as Overleaf. (3) Both homeworks and projects will be submitted and returned via UBlearns.

    Tentative Schedule

    WeekDateTopicContentsOther Notes
    1 Jan 23 Introduction Course Syllabus and Sample Algorithm with LLM Proof Sketch Notes
    2Jan 28 Probability Analysis Basics: Probability Spaces, Events, Expectation, Conditional Probability, Random Variables, Expected Values, Variance and Standard Deviation
    Jan 30 Common Distributions, Balls and Bins, Birthday Paradox
    3Feb 04 Applications: Minimum Cut, Karger's Contract Algorithm
    Feb 06 Fast Cut, Maximum Cut
    4Feb 11 Universal Hashing HW1 Deadline
    Feb 13 Randomized Quicksort
    5Feb 18 Concentration Inequalities Markov inequality, Chebychev's Inequality and Chernoff/Rubin Bounds
    Feb 20 Johonson-Linenstrauss Theorem/Transformation (JLT)
    6Feb 25 Application: Nearest Neighbor Search HW2 Deadline
    Feb 27 Markov Chains Markov Chains, Random Walks, Stirling's Formula and the Binomial Theorem
    7Mar 04 Applications: Local Search Algorithm for 2-Sat
    Mar 06 Project 1 Presentation
    8Mar 11 Lovász Local Lemma Lovasz Local Lemma P1 Deadline
    Mar 13 Moser's Constructive Proof
    9Mar 18 Spring Break Spring Break, no class
    Mar 20 Spring Break, no class
    10Mar 25 Linear programming (LP) Basics and Applications
    Mar 27 Exact Alg Using LP: Bipartite Matching
    11Apr 01 Primal-Dual Schema, Max-Flow Min-Cut Theorem HW3 Deadline
    Apr 03 Applications: Weighted Vertex Cover, Facility Location Problem
    12Apr 08 Online Algorithms Online Matching with a Primal-Dual Analysis
    Apr 10 Applications: Ski-Rental
    13Apr 15 Multiplicative Weight Update (MWU) Learning from experts, AdaBoost HW4 Deadline
    Apr 17 Applications: Multicommodity Flow Problems
    14Apr 22 Advanced Topics Streaming Algorithm
    Apr 24 Inapproximability
    15 Apr 29 Last Day of Classes Q & A
    May 01 Project 2 Presentation
    16 May 06 Oral Final exam (30 minutes per student Q & A) P2 Deadline