CS 466/666: Algorithm Design and Analysis (Fall 2023)
CS 466/666: Algorithm Design and Analysis (Fall 2023) |
|
| Lectures | Mondays and Wednesdays, 4:00 PM - 5:20PM in PHY 313 |
| Instructor | Sepehr Assadi (userid: sassadi) |
| Instructor office hours | Mondays, 2:30 PM - 3:30 PM in DC 3117 |
| Teaching assistant | Kam Chuen (Alex) Tung (userid: kctung) |
| TA office hours | Thursdays, 2 PM - 3 PM in DC 3139 |
| Prerequisites | CM 339/CS 341; Computer Science or Computational Mathematics students only |
| Textbook | There is no official textbook. Lecture notes and other required materials will be posted on this webpage. |
| Course outline | The course outline is available here. This page contains the highlights of course outline that can be updated as the term progresses. |
| Communication | The lectures will be delivered on the blackboard. We use LEARN for assignments and grades and use Piazza for general questions and discussions. For specific concerns, questions, or comments regarding your experience in the course, email me (sassadi) or Alex (kctung); just please prefix your email subject with [CS466-F23] for a timely reply. |
This is an advanced algorithm design and analysis course, aimed at undergraduate students interested in a deep dive in theoretical computer science (TCS), as well as graduate students doing research in TCS. It is more specialized and in-depth than the undergraduate level Algorithms course (CS 341). We will cover advanced algorithmic ideas (some classical, some very recent), and the theory behind them (theorems, proofs). Mathematical maturity, and a strong background in probability theory, data structures, and algorithm design are all essential.
The following is a tentative list of the topics that we will cover in this course (not necessarily in this particular order):
| • Probabilistic analysis: | Randomized algorithms, Concentration inequalities, Balls-and-bins experiments |
| • Minimum cuts: | Karger's algorithm, Vertex connectivity |
| • Minimum spanning trees (MSTs): | Boruvka's algorithm, Linear-time randomized algorithm |
| • Maximum matchings: | Hopcroft-Karp algorithm, Edmonds' algorithm, Auction algorithm |
| • Shortest paths: | Low diameter decompositions, Tree embeddings |
| • Graph compression: | Directed shortcuts, Spanners, Cut sparsifiers, Graph sketches |
| • Linear programming: | Basics, Duality, Center-of-gravity algorithm, Applications |
| • Multiplicative weight update (MWU): | Expert problem, Fast packing/covering linear programs |
| • Lovasz Local Lemma (LLL): | Basics, Algorithmic LLL |
| • Random walks: | Connectivity in RL, Perfect matchings in regular bipartite graphs, Sampling |
| • Sublinear time algorithms: | Connected components, Subgraph counting, Graph coloring |
| • Streaming algorithms: | Distinct element problem, Approximate matching, Graph sketches |
| • Distributed (LOCAL) algorithms: | Luby's Maximal Independent Set algorithm, Network decompositions |
| • Dynamic graph algorithms: | Connectivity, Approximate matching |
| • Online algorithms: | Ski rental, Karp-Vazirani-Vazirani (KVV) algorithm for bipartite matching |
| • Approximation algorithms: | Vertex cover, Set cover, Graph coloring, LP rounding |
| • Parallel algorithms: | Matching in RNC, Isolation lemma |
Official course description: Algorithmic approaches and methods of assessment that reflect a broad spectrum of criteria, including randomized algorithms, amortized analysis, lower bounds, approximation algorithms, and on-line algorithms. Particular examples will be chosen from different areas of active research and application.
I am hoping that by the end of the course, (1) you are able to design and analyze algorithms for a wide range of canonical problems studied in this course, and even more importantly, for new problems that you may have not encountered directly in this course, (2) you know a wide range of algorithmic and mathematical tools commonly used in design and analysis of algorithms, and (3) you have a have a basic familiarity with various algorithmic models of computation studied in TCS.
| ‣ Mid-term exam (take-home): | October 26, 9:00am to October 27, 9:00am | (25% points) |
| ‣ Final exam (in-person, Scheduled by the University): | Tuesday December 19, 7:30pm to 10:00pm @ PAC 7 | (25% points) |
Participation in lectures is not mandatory but I strongly encourage it -- this is a fast-moving course, so if you miss a lecture you may find it more difficult to keep up.
Important note: To pass this course, you must obtain at least 50% of the class average grade in the homework assignments and exams categories separately.| # | Date | Topics | Lecture notes & References | Assignments |
|---|---|---|---|---|
| 1 | Wednesday September 06 |
Introduction, Course policy, Probabilistic analysis, Karger's Min Cut Algorithm | [lec1], K93, KS96 | HW0 release: [HW0] |
| 2 | Monday September 11 |
Probabilistic Background, Concentration inequalities, Streaming algorithms | [lec2], discrete probability@E19, AMS96 | HW1 release: [HW1] |
| 3 | Wednesday September 13 |
Streaming distinct elements, Limited independence hash functions | [lec3], AMS96, BJKST02 | |
| 4 | Monday September 18 |
Balls-and-bins experiments: More on concentration inequalities | [lec4], Tail Inequalities@E19 | |
| 5 | Wednesday September 20 |
Balls-and-bins experiments: Power of two choices via random graph theory | [lec5], M01, KLM92 | |
| 6 | Monday September 25 |
MSTs: Basics, Fredman-Tarjan algorithm | [lec6], Minimum Spanning Trees@E19, FT87 | HW1 due HW2 release: [HW2] |
| 7 | Wednesday September 27 |
MSTs: Karger-Klein-Tarjan algorithm | [lec7], KKT95, K97 | |
| 8 | Monday October 02 |
Linear programming (LP): Basics and Applications | [lec8], Linear Programming@E19 | |
| 9 | Wednesday October 04 |
Linear Programming (LP): Duality and Integrality gaps | [lec9], Linear Programming@E19 | |
| Monday October 09 |
No class: Reading week | -- | ||
| Wednesday October 11 |
No class: Reading week | -- | ||
| 10 | Monday October 16 |
Linear Programming (LP): More on Integrality gaps, Dual fitting for set cover | [lec10], Approximation Algorithms@E19 | HW2 due |
| 11 | Wednesday October 18 |
Linear Programming (LP): Primal-dual for bipartite matching | [lec11], B88, HK73 | |
| 12 | Monday October 23 |
Online matching with a primal-dual analysis | [lec12], KVV90, DJK13 | |
| 13 | Wednesday October 25 |
Online decision making: Secretary problem, Prophet inequalities | [lec13], CFHOV18 | |
| * | Thursday October 26 |
Midterm take-home exam | ||
| 14 | Monday October 30 |
Graph sketches: Connectivity and L0-samplers | [lec14], AGM12 | HW3 release : [HW3] |
| 15 | Wednesday November 01 |
Graph compression: Spanners | [lec15], ABSHJKS20 | |
| 16 | Monday November 06* |
Polynomial identity testing, Schwartz-Zippel Lemma | [Guest lecture by Lap Chi Lau] | |
| 17 | Wednesday November 08* |
Parallel matching algorithms, Isolation lemma | [Guest lecture by Lap Chi Lau] | |
| 18 | Monday November 13 |
Multiplicative weight update (MWU): Learning from experts | [lec18], AHK12 | HW3 due HW4 release: [HW4] |
| 19 | Wednesday November 15 |
Multiplicative weight update (MWU): Matching and vertex cover LPs | [lec19], PST91 | |
| 20 | Monday November 20 |
Lovász Local Lemma (LLL): Motivation and applications | [lec20], The Local Lemma@AS16 | |
| 21 | Wednesday November 22 |
Algorithmic LLL: k-satisfiability, Entropy compression | [lec21], M09, MT10 | |
| 22 | Monday November 27 |
Asymmetric LLL: Proofs, Frugal coloring | [lec22], HMR97 | HW4 due |
| 23 | Wednesday November 29 |
Random walks: fundamental theorem of Markov chains, connectivity in RL | [lec23], Markov Chains and Random Walks@MR13 | |
| 24 | Monday December 04 |
Random walks: Perfect matching in regular bipartite graphs | [lec24], GKK10 | |
| * | Wednesday December 06 |
Pre-examination study day | -- | |
| |
There is no official textbook for the course (most of our material is not in textbooks yet anyway). The following resources are all optional but they can be quite helpful and I encourage you to refer to them throughout the term for more details on the topics we cover in the class.
For some related textbooks and surveys, you can refer to:
| MR13 | Rajeev Motwani and Prabhakar Raghavan, Randomized Algorithms. Cambridge University Press, 2013. |
| DP09 | Devdatt P. Dubhashi and Alessandro Panconesi, Concentration of Measure for the Analysis of Randomised Algorithms. Cambridge University Press, 2009. |
| AS16 | Noga Alon and Joel H. Spencer, The Probabilistic Method, 4th Edition. Wiley, 2016. |
| E19 | Jeff Erickson, Algorithms textbook. © Copyright 2019 Jeff Erickson. |
| V20 | Nisheeth K. Vishnoi, Algorithms for Convex Optimization. © Copyright 2020 Nisheeth K. Vishnoi. |
| AHK12 | Sanjeev Arora, Elad Hazan, Sagar Kale, The Multiplicative Weights Update Method: a Meta-Algorithm and Applications. Theory of Computing, 2012. |
| ABSHJKS20 | Abu Reyan Ahmed, Greg Bodwin, Faryad Darabi Sahneh, Keaton Hamm, Mohammad Javad Latifi Jebelli, Stephen G. Kobourov, Richard Spence, Graph spanners: A tutorial review. Computer Science Review 2020. |
This is a (rather incomprehensive) list of the papers related to the topics discussed in the lectures. The list will be updated frequently throughout the term.
| AGM12 | Kook Jin Ahn, Sudipto Guha, Andrew McGregor, Analyzing graph structure via linear measurements. SODA 2012. |
| AMS96 | Noga Alon, Yossi Matias, Mario Szegedy, The Space Complexity of Approximating the Frequency Moments. STOC 1996. |
| BJKST02 | Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, D. Sivakumar, Luca Trevisan, Counting Distinct Elements in a Data Stream. RANDOM 2002. |
| B88 | Dimitri P. Bertsekas, The auction algorithm: A distributed relaxation method for the assignment problem. Annals of Operations Research 88. |
| CFOV18 | Jose Correa, Patricio Foncea, Ruben Hoeksma, Tim Oosterwijk, Tjark Vredeveld, Recent Developments in Prophet Inequalities. SIGecom Exchanges 2018. |
| DJK13 | Nikhil R. Devanur, Kamal Jain, and Robert D. Kleinberg, Randomized Primal-Dual Analysis of RANKING for Online Bipartite Matching. SODA 2013. |
| FT87 | Michael L. Fredman and Robert E. Tarjan, Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms. JACM 87. |
| GKK10 | Ashish Goel, Michael Kapralov, Sanjeev Khanna Perfect Matchings in O(n log n) Time in Regular Bipartite Graphs. STOC 2010, SICOMP 2013. |
| HMR97 | Hugh Hind, Michael Molloy, and Bruce Reed, Colouring a Graph Frugally. Combinatorica 1995. |
| HK73 | John E. Hopcroft and Richard M. Karp, An n^{5/2} Algorithm for Maximum Matchings in Bipartite Graphs. SICOMP 1973. |
| M01 | Michael Mitzenmacher, The Power of Two Choices in Randomized Load Balancing. IEEE TPDS 2001. |
| K93 | David R. Karger, Global Min-cuts in RNC, and Other Ramifications of a Simple Min-Cut Algorithm. SODA 1993. |
| KKT95 | David R. Karger, Philip N. Klein, Robert Endre Tarjan, A randomized linear-time algorithm to find minimum spanning trees. JACM 1995. |
| KS96 | David R. Karger and Clifford Stein, A New Approach to the Minimum Cut Problem. JACM 1996. |
| KLM92 | Richard M. Karp, Michael Luby, Friedhelm Meyer auf der Heidet, Efficient PRAM Simulation on a Distributed Memory Machine. STOC 1992. |
| KVV90 | Richard M. Karp, Umesh V. Vazirani, Vijay V. Vazirani, An Optimal Algorithm for On-line Bipartite Matching . STOC 1990. |
| K97 | Valerie King, A Simpler Minimum Spanning Tree Verification Algorithm. Algorithmica 1997. |
| M09 | Robin Moser, A Constructive Proof of The Lovasz Local Lemma. STOC 2009. |
| MT10 | Robin Moser and Gabor Tardos A Constructive Proof of The General Lovasz Local Lemma. JACM 2010. |
| PST91 | Serge A. Plotkin, David B. Shmoys, Éva Tardos, Fast Approximation Algorithms for Fractional Packing and Covering Problems. FOCS 1991. |
This is a list of some other closely related courses or other offering of the same course at Waterloo and elsewhere:
You can download LaTeX for free. For the purpose of this course, you do not even need to install LaTeX and can instead use an online LaTeX editor such as Overleaf.
Two great introductory resources for LaTeX are Getting started with TeX, LaTeX, and friends by Allin Cottrell (for general purpose LaTeX) and LaTeX for Undergraduates by Jim Hefferson (for undergraduates mathematics) accompanied by the following cheatsheet (note that this document use "\( MATH \)" notation compared to the perhaps more widely used "$ MATH $" -- both are completely fine in LaTeX). You can also use this wonderful tool Detexify by Daniel Kirsch for finding the LaTeX commands of a symbol (just draw the symbol!).
If you are interested in learning more about LaTeX (beyond what is needed for this course), check the Wikibook on LaTeX and the Wikibook on LaTeX for Mathematics.
The University of Waterloo acknowledges that much of our work takes place on the traditional territory of the Neutral, Anishinaabeg and Haudenosaunee peoples. Our main campus is situated on the Haldimand Tract, the land granted to the Six Nations that includes six miles on each side of the Grand River. Our active work toward reconciliation takes place across our campuses through research, learning, teaching, and community building, and is co-ordinated within the Office of Indigenous Relations.
Email is fast and tends to give the illusion of constant and immediate access. But that cannot realistically happen. I am available to you in general during this course via email but it may take up 24 hours (48 hours over the weekends) before you hear back from me. Also, please use email only to communicate specific concerns, questions, or comments regarding your experience in the course, or setting up appointments for in-person meetings outside office hours in case necessary. Questions directly related to the materials of the course and clarifications about lectures should be posted on Piazza or discussed during office hours instead.
Important note: Please start the subject of all your emails in this course with '[CS466-F23]' (like "[CS466-F23] discuss my final grade") -- I am using bunch of different email filters to manage my (unmanageable) inbox and I may not get to see emails without this format at all or there is no guarantee on response time for such emails.
You are encouraged to discuss with me any appropriate accommodations that we might make on your behalf following the guidelines of the AccessAbility Services.
AccessAbility Services, located in Needles Hall, Room 1401, collaborates with all academic departments/schools to arrange appropriate accommodations for students with disabilities without compromising the academic integrity of the curriculum. If you require academic accommodations to lessen the impact of your disability, please register with AccessAbility Services at the beginning of each academic term.
This is a challenging course with various advanced topics and not-so-easy assignments and exams. All of these are going to be time and energy consuming. But, this is also an elective course so one of my main goals is for you to enjoy taking this course and learning these cool materials as much as I enjoy teaching them. Part of making sure you have fun involves taking care of yourself. Do your best to maintain a healthy lifestyle and work-life balance this term by eating well, exercising, getting enough sleep, and taking some time to relax -- all of these will tremendously help you to achieve your goals in the course and to enjoy the process in the meantime.
You can find more resources to help you with your health & well-being with the Campus Wellness and Student Success Office -- they have tons of resources on helping you to succeed, including very good tips on time management techniques.
Faculty of Math Statement on Mental Health: The Faculty of Math encourages students to seek out mental health support if needed:
On-campus Resources:Every member of this class---instructor, TA, and students---has rights and responsibilities toward having a pleasant, fair, supportive, and free of discrimination and micro-aggression environment in this course, and we are all answerable to the University policies governing ethical behaviour (Policy 33).
In addition, academic dishonesty and plagiarism is considered a serious offense in this course. I expect that any assignment or exam you submit in this course will be your own product and follows the collaboration and external resources policies specified in the course outline. If an assignment is too hard, start earlier, ask for help, or simply do not answer the question --- academic dishonesty is never the right answer. If you have any concerns or questions about these policies, please discuss them with me.
Finally, a reminder that all the course content including lecture notes, presentations, and other materials prepared for the course, are the intellectual property (IP) of the instructor. These course materials are available to you to enhance your educational experience, and sharing them without permission and proper citation is a violation of intellectual property rights.
University Policies: It is your job to know the university policies that govern your behaviour in this course. Some pointers are:Course materials and the intellectual property contained therein, are used to enhance a student’s educational experience. However, sharing this intellectual property without the intellectual property owner’s permission is a violation of intellectual property rights. For this reason, it is necessary to ask the instructor, TA and/or the University of Waterloo for permission before uploading and sharing the intellectual property of others online (e.g., to an online repository).
Permission from an instructor, TA or the University is also necessary before sharing the intellectual property of others from completed courses with students taking the same/similar courses in subsequent terms/years. In many cases, instructors might be happy to allow distribution of certain materials. However, doing so without expressed permission is considered a violation of intellectual property rights.
Please alert the instructor if you become aware of intellectual property belonging to others (past or present) circulating, either through the student body or online. The intellectual property rights owner deserves to know (and may have already given their consent).
Use of Generative Artificial Intelligence: The following statement is prepared by the Office of Academic Integrity with input from the Centre for Teaching Excellence, Library, and consultations with Associate Deans and members of the Standing Committee on New Technologies, Pedagogy, and Academic Integrity (Last Updated: August 2023):Generative artificial intelligence (GenAI) trained using large language models (LLM) or other methods to produce text, images, music, or code, like Chat GPT, DALL-E, or GitHub CoPilot, may be used for assignments in this class with proper documentation, citation, and acknowledgement. Recommendations for how to cite GenAI in student work at the University of Waterloo may be found through the Library.
Please be aware that generative AI is known to falsify references to other work and may fabricate facts and inaccurately express ideas. GenAI generates content based on the input of other human authors and may therefore contain inaccuracies or reflect biases. In addition, you should be aware that the legal/copyright status of generative AI inputs and outputs is unclear. Exercise caution when using large portions of content from AI sources, especially images. More information is available from the Copyright Advisory Committee.
You are accountable for the content and accuracy of all work you submit in this class, including any supported by generative AI.
Created & maintained by Sepehr Assadi