CSC2421 Topics in Algorithms: Online and other Myopic Algorithms (Fall 2025)

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

bor..at..cs..toronto.edu

While the title "Online and Other Myopic Algorithms" may seem very specialized, the course should be accessible to any CS student and also serves as a partial introduction to many of the topics in CSC2420. The course will be based on a itwo volume text (co-authored with Denis Pankratov). Volume 1 was completed May 2026 and will appear online hopefully by January 2027. Volume 2 will hopefully be completed by summer 2026. It is a reasonably self-contained text for anyone who has the equivalent of our CSC373 undergraduate course. I have uploaded Volume 1 on Quercus for class use. I will upload Volume 2 after a few uopdates. Howevere, Volume 2 is far from complete.

The adjective ``myopic'' implies algorithms where we do not see all the input items in advance; that is, after processing the first i items we have limited knowlegde about item i+1 and other future items. We will take a broad view of this term and (for example) will include (for example) algorithms that have some limited ability to change past decisions and we will consider both worst case and stochastic inputs. We will also consider algorithms that use predictions and altrenative measures of performance.

The topic of online myopic algorithms is of growing interest due to the increasing number of applications. We will consider various applications such auctions, fair division, scheduling, max-sat and graph algorithms, as well as some abstract algorithmic frameworks such as the k-server problem.

The table of contents for Volume 1 is provided here.

A draft table of contents for Volume 2 is provided here.

There are a number of excellent undergraduate texts (e.g. "Algorithm Design" by Jon Kleinberg and Eva Tardos; "Introduction to Algorithms" by Corman, Leiserson, Rivest and Stein; ``Algorithmics: Theory and Practice" by Brassard and Bratley; and "Algorithms" by DsGupta, Papadimitriou and U. Vazirani) that cover the standard topics and include some advanced material. There are also a number of texts on somewhat specialized topics (e.g. "Approximation Algorithms" by V. Vazirani; "A First Course in Combinatorial Optimization", by James Lee; and "Randomized Algorithms" by Motwani and Raghaven). There are also 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: