6.006: Introduction to Algorithms

Lectures and Handouts

Below are materials and information relevant to 6.006 lectures, recitations, and quizzes. These materials will be updated as term progresses.

Lecture and recitation notes are posted on the class wiki.

September
ThuSep 6
Lecture 1: Introduction, Document Distance
Document Distance Example
Readings: CLRS, chapters 1, 2, 3.
FriSep 7
Recitation 1
TueSep 11
Lecture 2: Document Distance (2)
Document Distance Version 3, Version 4, Version 5
Python log from lecture
Readings: CLRS, chapter 11, sections 1 and 2.
Resources: Python Cost Model
 PS1 Out (TeX, PDF, PS)
WedSep 12
Recitation 2
flatten function that works in place
ThuSep 13
Lecture 3: Document Distance (3)
Document Distance Version 6, mergesort.py
Python log from lecture
FriSep 14
Recitation 3
TueSep 18
Lecture 4: Binary Search Trees
Readings: CLRS, chapter 10, and chapter 12, sections 1–3.
WedSep 19
Recitation 4
Example Python OO implementation of a BST augmented with subtree size
ThuSep 20
Lecture 5: Balanced Binary Search Trees
See references page for papers with proofs relating to balanced BSTs.
Readings: CLRS, chapter 13, sections 1 and 2 (warning: red-black trees -- read for culture).
FriSep 21
Recitation 5
TueSep 25
Lecture 6: Hashing (1)
Readings: Lecture notes from OCW; CLRS, chapter 11, sections 1 and 2.
PS1 Due
PS2 Out (TeX, PDF, PS, unit tests, DNA data)
WedSep 26
Recitation 6
Python built-in hash() reimplementation
ThuSep 27
Lecture 7: Hashing (2)
Readings: CLRS, 11.3 and 32.2.
FriSep 28
Recitation 7
October
TueOct 2
Lecture 8: Hashing (3)
Readings: CLRS, chapter 11, section 4.
WedOct 3
Recitation 8
Rabin Karp code for searching digits of Pi.
ThuOct 4
Lecture 9: Dynamic Programming (1)
Readings: CLRS, 15.1–15.3.
FriOct 5
Recitation 9
DP, memoization example code
Add Date
WedOct 10
Recitation 10
ThuOct 11
Lecture 10: Dynamic Programming (2)
Image Compression Handout
PS2 Due
PS3 Out (LaTeX, PDF, PS, template, price data)
FriOct 12
Recitation 11
TueOct 16
Lecture 11: Dynamic Programming (3)
Readings: CLRS, 15.3–15.4.
WedOct 17
Recitation Quiz Review
EVENING QUIZ 1
ThuOct 18
Lecture 12
FriOct 19
Recitation 12
TueOct 23
Lecture 13
PS3 Due
PS4 Out
WedOct 24
Recitation 13
ThuOct 25
Lecture 14
FriOct 26
Recitation 14
TueOct 30
Lecture 15
WedOct 31
Recitation 15
November
ThuNov 1
Lecture 16
FriNov 2
Recitation 16
TueNov 6
Lecture 17
PS4 Due
PS5 Out
WedNov 7
Recitation 17
ThuNov 8
Lecture 18
FriNov 9
Recitation 18
TueNov 13
Lecture 19
WedNov 14
Recitation 19
ThuNov 15
Lecture 20
FriNov 16
Recitation 20
TueNov 20
Lecture 21
PS5 Due
PS6 Out
WedNov 21
Recitation 21
Drop Date
TueNov 27
Lecture 22
WedNov 28
Recitation Quiz Review
EVENING QUIZ 2
ThuNov 29
Lecture 23
FriNov 30
Recitation 22
December
TueDec 4
Lecture 24
PS6 Due
WedDec 5
Recitation 23
ThuDec 6
Lecture 25
FriDec 7
Recitation 24
TueDec 11
Lecture 26
WedDec 12
Recitation 25
??Dec ??
FINAL EXAM (to be scheduled)