6.856J/18.416J Randomized Algorithms (Spring 2021)

Lecture:	2:30-4 Monday, Wednesday, Friday
Units:	5-0-7
Instructor:	David Karger	karger@mit.edu
TAs:	Thiago Bergamaschi	thiagob@mit.edu
	Yinzhan Xu	xyzhan@mit.edu
	Office hours:	5:30-6:30pm, 10-11pm on Monday and 4-5pm on Friday in this Comingle room

Course Announcements

• Lectures will be streamed online during class time and recorded for later viewing. The zoom link is here. We have the waiting room enabled, so make sure to arrive early so that you can be admitted.
• You can find the the final project handout here, and you can find sample projects from previous years here. We will be accepting project proposals by email starting Friday the 23rd.
• If you would like to find collaborators for the final project, please add your name and reach out to students on this Google Spreadsheet.
• Given the long weekend, the Pset 9 deadline has been extended to Friday the 23rd, and the Pset 8 second late deadline has been extended to Wednesday the 21st.

NB Discussion System

Course Information

If you are thinking about taking this course, you might want to see what past students have said about previous times I taught Randomized Algorithms, in 2013, 2005, or 2002.

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 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.

Policy

• Collaboration is strongly encouraged except where explicitly forbidden. However, each person must independently write up his/her own solution, and you must list all collaborators for each problem on your problem set.
• Collaboration groups should be small, to ensure that everyone is actively engaged with the problems. Please limit your groups to 3 students at most, unless extreme circumstances prohibit collaboration (e.g. timezones); in which case 4 students will be allowed. Please email us if you think you fall in one of these cases.
• 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.
• So you can meet more of your classmates and so we can make the collaboration groups more equitable, we will be giving you random partners every 3 psets. Starting on problem set 4, you should not form a group with anyone that you have already worked with on 3 psets or more.

Peer Grading

• Each student is required to grade (at least but hopefully) one problem in the semester.
• We will have a TA-supervised grading session 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

• The lecture schedule is tentative and will be updated throughout the semester to reflect the material covered in each lecture.
• The notes are my own lecture notes; they will not serve to teach the material but should serve as a record of what was covered in each lecture.
• Note that all course notes can be found in nb, where you can read and annotate them with questions.
• Lecture recordings from Spring 2019 can be found here.