6.5210J/18.415J: Advanced Algorithms (Fall 2022, Previously 6.854)

Announcements

1. If you intend to take this course please fill out this survey. Note that this form does NOT replace official registration via MIT Registrar's office, it's for our own internal bookkeeping.
2. We will be using NB, a tool that permits students to discuss and ask questions about lecture videos, notes, and problems sets. For feature reasons we will be using one version of the tool to view and discuss videos and another to view and discuss notes and problems sets. You should sign up for NBv1 at this link. You will get a separate invite for NBv2.
3. We've added this class to psetpartners, which you can use to find collaborators and comply with the collaboration policy which limits the number of psets you can work on with any individual collaborator.

Past Announcements

Course Overview

The prerequisites for this class are strong performance in undergraduate courses in algorithms (e.g., 6.1220J/18.410J, previously 6.046) and discrete mathematics and probability (6.1200J, previously 6.042, is more than sufficient), in addition to substantial mathematical maturity.

The coursework will involve problem sets and a final project that is research-oriented. For more details, see the handout on course information.

Problem Sets

Submission

• We will use gradescope to electronically collect and grade homeworks.
• Because we are doing peer grading, you will need to add a separate gradescope course for submission each week.
• Each week will have a gradescope course code and there will be a single assignment to submit to in gradescope for that week.
• Make sure to use a seperate page for each (sub-)problem.
• Gradescope lets you associate each subproblem with the corresponding pages on your solution. Make sure not to skip this step. Your problem set will not be graded otherwise, and you will lose the corresponding points!
• After your submission has been graded, you can submit a regrade request directly in gradescope.

Due Date and Late Submission

• Problem sets are due Wednesdays at the beginning of class (2.30pm).
• Each student has a total budget of 15 "slack" points to accommodate his/her late problem submissions. Each problem (not pset) that is submitted late but in before Friday class will consume one slack point (and incur no grade penalty). If that problem is submitted in before Monday class, it will consume two slack points (and, again, incur no grade penalty). No late problem will be considered if submitted after the Monday class begins. (So, for example, if there is a problem set with a total of five problems on it, submitting three of these problems on time, one of them before Friday class, and one of them before Monday class will consume three slack points in total.)
• You are responsible for keeping track of your own slack points.
• Late submission can directly be submitted to gradescope as well.
• In order for the late submission to be graded students are additionally required to fill out the late submission form. The link to the form can be found next to the problem set.

Collaboration Policy

• Collaboration is strongly encouraged except where explicitly forbidden. However, you must independently write up your own solution, without relying on extensive collaborator notes, and you must list all collaborators for each problem on your problem set. Collaboration groups should be small (3 or 4 students) to ensure that everyone is actively engaged with the problems.
• You may not seek out answers from other sources without prior permission. In particular, you may not use bibles or posted solutions to problems from previous years.
• You may not work with the same collaborator on more than 3 psets. We hope this will give you more opportunity to meet and learn from your amazing peers and help to level the playing field for students entering the class without existing social ties. Starting with problem set 4, you should not form a group with anyone that you have already worked with on 3 psets or more.
• You can find collaborators for this course through psetpartners.

Peer Grading

• Each student is required to grade (at least but hopefully) one problem in the semester.
• We will have a TA-supervised grading meeting each week. This session is used to make sure that the graders fully understand the solution, while they can grade the problems at home after this session.
• Please use the link next to the problem set, to sign up as grader for the corresponding problem set. Make sure to sign up before the pset due date as soon as possible because slots to grade a given pset can fill up.
• Peer graders need to finish grading their assigned problem by the Friday 9 days after the problem set is due. They are also responsible for grading late submissions and regrade requests.
• Note that no late submissions are allowed if you sign up as peer-grader.

Lectures

For notes and videos related to each topic, see the course materials.