Lectures and Recitations

From 6.006 Wiki

Revision as of 14:34, 15 October 2008 (view source) Wrightc (Talk | contribs) ← Older edit		Revision as of 22:26, 15 October 2008 (view source) Juang (Talk | contribs) Newer edit →
Line 1:		Line 1:
	{{TOCright}}		{{TOCright}}
		+
		+	'''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 ===		=== Introduction and Document Distance ===

---

Revision as of 22:26, 15 October 2008

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 4.5 Lecture 10 : Decision tree - lower bounds on sorting, counting sort 4.6 Recitation 10 4.7 Lecture 11 : Radix sort 5 Quiz 1 Review (Recitation 11) 6 Searching 6.1 Lecture 12 : Intro to Searching, Graphs, small Rubiks problem

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