15-850: Advanced Algorithms, Spring 2023: Course Policies

Description

An intensive graduate course on the design and analysis of algorithms. This course is primarily aimed at graduate and advanced undergraduate students interested in doing research in theoretical computer science. It is more specialized and in-depth than the graduate level Algorithms in the Real World course (15-750), and the undergraduate/masters' level Algorithms course (15-451/651). We will cover advanced algorithmic ideas (some classical, some very recent), and the theory behind it (theorems, proofs). For topics that were covered in 451/750, the goal is to cover advanced content, proofs, and new techniques.

Syllabus

1. MSTs. Recap Prim/Kruskal/Boruvka, an \(O(m \log^\star n)\) time algorithm, a randomized linear-time algorithm, MSTs in directed graphs
2. Shortest paths. recall Dijkstra/Bellman-Ford/etc, Seidel's algorithm using matrix multiplication, recent near-linear time algorithm with negative-weight edges.
3. Matchings: classical matchings using augmenting paths, matching using matrix inversions (Tutte/Lovasz, Mucha-Sankowski), matchings using random walks, matchings using matrix balancing.
4. The Experts algorithm via multiplicative weights, online gradient descent.
5. Flows: max-flows via electrical flows, Sherman's near-linear time max-flow.
6. Linear and Convex Programming
• Solving convex optimization problems via gradient descent, ellipsoid, interior-point methods
• Using convex optimization to solve combinatorial problems (maybe)
7. High-dimensional geometry: Dimension reduction and singular value decompositions.
8. Fixed-parameter tractable algorithms.
9. Streaming algorithms (a.k.a. algorithms for big data)
10. Online algorithms
11. Approximation Algorithms
12. The Sums-of-Squares Paradigm
13. Submodular Optimization

Effort and Criteria for Evaluation:

We have 3 lectures a week for the first ~10 weeks of the semester. Attendance is required: it's a fast-moving course, so if you miss lecture you may find it more difficult to keep up. We have ~7 HWs (including HW0). Your grade will depend on these HWs, class participation, and attendance.

We may record the lectures. However, I recommend you attend the lectures in person when possible, and use these recordings to recap the material, or to catch up in case you need to miss some lectures.

Textbook:

There is no textbook for the course. Most of our material is not in textbooks (yet), so we will rely on lecture notes, papers and monographs. We will provide you with lecture notes; we appreciate feedback and suggestions for improvements.

Homeworks:

Some of the homeworks, some solved in collaboration (groups of two, or at most three, please), and the others solved individually. Homeworks are due at 11:59pm on the due date. They must be submitted via gradescope. For each homework, there will be a two-day (48 hours) no-questions-asked extension. Students can use this extension for any valid reason without having to ask the course staff. We do not plan to provide additional extensions (barring exceptional circumstances).

Collaboration policy: On solo homeworks (like HW0) you must solve all the problems yourself. You must not discuss the problems with others. On other collaboration HWs (like HW1) we permit--in fact, we encourage--groups of two people (3 if you must). We require that collaborations be "whiteboard" collaborations, you can discuss problems and solutions with your group on a "whiteboard". After this each person should go away and write their own solutions, which they then submit. That is, collaboration should be limited to *talking* about the problems, so that your write-up is written entirely by you. No written work should be shared. Of course, you must also list all members of your group. In all cases if you use any resources not on the course webpage, you should cite them. Use Piazza to form groups if you like.

You should ideally typeset your solutions, it makes grading much easier for the TAs. But you can write and scan your HWs, as long as you make them as legible as possible, please. Also, please aim for clarity and conciseness in your solutions. Please cite all collaborations and sources.

Prerequisites:

You should know material in standard UG courses in algorithms, probability, and linear algebra very well. Above all, mathematical maturity/curiosity and problem-solving skills are a must. That way you can make up for gaps in your knowledge yourself. It is natural to not know everything, or for you to get rusty on concepts, but you must learn how to learn. This may seem vague, so here are concrete things.

• Here are links to some resources for algorithms, probability, and linear algebra.
• You should know material from an undergraduate Algorithms course, say until Lecture 16 (P/NP) from our Spring 2018 version of 15-451. You should definitely know dynamic programming, flows, basics of linear programming and LP duality, NP-hardness, etc. If not, please pick these up from the 451 lecture notes/textbooks/Wikipedia/etc (see resources above).
• Same for undergraduate probability and linear algebra courses. E.g., for LinAlg, see whether you can solve the first homework from Steve Vavasis' Optimization course at Waterloo (you can skip the coding if you want), we will add some more exercises here. For probability (and randomized algorithms), I will add some exercises as well, and will give some problems in HW0.
• HW0 will make an attempt to test this preparedness, and to give you and us feedback.

FAQs:

• Q: Will you give the real-world context for the algorithms you cover?
  Not much. We will focus on the theoretical side (think: algorithms, techniques, theorems, proofs), so we will not have much time to motivate the choice of topics or give much real-world context (of which there is plenty). If you are looking for the latter, you should consider taking 15-750: Algos in the Real World (older versions here) which is aimed at a broader audience, and is being offered in Spring 2023 as well.


• Q: I am on the wait-list: will I get in?
  We hope everyone who wants to take the class will get in. (Usually some students are "shopping around" in the first couple weeks, and things settle down after that.) Just attend the lectures, and we will try to get clear the wait-lists soon. OTOH, if you are on the wait-list because you have too many credits, or are enrolled for a course with a conflicting time-slot, you should fix those issues yourself.


• Q: I am struggling with the homework: what should I do?
  A little struggle in doing the homework is expected (and healthy), since these are not trivial problems, you're probably learning something new. Think about the problem, bounce ideas around (with your team-mates or the course staff), think some more, and repeat until you have a solution. Of course, make sure you are putting in the time to think. Working with others is a good way to learn too, with the usual caveats. However, if you are struggling a fair bit, and if the struggle is unpleasant for you, come talk to us. You may consider taking 15-451 (UG Algos) or 15-750 (Algos in the Real World) instead of this course.


• Q: Can I attend via Zoom, or skip lectures and just follow the course videos instead?
  We require synchronous (in-person) attendance in this course. If you want to get the most out of the course, I strongly recommend you attend lectures in-person. Please use the videos as supplemental resources rather than the basic source of learning. That said, we won't actively take attendance (unless it becomes necessary), and your missing a lecture or two will not be held against you. If you have compelling reasons for missing more than a couple of lectures during the semester, please come talk to us.

Your Health & Well-being

This is an intensive (and somewhat intense) course: 3 days a week, studying new/advanced topics, several HWs. One major goal is that you enjoy taking it and learning this new cool material, as much as I enjoy teaching it. Part of making sure you have fun involves taking care of yourself. Do your best to maintain a healthy lifestyle this semester by eating well, exercising, avoiding drugs and alcohol, getting enough sleep and taking some time to relax. This will help you achieve your goals and cope with stress.

If you or anyone you know experiences any academic stress, difficult life events, or feelings like anxiety or depression, we strongly encourage you to seek support. Counseling and Psychological Services (CaPS) is here to help: call 412-268-2922 and visit http://www.cmu.edu/counseling/. Consider reaching out to a friend, faculty or family member you trust for help getting connected to the support that can help.

Diversity in the Classroom

In this course, we strive to treat everyone with respect, and provide everyone with the best learning experience we can. We believe that diversity, equity, and inclusion should be our goals, not only because they fuel excellence and innovation, but because these are just. Your suggestions are encouraged and appreciated. Please let us know ways to improve the effectiveness of the course for you personally, or for others.

Accommodations for Students with Disabilities:

If you have a disability and are registered with the Office of Disability Resources, I encourage you to use their online system to notify me of your accommodations and talk to me to discuss your needs with me as early in the semester as possible. Since this is a fast-moving course, we should discuss how to make things work out. I will work with you to ensure that accommodations are provided as appropriate. If you suspect that you may have a disability and would benefit from accommodations but are not yet registered with the Office of Disability Resources, I encourage you to contact them at access@andrew.cmu.edu.

Academic Integrity