Lectures and Recitations

From 6.006 Wiki

Revision as of 15:15, 7 October 2008

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

Sorting

Lecture 8 : Insertion, Merge, and Heap Sort

Recitation 8

• (R01, R02)
  • notes
  • heaps code (handout)
  • heaps code (complete)
• (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

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