Announcements
Syllabus
Logistics: The instructor for this course is me, Professor Zlatin. We meet on Tuesdays and Thursdays from 1:15 - 2:30pm in Estella 1249. My office hours are on Mondays from 10:30 - 11:30am, Thursdays 2:40 - 4:00pm, and by appointment in Edmunds 223. I am happy to talk about the class, CS theory or whatever is on your mind. The best way to reach me is by email. There will also be a course Slack channel. The TAs for the course are Kartika Santoso and Cole Uyematsu.
Course Description: Did you enjoy your first algorithms course and want to go deeper? Then this course is for you! We will cover a range of topics which have become fundamental tools in the design of modern algorithms.
We begin by studying widely applicable network optimization problems. We will then go beyond the realm of exact algorithms and learn how to approach problems which are known to be intractable, or for which we only have partial information.
The class will culminate in a course project.
This class has CS 140 as a prerequisite. It is also focused on algorithm design and analysis, not implementation. Please send me an email if you are considering enrolling and have any questions.
Deliverables: Most weeks, I will put out a set of exercises accompanying the material for that week. These will be graded for completion/effort and correctness: half of the points are achieved by turning something in with a genuine effort. In addition, there will be three or four assignments in the course. These will typically consist of around four or five challenging problems which will test your understanding of the material and creative problem solving skills. Finally, there will be a course project and associated milestones. The grading breakdown is as follows:
- Participation – 5%
- Exercises – 25%
- Assignments – 50%
- Project milestones – 5%
- Final project – 15%
Course Project: The final project will consist of a deep dive into some aspect of algorithms, as well as a presentation of your findings. There are two main directions you can take.
One is to choose some algorithmic problem which we didn't get to cover in class (and there are many cool ones), learn about the motivation for the problem, the history, and state-of-the-art methods for its solution.
The second option is to select some computational task or applied problem and implement one or more algorithms to solve it. How do different algorithms compare in theory and in practice in terms of speed, memory usage, quality of solution, or fairness?
I have compiled a list of good project choices here. Of course, this is your project so feel free to get creative! Students can work by themselves or form groups of up to two.
- Algorithm Design, by Jon Kleinberg and Eva Tardos.
- The Design of Approximation Algorithms, by David Williamson and David Shmoys.
- A Second Course in Algorithms, by Tim Roughgarden.
Schedule
This is the course calendar, which will be populated over time with lecture notes and associated readings. You can get a sense of the complete calendar by looking at a previous iteration of the course here. KT refers to Algorithm Design by Kleinberg and Tardos.| Date | Topic | Readings | Due |
|---|---|---|---|
| Part 1 · Network Optimization | |||
| 01/20 | Welcome to the course | slides | Welcome survey |
| 01/22 | Stable Matchings | KT 1.1, GS paper, slides | |
| 01/27 | Maximum Flows, Ford-Fulkerson algorithm | KT 7.1, flow notes, FF demo | Exercise set 0 |
| 01/29 | Max-Flow Min-cut Theorem | KT 7.1, flow notes | |
| 02/03 | Image segmentation | slides | Exercise set 1 |
| 02/05 | Pseudo-polynomiality and faster flows, Push-relabel | KT 7.3-7.4, handout, video, original paper | |
| 02/10 | Exercise set 2 | ||
| 02/12 | |||
| 02/17 | Assignment 1 | ||
| Part 2 · Combinatorial Optimization | |||
| 03/17 | Spring Break | ||
| 03/19 | Spring Break | ||
| Part 3 · Dealing with Intractability | |||
| Part 4 · Dealing with Uncertainty | |||
| Final Project Presentations | |||
| 04/30 | |||
| 05/05 | |||
| 05/12 | Final Report due | ||
Policies
Please let me know as early as possible if you cannot attend class. If you want to meet outside of office hours, write me an email or come to my office - if I am there I will answer your questions. Any feedback, concerns, or suggestions are more than welcome. You can email me, come to my office or submit feedback through this anonymous form . If you need accommodations, please contact the Disability Coordinator on your home campus. The process for Pomona students is available here. If you feel overloaded with the amount of work for this course, or are feeling burned out, I encourage you to contact me so that we can address the concerns together. You are probably not alone in feeling that way, and I am here to help.
Exercises
These will be released over the course of the semester.
- Exercise set 0, Latex template here.
- Exercise set 1, Latex template here.
- Exercise set 2, Latex template here.
Assignments
These will be released over the course of the semester.
- Assignment 1, Latex template here.