CSC2420 (Algorithm Design, Analysis and Theory) Home Page (Fall, 2022)

This page will provide WWW access to various documents concerning CSC2420. Announcements will also be made on this page but mostly we will use Quercus for announcements.

Please send any comments or questions to the instructor:
Announcements will be placed here as appropriate.

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. Some possible topics include: stochastic models, the random order online model, derandomizing online algorithms, LP rounding, primal dual algorithms, sublinear time algorithms, parameterized complexity, fine grained complexity, data stream algorithms, multiplicative weights algorithm, algorithmic 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:

  • Tim Roughgarden Stanford Lectures
  • Princeton University CS521
  • University of Washington CSE 521
  • University of Washington CSE 522
  • Cornell University CSC6820
  • CMU 451/651
  • 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 algorithms. Reposted September 25. Material after we ended on September 14 will appear in the sldies for L2
  • Week 2 of class, Week 3 of course. Brief introduction to online bipartite matching. Scheduling anomolies. The knapsack problem. The prioirty model for greedy and myopic algorithms.
  • Week 3 of class. Calum's slides for online bipartite matching
  • Week 4 of class. Priority algorithms and their limitations.
  • Week 5 of class. Finishing up greedy/priority algorithms. Begin local search.
    • Note: L6 was the completion of the online bipartite matching discussion.
  • Week 7 of class. Local search. Ranomized algorithms.
  • Week 8 of class. Randomized algorithms. The naive randomized agorithms for polynomial identity testing, max-sat, max-cut and max-di-cut. Randomized rounding of an LP, the doulble sided randomized greedy algorithm for non-monotone submodular maximization, de-randomization.
  • Week 9 of class. Vector program for Max-2-Sat. 2-SAT in polynomial time. Improved run times for 3-SAT and $k-SAT$. Begin sublinear time algorithms. Reposted November 24.
  • Week 10 of class. Continue sublinear time algorithms. Sublinear space and the streaming model.
  • Week 11 of class. Continue streaming algorithms. The weighted majority algorithm. Primality testing. Reposted December 7.

    • Assignments will be posted here. There will most likely be three or four assignments. Given the number of students who are initially enrolled, we might allow submissions from pairs of students so as to make the grading manageable. I would also entertain individuals doing a project on some specific topic instead of doing the assignments. We will finalize the course requirement after a week or two in order to see what the actual enrollment will be.

  • Assignment 1 (Assignment is now complete.)
  • Assignment 2. (Assignment 2 is now complete.)
  • I added a third question for Assignment 3. Posted November 28.
    • 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.
  • Here is the Gupta and Tangwongsan paper concerning local search algorithms for UFL and K-medians.
    • Here is the Meyerson paper concerning an online algorithm for the UFL problem in both a model where all clients can be facilities and a model where the facilities and clients are distinct sets.
  • The seminal KVV paper regarding online bipartite matching and the Ranking algorithm.
  • The 2013 survey by Aranyak Mehta concerning Online Matching and Allocation. 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
  • Here is Periklis Papakonstantinou's paper on hieraarchies of priority algorithms that considers hierarchies based on whether the algorithm is adaptive priority or not, greedy or not, and memoryless or not. Priority algorithm hierarchies
    • Here is the table of contents (dated September 20, 2022) of this text when we had a very ambitious agenda. We now intend to shorten the text to something a little more manageable in order to hopefully complete the text by sunmmer 2023.
  • Ambitious Table of Contents to be shortened.