15-850: Advanced Algorithms, Spring 2023

Lecturer: Anupam Gupta, GHC 7203, anupamg at cs.
TAs: TBD
Office hours: TBD

Location: Posner 153, MWF 3:30-4:50 (note: 3 days a week).
Piazza is the best way to contact the course staff.
Gradescope should be used to submit HWs. Entry code: 3J7YX4

Announcements


Homeworks


Lectures


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

The current list of potential topics are:
  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
  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
Here are the Fall 20, Fall 18, Spring 17 and Spring 15 versions of this course. The topics this year will be similar (though not identical). I will take a poll in early March about topics to cover in the last 4-5 lectures.

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.

FAQs:


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

Honesty and transparency are important features of good scholarship. Equally importantly, plagiarism and cheating are serious academic offenses with serious consequences. You should cite any sources you use, other than the lectures notes we give you. (E.g., if you refer a reserch paper to solve a problem, you should say that.) If you are discovered engaging in either behavior in this course, you will earn a failing grade on the assignment in question, and further disciplinary action may be taken. For a clear description of what counts as plagiarism, cheating, and/or the use of unauthorized sources, please see the University Policy on Academic Integrity and the Carnegie Mellon Code on Academic Integrity.
Maintained by Anupam Gupta