Lectures and Recitations

From 6.006 Wiki

Revision as of 16:29, 25 October 2008

PNG versions of the PDFs, if you're having trouble opening them: http://courses.csail.mit.edu/6.006/fall08/notes/png/

Introduction and Document Distance

Lecture 1, Introduction and Document Distance

• Document Distance (docdist{1,2,3,4}.py)
• Readings: CLRS Chapters 1,2,3

Recitation 1

• (R01, R02) docdist_profiling.py
• (R06) Recitation01 Notes

Lecture 2, Document Distance, Mergesort

• Document Distance (docdist{5,6}.py)
• mergesort.py code from class
• Readings:
  • CLRS Chapter 11, Sections 1-2; CLRS Chapter 4
  • Python Cost Model

Recitation 2 : maximum sum contiguous subarray problem

• Jon Bentley's column on the maximum sum contiguous vector problem discussed in class
• (R01, R02) Rec 02 warmup
• (R01, R02) maxsumsubarray.py
• (R06) Recitation02 Notes

Binary Search Trees

Lecture 3, Binary Search Trees

• runway.py code from class
• Readings: CLRS Chapter 10; Chapter 12, Sections 1-3

Recitation 3

• (R01, R02) Rec 03
• (R01, R02) BSTobjects.py implements BSTs as python objects
• BSTlists.py implementation extending the one shown in lecture
• (R06) Recitation03 Notes

Lecture 4 : AVL trees (Balanced BSTs)

Recitation 4

• AVL applet
• Another AVL applet
• (R03, R04) AVL template
• (R01, R02) Rec 04
• (R06) Recitation04 Notes

Hashing

Lecture 5 : Hashing I

Readings: CLRS 11.1-11.3

Recitation 5

• (R01, R02) Rec 05

Lecture 6 : Hashing II

Readings: CLRS 17, 32.2

Recitation 6

• (R01, R02, R05) Rec 06

Lecture 7 : Hashing III

Readings: CLRS 11.4, 11.3.3, 11.5

Recitation 7

• short cuckoo hashing reference
• (R01, R02) Rec 07
• (R03, R04) Jayant's Problems from Rec 07

Sorting

Lecture 8 : Insertion, Merge, and Heap Sort

Recitation 8

• (R01, R02)
  • notes
  • heaps code (handout)
  • heaps code (complete)
• (R03, R04) Jayant's Problems from Rec 08
• (R06) Recitation08 Notes

Lecture 9 : more heaps(heapsort, building), priority queues

Recitation 9

• (R1, R2)
  • notes
  • merging k-lists code (i have not verified the validity of this code)
  • merging k-lists in more depth
• (R03, R04) Jayant's Problems from Rec 09

Lecture 10 : Decision tree - lower bounds on sorting, counting sort

Recitation 10

• (R1, R2)
  • notes
  • debugging lecture notes 6.170
• (R03, R04) Jayant's Problems from Rec 10

Lecture 11 : Radix sort

Quiz 1 Review (Recitation 11)

• quiz review handout
• recurrences practise

Searching

Lecture 12 : Intro to Searching, Graphs, small Rubiks problem

Rectation 12 (canceled)

Lecture 13 : Graph Searching : BFS, DFS

Recitation 13

• (R1, R2) notes

Lecture 14 : Graph Searching II : DAGs, topological sort

Recitation 14

• (R1, R2) notes

Shortest Paths

Lecture 15 : Intro Shortest Paths : weighted graphs & general structure

Recitation 15

• (R1, R2) notes