Lectures and Recitations
From 6.006 Wiki
(Difference between revisions)
(→Quiz 1 Review (Recitation 11)) |
|||
Line 61: | Line 61: | ||
* [http://www.it-c.dk/people/pagh/papers/cuckoo-undergrad.pdf short cuckoo hashing reference] | * [http://www.it-c.dk/people/pagh/papers/cuckoo-undergrad.pdf short cuckoo hashing reference] | ||
* (R01, R02) [http://courses.csail.mit.edu/6.006/fall08/notes/rec07.pdf Rec 07] | * (R01, R02) [http://courses.csail.mit.edu/6.006/fall08/notes/rec07.pdf Rec 07] | ||
- | + | * (R03, R04) [http://courses.csail.mit.edu/6.006/fall08/notes/jayant-r07-problems.pdf Jayant's Problems from Rec 07] | |
=== Sorting === | === Sorting === | ||
Line 71: | Line 71: | ||
** [http://courses.csail.mit.edu/6.006/fall08/source/rec/r08_heap_HANDOUT.py heaps code (handout)] | ** [http://courses.csail.mit.edu/6.006/fall08/source/rec/r08_heap_HANDOUT.py heaps code (handout)] | ||
** [http://courses.csail.mit.edu/6.006/fall08/source/rec/r08_heap_MASTER.py heaps code (complete)] | ** [http://courses.csail.mit.edu/6.006/fall08/source/rec/r08_heap_MASTER.py heaps code (complete)] | ||
+ | * (R03, R04) [http://courses.csail.mit.edu/6.006/fall08/notes/jayant-r08-problems.pdf Jayant's Problems from Rec 08] | ||
* (R06) [[Recitation08 Notes]] | * (R06) [[Recitation08 Notes]] | ||
Line 79: | Line 80: | ||
** [http://blog.davebsd.com/2007/02/05/merge-k-sorted-lists-in-onlogk-time/ merging k-lists code] (i have not verified the validity of this code) | ** [http://blog.davebsd.com/2007/02/05/merge-k-sorted-lists-in-onlogk-time/ merging k-lists code] (i have not verified the validity of this code) | ||
** [http://wordaligned.org/articles/merging-sorted-streams-in-python merging k-lists] in more depth | ** [http://wordaligned.org/articles/merging-sorted-streams-in-python merging k-lists] in more depth | ||
+ | * (R03, R04) [http://courses.csail.mit.edu/6.006/fall08/notes/jayant-r09-problems.pdf Jayant's Problems from Rec 09] | ||
==== [http://courses.csail.mit.edu/6.006/fall08/notes/lecture10.pdf Lecture 10] : Decision tree - lower bounds on sorting, counting sort ==== | ==== [http://courses.csail.mit.edu/6.006/fall08/notes/lecture10.pdf Lecture 10] : Decision tree - lower bounds on sorting, counting sort ==== | ||
Line 86: | Line 88: | ||
** [http://courses.csail.mit.edu/6.006/fall08/notes/rec10.pdf notes] | ** [http://courses.csail.mit.edu/6.006/fall08/notes/rec10.pdf notes] | ||
** [http://courses.csail.mit.edu/6.170/old-www/2006-Spring/lectures/lect12-debugging.pdf debugging lecture notes 6.170] | ** [http://courses.csail.mit.edu/6.170/old-www/2006-Spring/lectures/lect12-debugging.pdf debugging lecture notes 6.170] | ||
+ | * (R03, R04) [http://courses.csail.mit.edu/6.006/fall08/notes/jayant-r10-problems.pdf Jayant's Problems from Rec 10] | ||
==== [http://courses.csail.mit.edu/6.006/fall08/notes/lecture11.pdf Lecture 11] : Radix sort ==== | ==== [http://courses.csail.mit.edu/6.006/fall08/notes/lecture11.pdf Lecture 11] : Radix sort ==== |
Revision as of 03:52, 15 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
- (R03, R04) Jayant's Problems from Rec 07
Sorting
Lecture 8 : Insertion, Merge, and Heap Sort
Recitation 8
- (R01, R02)
- (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)
- (R03, R04) Jayant's Problems from Rec 10