Introduction to Algorithms: 6.

006
Massachusetts Institute of Technology January 31, 2020
Instructors: Erik Demaine, Jason Ku, and Justin Solomon Course Information

Course Information

Instructors Erik Demaine 32-G680 edemaine@mit.edu

Jason Ku 38-683 jasonku@mit.edu
Justin Solomon 32-D460 jsolomon@mit.edu

Teaching Assistants Jeffrey Bosboom JBo jbosboom@mit.edu

Jackie Bredenberg JBr jamb@mit.edu
Alex Chen AC achen19@mit.edu
Michael Coulombe MC mcoulomb@mit.edu
Yevhenii Diomidov YD diomidov@mit.edu
Louisa Huang LH rlhuang@mit.edu
Shreyas Kapur SK shreyask@mit.edu
Rachel Levy-Green RL levyr@mit.edu
Sabrina Liu SL sabliu@mit.edu
Srijon Mukherjee SM srijonm@mit.edu
Priya Pillai PP pppillai@mit.edu
Eric Qian EQ ericqian@mit.edu
Alexander Root AR aroot222@mit.edu
Martin Schneider MS martinfs@mit.edu
Crystal Su CS cbsu@mit.edu

Questions? 6.006-questions@mit.edu

Websites

Stellar Announcements, calendar, grades, and PDF course content.

https://tinyurl.com/6-006sp20
Piazza All discussion related to course material.
http://piazza.com/mit/spring2020/6006
Gradescope LATEX problem set submissions and regrades.
https://www.gradescope.com/courses/84219
Code Checker Auto-graded code problem set submissions.
https://alg.mit.edu
2 Course Information

Content
6.006 is an introductory course covering elementary data structures (dynamic arrays, heaps, bal-
anced binary search trees, hash tables) and algorithmic approaches to solve classical problems
(sorting, graph searching, dynamic programming). Written course material will be distributed via
notes from lectures and recitations. An additional useful reference is Introduction to Algorithms
by Cormen, Leiserson, Rivest, and Stein (Third Edition, MIT Press), commonly known as CLRS,
though this text is not required for the course.

Lectures
Lectures will be available online, prerecorded for OCW1 . They will be released at 11 A . M . on
Tuesdays and Thursdays. A link to the unlisted video recordings can be accessed by going to the
Online Content page on alg.mit.edu after login.

Recitations
One-hour Recitations will be held weekly on Wednesdays and Fridays. Recitations supplement
the material presented in lecture in a more interactive setting. You are responsible for material
presented during both lecture and recitation. Recitations will occur in LIVE in Zoom classrooms2 .
Please add yourself to any available recitation section on the LMOD website. While recitations are
online, they will still be space limited. If you attend a section to which you are not assigned, the
TA may ask you to leave if there are too many students connected. We will assign two additional
sections after we gauge demand.

Time TA Zoom Room Time TA Zoom Room

(EDT) mit.zoom.us/ (EDT) mit.zoom.us/
R01 10 A . M RL j/232599005 R09 6 P. M AC j/747242461
R02 11 A . M LH j/655956749 R10 7 P. M MC j/784346143
R03 12 P. M JBr j/383921417 R11 10 P. M MS j/997867070
R04 1 P. M PP j/878130681 R12 11 P. M SK j/465070431
R05 2 P. M PP j/878130681 R13 12 A . M EQ j/634617844
R06 3 P. M CS j/260092214 R14 5 P. M SL j/110182901
R07 4 P. M AR j/799332156 R15 6 P. M SM j/924219799
R08 5 P. M AC j/747242461

Your recitation grade will be assigned based on the average of two numbers: 5.0, and the grade
(between 0.0 to 5.0) your original recitation instructor would have assigned you before the course
moved online.

1
https://ocw.mit.edu/index.htm
2
The password for our Zoom rooms can be accessed at alg.mit.edu after login on the Online Content page.
Course Information 3

Office Hours
Teaching Assistants will hold virtual office hours via Zoom3 on designated office hour days that
directly precede each problem set due date or quiz.

6.006 Office Hours Zoom Room: https://mit.zoom.us/j/234349376

On every office hour day, office hours will be held in the Zoom room listed above, at ALL of the
following times (EDT). The room will also be open at other times for students to chat with each
other, but we suggest moving to non-course Zoom rooms to work outside of office hour times.
• 10 A . M . − Noon (morning)
• 2 P. M . − 4 P. M . (afternoon)
• 8 P. M . − 10 P. M . (evening)

Office hours will be held in one of two formats:

• One TA: Most office hours will be staffed by only a single TA in the Zoom room. This TA
will maintain a queue of help requests (either from individuals or from groups of students),
and will help students based on this queue.
• Many TAs: During the three days preceding each problem set deadline and the two days
preceding each quiz, the evening office hours session from 8 P. M . − 10 P. M . will be staffed
by 6 or more TAs who will each help many students working on the same content at the same
time.

If you need help with theory questions, you will probably be helped fastest during office hours
staffed by multiple TAs. Below is a calendar marking the days office hours will be held after
moving online:
• days without office hours are white, and
• office hour days are gray (Many TA evening days are darker),
• assignment deadlines are black (these are never office hour days).

Month U M T W R F S
March 22 23 24 25 26 27 28
29 30 31 1 2 3 4
April 5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 1 2
May 3 4 5 6 7 8 9

As before, Instructors will hold individual office hours online by appointment.

3
The password for our Zoom rooms can be accessed at alg.mit.edu after login on the Online Content page.
4 Course Information

Prerequisites
6.0001 Basic experience programming in Python 3.
6.042 Basic knowledge of discrete mathematics: set theory, relations and logic, combinatorics,
proofs, recursion, number theory, graph theory, and probability.
We strongly caution against taking 6.006 before having fulfilled the listed prerequisites. We will
evaluate entering understanding of the prerequisite material via a short Problem Set 0 assignment
(released S 2/01 and due on F 2/07). All students must submit this evaluation, regardless of
prerequisite status. We will assign each submission a letter grade. If you receive a C or below
on the assignment, you will need to meet with a staff member to review your performance before
you will be allowed to take the class. We will not grade any other assignments from you until
a good faith attempt of Problem Set 0 has been submitted. The grade for this assignment will
NOT affect your final grade in the class, but turning it in is required for taking this class.

Grading Policy
UPDATE: In compliance with EECS guidelines, we have removed 12 hours of course work from
this class: two lectures, two recitations, and one problem set. While problem sets normally cover
only two lectures, Problem Sets 5 and 6 now cover six lectures of material together, and will each
be worth 50% more than a normal problem set. Your grade will now be based on recitation, 8
problem sets, 3 quizzes, and a final exam.

Weight Date Time

Quiz 1 20% Tuesday, March 31, 2020 7:30–9:30 P. M .
Quiz 2 15% Tuesday, April 21, 2020 7:30–9:00 P. M .
Quiz 3 10% Thursday, May 7, 2020 7:30–8:30 P. M .
Final Exam 35% Wednesday, May 20, 2020 1:30–4:30 P. M .
Problem Sets 18% 8 PSs, 3% PS5 & PS6, 2% rest
Recitation 2% Graded by your TA

MIT provides definitions4 for the letter grades A, B, C, D, and F . In order to normalize assign-
ments that vary in length and difficulty, we will provide a separate piece-wise linear mapping for
each assignment, from the assignment’s grade space to the interval [0, 5]. Grades mapped to the
half-open intervals (4, 5], (3, 4], (2, 3], (1, 2], and [0, 1] correspond to letter grades A, B, C, D, and
F respectively.

This term Alternate Grades are in effect (PE, NE, IE). To determine your final grade in the class,
we will compute the weighted sum of your mapped assignment grades. A sum strictly above a 2
will receive a PE in this class. All other students will be assigned a grade individually based on
institute recommendations.

4
http://catalog.mit.edu/mit/procedures/academic-performance-grades/#gradestex
Course Information 5

If you feel that any assignment has been graded incorrectly, you may submit a regrade request to
the relevant assignment on Gradescope, within a regrade window after the assignment’s grade has
been released (typically about a week). For any regrade request, we reserve the right to regrade the
entire assignment, and your grade may be adjusted up or down as a result of the regrade.

Problem Sets
Problem sets will be released roughly a week before they are due. Associated with each problem
set, we will hold an optional worked problem session, covering a selection of problem-set problems
from previous terms. As with lectures this term, these problem sessions will be prerecorded for
OCW, and will be released by 4 p.m. on the day listed.

Problem Release Due

PS # Session Date Date Topic
0 S 2/01 F 2/07 Prerequisite Evaluation
1 F 2/07 S 2/08 F 2/14 Asymptotics, Sequences
2 F 2/14 S 2/15 F 2/21 Sets, Sorting, Recurrences
3 F 2/21 S 2/22 F 2/28 Hashing, Linear Sorting
4 F 2/28 S 2/29 F 3/06 Binary Trees, Binary Heaps
5 F 3/20 S 3/28 U 4/05 Graph Traversal, Topological Sort
F 4/03
6 T 4/07 U 4/05 U 4/12 Weighted Shortest Paths
7 F 4/17 U 4/19 U 4/26 Dynamic Programming
8 T 4/28 U 4/26 F 5/01 More Dynamic Programming (shorter)

Each problem set will contain a theory portion and a coding portion. Each theory portion must
be uploaded to Gradescope as a PDF file compiled from a provided LATEX template. Each coding
portion will be administered and automatically graded via our Code Checking website, and must
be completed using Python 3. Problem set submissions are due by 6 P. M . on the posted due date.

Late submissions will be accepted up until 48 hours after the due date, also at 6 P. M .. Solutions
will be posted shortly after the late submission window closes. We will not penalize your two
highest scoring late submissions, but we will penalize any additional late submissions by 50%. In
exceptional circumstances, problem set deadlines may be individually extended without penalty at
the request of an Institute Dean. Please submit extension requests via the online extension form on
alg.mit.edu. As every assignment contributes to learning, no assignment may be dropped.
6 Course Information

Exams
There will be no official lecture on quiz days. A review will be given during the recitation preceding
each quiz. Quizzes and the Final Exam will be given online via Gradescope. Each exam will be
closed book, but you will be allowed to use some pre-prepared double-sided notes: one page for
Quiz 1, two for Quiz 2, three for Quiz 3, and three for the Final Exam. Attendance at the quizzes
and the Final Exam is mandatory and may not be excused. Because of various issues with
administering an exam online, we will provide an online form where students can request:
• a makeup exam at a different time, and/or
• extended time in extenuating circumstances.
Please only make such requests via our online form.

Collaboration
The goal of the problem sets is for you to practice applying the course material. In this class,
you are encouraged to collaborate on problem sets. Students who work together on problem sets
generally do better on exams than students who work alone, but you will learn the material best if
you work on the problems FIRST on your own. Some forms of collaboration are not allowed;
some examples are listed below. Violating the collaboration policy to increase your score on a
problem set is likely to lower your score on an exam, which carries significantly more weight. A
violation may also lead to academic action and/or a significant penalty on your grade.

• Identify any collaborators or outside sources at the top of each LATEX submission.
• Write code and theory problem solutions by yourself in your own words.
• Do NOT directly copy the work of others.
• Do NOT look at written solutions or code by other students before submitting your own
solution. You may look at another student’s code on their screen, only to help them debug,
and only after you have submitted your own solution.
• Do NOT let other students see your written solutions.
• Do NOT send other students your code.
• You may ask TAs to help you debug your code during office hours or in a private Piazza post.
Course Information 7

Syllabus

Date Lec Topic Date Rec PS Due

T 2/04 L01 Algorithms and Computation W 2/05 R01 PS0
R 2/06 L02 Data Structures / Dynamic Arrays F 2/07 R02 F 2/07
T 2/11 L03 Sets / Sorting W 2/12 R03 PS1
R 2/13 L04 Direct Access & Hashing F 2/14 R04 F 2/14
T 2/18 President’s Day (Monday classes) W 2/19 PS2
R 2/20 L05 Linear Sorting F 2/21 R05 F 2/21
T 2/25 L06 Balanced Binary Trees W 2/26 R06 PS3
R 2/27 L07 BSTs and Sequence Trees F 2/28 R07 F 2/28
T 3/03 L08 Heaps / Priority Queues W 3/04 R08 PS4
R 3/05 L09 Breadth-First Search F 3/06 R09 F 3/06
T 3/10 L10 Depth-First Search W 3/11 R10
R 3/12 L11 Weighted Shortest Paths in DAG F 3/13 R11
T 3/17 Cancelled W 3/18
R 3/19 F 3/20
T 3/23 Spring Break W 3/24
R 3/25 F 3/26
T 3/31 Quiz 1: L01 – L08 W 4/01 PS5
R 4/02 L12 Bellman-Ford F 4/03 R12 U 4/05
T 4/07 L13 Dijkstra W 4/08 R13 PS6
R 4/09 L14 All-Pairs Shortest Paths F 4/10 R14 U 4/12
T 4/14 L15 Dynamic Programming Intro W 4/15 R15
R 4/16 L16 Guessing Subproblems F 4/17 R16
T 4/21 Quiz 2: L01 – L14 W 4/22 PS7
R 4/23 L17 Subproblem Expansion F 4/24 R17 U 4/26
T 4/28 L18 Subset Sum & Pseudo-polynomial W 4/29 R18 PS8
R 4/30 L19 P, NP, Hardness, Completeness F 5/01 R19 F 5/01
T 5/05 L20 Course Review W 5/06 R20
R 5/07 Quiz 3: L01 – L18 F 5/08
T 5/12 L21 Algorithms: Next Steps W 5/13
W 5/20 Final: L01 – L20