CSC2420 (Algorithm Design, Analysis and Theory) Home Page (Spring 2019)
This page will provide WWW access to various documents concerning CSC2420.
Announcements will also be made on
this page.
NOTE: I have had a couple of requests for an extension with regard to the last assignment. I am willing to do this but I have to get grades in for undergraduate students and Chris is away next week. So, I will grant an extension for the last assignment until Thursday, April 11. All assignments should be submitted electronically to me and with a copy to Chris (ckar at cs.toronto.edu). If you want to submit this Thursday that will faciliate our grading. You can revise any "early" submissions up to the due date. THE TOPIC REVIEW IS STILL DUE THIS THURSDAY, APRIL 4.
Presentations are scheduled for this Thursday. If you intend to use slides (which is probably a good idea), then please send me a file that I can upload to save time.
NOTE: I discussed the nature of the reading project assignment. Namely, you are asked to write a survey type paper on a topic relevant to this course. For example, as I mentioned, you could take any of the chapters mentioned in the index of the online text draft and help develop the material in that chapter. In some cases, even a section within a chapter is a topic of substantial interest. But you are not restricted to these topics.
I think everyone by now has a project. The presentation next week will make up a small part (say 10%) of the grade for the project with 90% based on the writen project.
I have now posted all the questions for the final assignment.
Please send any comments or questions to the instructor:
Announcements will be placed here as appopriate.
This course serves as a foundational course,
appropriate for students in computer science, computer engineering,
and mathematics. However, the course should also be of
interest to ``theory students'' looking for research topics.
We will begin with topics usually discussed in
undergraduate courses such as our CSC373/CSC375 using some less standard
examples and also discussing some precise models for
standard algorithmic paradigms such as greedy, local search and
dynamic programming algorithms.
This term there will be an emphasis on online, online-like algorithms and
``beyod wirst case analysis". Some possible topics include:
stochastic models, the random order online
model,
derandomizing online algorithms,
submodular
maximization,
primal dual algorithms,
sublinear time algorithms,
parameterized complexity, fine grained complexity,
data stream algorithms,
multiplicative weights algorithms,
algorithmic aspects of mechanism design,
We will not use any one text book for this course. 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:
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
Lecture slides will be posted here.
Week 1
Motivating the course and starting to introduce basic combinatorial paradigms. Online algorithms, greedy, partial enumeration greedy
Week 2
The priority model for greedy and myopic algorithms, inapproximations in the priority framework. Interval selection. Charging arguments. Some extensions of the online and priority models. Set packing and s-set packing.
Week 3
Set packing continued. (s+1)-claw free graphs. The job interval scheduling problem. Approximation algorithms for set cover and vertex cover. Priority algorithms with revocable acceptances and priority stack algorithms. Chordal graphs, perfect elimination orderings, k-PEOs and inductive k-independent graphs.
Week 4
Chris' slides for online learning
Week 5
Local search. Oblivious and non-oblivious local search for exact max-k-sat, local seacrh for k-claw free graphs, matroids and indepoendence systems, maximizing modular and submodular functions subject to a matroid constraint.
Week 6
Finish oblivious and non-oblivious local search for
maximizing monotone
submodular functions subject to a matroid constraint. Randomized algorithms and in particular online randomized algortithms.
Week 7
The Yannakakis randomized rounding algorithm for max-sat. The Buchbinder et al deterministic and randomized ``double-sided online algorithms'' for the unconstrained (non-monotone) submodluar maximization (USM) problem. The adaption to max-sat and the Poloczek et al presentation of the randomized online max-sat algorithm. (See also chapters of online text draft.)
Week 8. There are no lecture slides for this week. Chris gave a blackboard lecture dicussing the ADWORDS problem and the DISPATCH paper.
I am posting the Mehta survey article (which discusses the ADWORDS problem)
and the DISPATCH paper.
Week 9
Proof sketch for 1/2 competitive ratio of the randomized double-sided greedy algorithm for the USM problem. The corespondence between the USM result and the
3/4 randomized algorithm for max-sat. Brief discussion of primal dual algorithms and primal dual based analysis. Start of discussion of stochstic input models.
Week 10
More discussion on ROM model. Random walk algorithm for 2-sat and k-sat. Start of sublinear time algorithms.
Week 11
Sublinear time algorithms, often conceptually very simple but deceptively hard to analyze. Streamng algorithms.
Assignments will be posted here.
The due date for A1 was February 25, the last day to drop a graduate course without penalty.
Assignment 2 is the reading project on a topic of your choice.
I have now posted all questions for the final assignment. The due date is April 4, the last class of the term.
Assignment 1
Final Assignment
Additional papers/slides will be posted here.
Probability Primer
Kim Larsen slides
The FPT slides by Daniel Marx:
Marx Lecture 1 ;
Marx Lecture 2 ;
Marx Lecture 3 ;
Marx Lecture 4
Here is Virginia Williams
fine-grained complexity
Here is the Khanna et al paper concerning
local search algorithms for exact max-k-sat.
The seminal KVV paper regarding
online bipartite matching and the Ranking algorithm.
The 2013 survey by Aranyak Mehta concerning Online Matching and Adllocation. This is an excellent survey but of course not totally up to date.
Mehta survey.
The Chang et al DISPATCH algorithm paper for Maximum Online Perfect Bipartite Matching with i.i.d. Arrivals.
DISPATCH algorithm.
Here are 2009 Lecture Notes on Data Stream Algorithms by Amit Chakrabarti.
He has more recent 2011 and 2015 courses on Data Stream Algorithms.
Data Stream Lecture Notes
Preliminary versions of some chapters from our new ``Online Algorithms'' text will be posted here. We are just beginning this text so there are bound to be mistakes and incomplete references. We welcome any comments.
Here is a draft (posted March 14) of our index and Chapters 1-4 and 7,8 but missing most references and historical notes. And as noted before, all of the chapters are still being written.
Chapters 1,2,3,4,7,8
Here is a draft of the current bibliography for some chapters. Even for chapters where we have some references, the history is far from comoplete.
Current bibliography.