15-850: Advanced Algorithms, Fall 2020: 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 Algorithms course (15-750). 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, Williams' subcubic APSP algorithm for general graphs.
  3. Matchings: classical matchings using augmenting paths, matching using matrix inversions (Tutte/Lovasz, Mucha-Sankowski), matchings using random walks.
  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 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 mid-Oct about topics to cover in the last 4-5 lectures.

Course Rules during the Pandemic

Things are tricky, for a variety of reasons. I have left most of the rules below as they would be in usual times, with only basic changes. However, I want you to be OK. And I want you to enjoy the course, and get stuff out of it. If you need extra time or help, or if there is something that can make a difference, talk to the course staff. We will help how we can.

Effort and Criteria for Evaluation:

We have 3 lectures a week for the first ~10 weeks of the semester. Attendance is (normally) 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.

Online Attendance and Zoom:

Lectures will be on Zoom. I will write on a real or virtual whiteboard during the lecture. The lecture will be taped, and you can review the video later. I strongly suggest you attend the lecture live, if possible. Also, please leave your video on, and ask questions as you would in an in-person lecture. You can unmute yourself and pipe up, or you can type into the chat and a TA can ask on your behalf. The more we can recreate the classroom environment the better our joint experience. You can check out Loom.ai for fun 3D avatars to use if you're having a bad hair day, it's more fun than a static photo or nothing at all. (Loom.ai was co-founded by a CMU Alumnus.)

Textbook:

There is no textbook for the course. Most of our material is not in textbooks (yet), so we will rely on papers and monographs. We will provide you with lecture notes from past years; 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. We will not accept late HWs, barring exceptional circumstances. However, each individual student has three "24 hour free" passes. Each pass can be used to extend the deadline for a homework by up to 24 hours. You can use at most two passes per HW. Those are the regular rules. But we understand that these are difficult times. If you have trouble with meeting these deadlines, talk to us. We will figure something out.

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, and use Google Jamboard, or AwwApp, or other online whiteboards to collaborate.

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 will have fun taking it and learning this new cool material, as much as I hope to have fun 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