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

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 (and references in these sourses):

  • 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
  • Nikhil Bansal's Randomized Algorithms Course

    • Lecture slides will be posted here.
  • Week 1 Motivating the course and starting to introduce basic combinatorial paradigms. Online algorithms, greedy algorithms.
  • Week 2 Alternative machine models and the makespan prolem, the proportional weights and general knapsack problem, randomized online algorithms with and without revoking
  • Week 3 Proving inapproximations for randomized online algorithms, the priority algorithms model. Some priority algorithm approximations and charging arguments.
  • Week 4 Proving inapproximations for deterministic priority algorithms. Begin local search. Exact max-k-sat, oblivious and non-oblivious local search algorithms for max-2-sat. Not in slides was a quick blackboard discussion of the naive randomized algorithm for max-k-sat and how to view max flow as a local search algorithm. the priority algorithms model. Some priority algorithm approximations and charging arguments.
  • Week 5 The proof for the non-oblivious Exact Max-2-Sat problem, k set packing and local search, metric facility and k median problems, submodular functions.
  • Week 6 Oblivious and non-oblivious local search for monotone submodular maximization subject to aa matroid constraint, randomization as a paradigm, polynomial identity testing and the Schwartz-Zipple Lemma, Max-Sat and the de-randomization of the naive randomized online algorithm as Johson's algorithm.
  • Week 7 Johnson's algorithm for MaxSat, a modified Johnson's algorithm and its canonical randomization, the double-sided greedy algorithm for unconstrained submodular maximizmation, derandoizing the 3/4 commpetitive ratio as 2n parallel algorithms. Online bipartite matching, the KVV Ranking algorithm.
  • Week 8 Online bipartite matching, ROM c-competitiveness implies c-competitveness in the unknown i.i.d. model. Some results for bipartite matching with i.i.d. inputs, Adwords and Display Ads, Max-2-Sat by vector programming, the random walk algorithm for Max-2-Sat.
  • Week 9 The random walk algorithm for Max-2-Sat, Markov chains, uniform walks on a graph, random walk algorithm for k-Sat, fine-grained complexity, primality testing, set cover and vertex cover.
  • Week 10 The dual of an LP, strong and weak duality, a primal dual algorithm for the f-frequency weighted set cover problem, dual fitting analysis of the greedy algorithm for weighted set cover problem,. The streaming and semi-streaming models, heavy hitters, frequency meoments
  • Week 11 The CVM estimator for the number of distinct elements in a stream. Sublinear time algorithms.
  • Week 12 Combining brute force with divide and conquer for 3Sat, the LST IP/LP for the makepsan problem in the unrelated machines model, the weighted majority algorithm, vector progams with cardinality constraints, the densest subgraph problem and Chazelle's reverese greedy algorithm.

    • 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 1, reposted September 28 The assignment is now complete.
  • Assignment 2 Assignment 2
  • Assignment 3 Assignment A3 Assignment 3 is now complete as I have posted (on November 27) a final question relating to Sch\"{o}ning's random walk algorithm for 3SAT.
    • Additional papers/slides will be posted here.
  • Probability Primer
  • Denis Pankratov LP theory and LP duality slides.
  • Kaplan-Zwick Mutlipicative Weights slides.
  • 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 (highlighting application to online advertising) 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 hierarchies 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, 2023) 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 the end of the calendar year 2023.
  • Ambitious Tentative Table of Contents.