CSC2421 Home Page

CSC2421 Topics in Algorithms: Online and other Myopic Algorithms (Winter/Spring 2022)


This page will provide WWW access to various documents concerning CSC2421. Announcements will also be made on this page.


The class is scheduled for Wednesday 2-4. We will continue to meet online via the zoom link until at least reading week. Please send any comments or questions to the instructor:


There are many web accessible courses that indicate the diversity of topics taught in graduate algorithms courses. For example, you may want to consider the following sources:

  • My previous CSC2421 Course
  • The Last Version of my CSC2420 Course
  • Tom Roughgarden Stanford Lectures
  • Princeton University CS521
  • University of Washington CSE 521
  • University of Washington CSE 522
  • Cornell University CSC6820
  • CMU 451/651
  • Nikhil Devanur Online Course
  • Avner Magen LP and SDP Course

  • Slides for the spring 2022 term will appear here. The first two weeks were used to provide an introduction to the general area of "online and othetr myopic algorithms" and for getting organized.
  • Calum's overview of online maximum bipartite matching.
  • The fourth week consisted of two presentations: Koosha's presentation for min cost matching with delays, and Noah's presentation of buffers and the QoS problem.

  • Overview of min cost matching with delays.
  • Overview of buffers and the QOS problem.
  • The fifth week consisted of two presentations: Ray's presentation of option pricing and Yuqui's prsentation of the EV charging-pricing-problem.

  • Overview of option pricing (updated April 13)
  • EV charging slides
  • The sixth week consisted mainly of a presentation by Rebecca regarding online path planning. The remainder of the class was a quick discussion of the secretary problem, prophet inequalities and prophet secretaries as in the text.

  • Path planning
  • The seventh week consisted of a presentation by Randy regarding online max sat and submodular maximization followed by an introduction to bandits and causal models by Arnav. Arnav has porovided his slides in advance of the class.

  • Online MaxSat
  • Bandits and Causal Models (updated March 4)
  • The eighth week will consist of presentations by Mohammed and Soroush regarding online algorithms and fairness.

  • Online Fair Division
  • Online Fair Resource Allocation
  • The ninth week will consist of presentations by Amanjit regarding the primal dual metod for online problems followed by Esther's presentation on 3 dimensional search and navigation.

  • Slides for the primal dual method (updated March 23)
  • Slides for 3D Scene Reconstruction
  • In the tenth week Aminjit will finish his presentation of the primal dual method and Fengwei will begin a discussion of social networks, local algorithms and dynmaic graph algorithms.

  • Slides for Social Networks, Local Algorithms and Dynamic Algorithms Reposted April 4
  • In the eleventh week, Fengwei finished his presentations of social networks and Noah presented the optimal competitive algorithm for the QoS problem. Arnav started on the completion of his presentation on casual models and will finish that next week.

    In the twelth week, Amin gave a presentation on reinforcement learning. Arnav completed of his presentation on casual models and Yuqui finished his presentation regarding EV charging pricing.

  • Slides for Rinforcement Learning
  • In our final week, Mohammed gave a presentation on competitive secretary problems. Ray completed his presentation on robust option pricing. Slides contain links to the relvant papers. In addition to his updated slides, I am posting (in the additional papers below) the DeMarzo et al paper upon which his presentation was based.

  • Updated Slides for Robust Option Pricing
  • Slides for competitive secretaries

  • Additional papers/slides will be posted here. I will post related pers in chronological order of the material discussed in the presentations.
  • Mehta 2013 Online Matching and Ad Allocation survey.
  • Devanur-Mehta 2021 Online Matching in Advertisement Auctions survey.
  • Devanur et al primal dual ranking algorithm proof.
  • De Marzo et al primal paper on robust option pricing.