CSC2420 (Algorithm Design, Analysis and Theory) Home Page (Fall 2017)
This page will provide WWW access to various documents concerning CSC2420.
Announcements will also be made on
this page.
The class will be held Wednesdays 11-1 in BA 2179.
Please send any comments or questions to the instructors:
Allan Borodin bor..at..cs.toronto.edu and Nisarg Shah nisarg..at..cs.toronto.edu
Announcements will be placed here as appopriate.
Assignment 1 is due October 18, 1PM on Markus. The link to Markus is https://markus.teach.cs.toronto.edu/csc2420-2017-09/
The full assignment 2 is posted. It is due on November 22, by 11am (before the class starts). Please submit A SINGLE PDF on MarkUs.
Assignment 3 has been posted. It is due on December 6, by 11:59pm. Please submit A SINGLE PDF on MarkUs.
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. Other possible topics include:
online algorithms (adversarial and stochastic models), the random order online
model,
derandomizing online algorithms,
submodular
maximization,
LP and SDP relaxations,
primal dual algorithms,
sublinear time algorithms,
parameterized complexity, fine grained complexity,
data stream algorithms, MapReduce 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:
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.
Lecture 1
Motivating the course and starting to introduce basic combinatorial paradigms. Online algorithms, greedy, partial enumeration greedy
Lecture 2
Further discussion of greedy and greedy like algorithms. The priority model and extensions. Proving an inapproximation. Interval selection, set packing, set cover, vertex cover.
Lecture 3
Finish discussion of greedy and greedy like algorithms. The priority stack model. Interval colouring and the vertex min colouring problem. m-machine interval scheduling. Begin dynamic programming (DP). Weighted interval scheduling. Pseudo polynomial DP algorithms for the knapsack problem and an FPTAS. The priority branching tree pBT model .
Lecture 4
Different styles of DP algorithms. Shortest path problems.The all pairs shortest path problem and its role in fine grained complexity. Using DP to improve the exponential time for the TSP problem. Matrix chain problem. The Baptiste DP for a special case of the throughout maximization problem. Begin local search. Local search for max-cut problem. Oblivious and non-oblivious local searchi for Max-Sat problem.
Lecture 5
Finish up discussion of local search. Max flow, Ford Fulkerson max flow-min cut theorem and algorithm; applications of max flow-min cut. Start IP/LP discussion.
Lecture 6
IP/LP for makespan. Introduction to LP duality, primal dual algorithms,
dual fitting. Introduction to randomization. De-randomizing the naive
randomized algorithm for Max-Sat and Johnson's algorithm.
Lecture 7
Online randomized algorothms for Max-Sat. The Yannakakis randomized
LP rounding. The Buchbinder et al 2-sided online algorithm for unconstrained
non-monotone submodular maximation. To what extent can these randomized algorithm be de-randomized? The KVV randomized algorithm for online bipartite matching. The relation between randomized online algorithms and deterministic online algorithms with advice. Two pass online algorithms for Max-Sat and bipartite matching.
Lecture 8 Two different proofs of the RANKING algorithm for online bipartite matching (the combinatorial proof of Birnbaum and Mathieu, and the LP rounding proof of Devanur et al.), Papadimitriou's random walk algorithm for 2-SAT, Schoning's generalization for k-SAT, comments about random walks on graphs.
Lecture 9 Starting sublinear time algorithms: deterministic+inexact - approximating diameter in a metric space, randomized+exact - tight bound for searching in a sorted list, randomized+inexact - estimating average degree in a graph, estimating size of maximal matching, starting property testing - testing linearity of a Boolean function.
Lecture 10 Finishing sublinear time algorithms: testing monotonicity of array and bipartiteness of graphs, starting streaming algorithms: missing element(s), frequency moments, majority element
Lecture 11 Finishing streaming algorithms: k-heavy hitters through Misra-Gries algorithm and through Count-Min sketch, a note about semi-streaming model, online expert learning: weighted majority, randomized weighted majority, learning disjunctions (arbitrary, r-way, k-of-r).
Lecture 12 Applications of algorithmic ideas to game theory and social choice theory; minimax theorem via online expert learning; cake cutting; fair allocation of indivisible goods.
Assignments will be posted here.
Assignment 1
Assignment 2
Assignment 3
Additional papers/slides will be posted here.
Kim Larsen's slides regarding
alternative online models and measures
The FPT slides by Daniel Marx:
Marx Lecture 1 ;
Marx Lecture 2 ;
Marx Lecture 3 ;
Marx Lecture 4
Here is Virginia Williams' paper on
fine-grained complexity
Dan Spielman's
tutorial on spectral graph theory