Lectures and Recitations

From 6.006 Wiki

Contents 1 Introduction and Document Distance 1.1 Lecture 1, Introduction and Document Distance 1.2 Recitation 1 1.3 Lecture 2, Document Distance, Mergesort 1.4 Recitation 2 : maximum sum contiguous subarray problem 2 Binary Search Trees 2.1 Lecture 3, Binary Search Trees 2.2 Recitation 3 2.3 Lecture 4 : AVL trees (Balanced BSTs) 2.4 Recitation 4 3 Hashing 3.1 Lecture 5 : Hashing I 3.2 Recitation 5 3.3 Lecture 6 : Hashing II 3.4 Recitation 6 3.5 Lecture 7 : Hashing III 3.6 Recitation 7 4 Sorting 4.1 Lecture 8 : Insertion, Merge, and Heap Sort 4.2 Recitation 8 4.3 Lecture 9 : more heaps(heapsort, building), priority queues 4.4 Recitation 9

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 answers
  • 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