Lectures and Recitations
From 6.006 Wiki
(Difference between revisions)
m (→Recitation 2 : maximum sum contiguous subarray problem) |
(→[http://courses.csail.mit.edu/6.006/fall08/notes/lecture26.pdf Lecture 26] : Beyond 6.006) |
||
(76 intermediate revisions not shown) | |||
Line 1: | Line 1: | ||
+ | {{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 === | ||
- | ==== [http://courses.csail.mit.edu/6.006/fall08/notes/ | + | ==== [http://courses.csail.mit.edu/6.006/fall08/notes/lecture01.pdf Lecture 1], Introduction and Document Distance ==== |
* [[Document Distance]] (docdist{1,2,3,4}.py) | * [[Document Distance]] (docdist{1,2,3,4}.py) | ||
* Readings: CLRS Chapters 1,2,3 | * Readings: CLRS Chapters 1,2,3 | ||
==== Recitation 1 ==== | ==== Recitation 1 ==== | ||
- | |||
* (R01, R02) [http://courses.csail.mit.edu/6.006/fall08/source/rec/r01%20-%20docdist.py <code>docdist_profiling.py</code>] | * (R01, R02) [http://courses.csail.mit.edu/6.006/fall08/source/rec/r01%20-%20docdist.py <code>docdist_profiling.py</code>] | ||
+ | * (R06) [[Recitation01 Notes]] | ||
- | + | ==== [http://courses.csail.mit.edu/6.006/fall08/notes/lecture02.pdf Lecture 2], Document Distance, Mergesort ==== | |
- | ==== [http://courses.csail.mit.edu/6.006/fall08/notes/ | + | |
* [[Document Distance]] (docdist{5,6}.py) | * [[Document Distance]] (docdist{5,6}.py) | ||
* [http://courses.csail.mit.edu/6.006/fall08/source/mergesort.py <code>mergesort.py</code>] code from class | * [http://courses.csail.mit.edu/6.006/fall08/source/mergesort.py <code>mergesort.py</code>] code from class | ||
Line 18: | Line 21: | ||
==== Recitation 2 : maximum sum contiguous subarray problem ==== | ==== Recitation 2 : maximum sum contiguous subarray problem ==== | ||
* [https://courses.csail.mit.edu/6.006/fall08/handouts/protected/Bentley.pdf Jon Bentley's column on the maximum sum contiguous vector problem discussed in class] | * [https://courses.csail.mit.edu/6.006/fall08/handouts/protected/Bentley.pdf Jon Bentley's column on the maximum sum contiguous vector problem discussed in class] | ||
- | + | * (R01, R02) [http://courses.csail.mit.edu/6.006/fall08/notes/rec02.pdf Rec 02 warmup] | |
- | * (R01, R02) [http://courses.csail.mit.edu/6.006/fall08/notes/ | + | |
* (R01, R02) [http://courses.csail.mit.edu/6.006/fall08/source/rec/r02%20-%20maxsumsubarray.py <code>maxsumsubarray.py</code>] | * (R01, R02) [http://courses.csail.mit.edu/6.006/fall08/source/rec/r02%20-%20maxsumsubarray.py <code>maxsumsubarray.py</code>] | ||
+ | * (R06) [[Recitation02 Notes]] | ||
+ | |||
+ | |||
=== Binary Search Trees === | === Binary Search Trees === | ||
- | ==== [http://courses.csail.mit.edu/6.006/fall08/notes/ | + | ==== [http://courses.csail.mit.edu/6.006/fall08/notes/lecture03.pdf Lecture 3], Binary Search Trees ==== |
* [http://courses.csail.mit.edu/6.006/fall08/source/runway.py <code>runway.py</code>] code from class | * [http://courses.csail.mit.edu/6.006/fall08/source/runway.py <code>runway.py</code>] code from class | ||
* Readings: CLRS Chapter 10; Chapter 12, Sections 1-3 | * Readings: CLRS Chapter 10; Chapter 12, Sections 1-3 | ||
==== Recitation 3 ==== | ==== Recitation 3 ==== | ||
- | + | * (R01, R02) [http://courses.csail.mit.edu/6.006/fall08/notes/rec03.pdf Rec 03] | |
- | * (R01, R02) [http://courses.csail.mit.edu/6.006/fall08/notes/ | + | |
* (R01, R02) [http://courses.csail.mit.edu/6.006/fall08/source/rec/r03%20-%20BST%20v2%20master.py <code>BSTobjects.py</code>] implements BSTs as python objects | * (R01, R02) [http://courses.csail.mit.edu/6.006/fall08/source/rec/r03%20-%20BST%20v2%20master.py <code>BSTobjects.py</code>] implements BSTs as python objects | ||
* [http://courses.csail.mit.edu/6.006/fall08/source/rec/r03%20-%20BST%20-%20jayant.py <code>BSTlists.py</code>] implementation extending the one shown in lecture | * [http://courses.csail.mit.edu/6.006/fall08/source/rec/r03%20-%20BST%20-%20jayant.py <code>BSTlists.py</code>] implementation extending the one shown in lecture | ||
+ | * (R06) [[Recitation03 Notes]] | ||
- | ==== [http://courses.csail.mit.edu/6.006/fall08/notes/ | + | ==== [http://courses.csail.mit.edu/6.006/fall08/notes/lecture04.pdf Lecture 4] : AVL trees (Balanced BSTs) ==== |
==== Recitation 4 ==== | ==== Recitation 4 ==== | ||
* [http://www.site.uottawa.ca/~stan/csi2514/applets/avl/BT.html AVL applet] | * [http://www.site.uottawa.ca/~stan/csi2514/applets/avl/BT.html AVL applet] | ||
Line 40: | Line 45: | ||
* (R01, R02) [http://courses.csail.mit.edu/6.006/fall08/notes/rec04.pdf Rec 04] | * (R01, R02) [http://courses.csail.mit.edu/6.006/fall08/notes/rec04.pdf Rec 04] | ||
* (R06) [[Recitation04 Notes]] | * (R06) [[Recitation04 Notes]] | ||
+ | |||
+ | |||
=== Hashing === | === Hashing === | ||
- | ==== [http://courses.csail.mit.edu/6.006/fall08/notes/ | + | ==== [http://courses.csail.mit.edu/6.006/fall08/notes/lecture05.pdf Lecture 5] : Hashing I==== |
+ | Readings: CLRS 11.1-11.3 | ||
+ | |||
+ | ==== Recitation 5 ==== | ||
+ | * (R01, R02) [http://courses.csail.mit.edu/6.006/fall08/notes/rec05.pdf Rec 05] | ||
+ | |||
+ | ==== [http://courses.csail.mit.edu/6.006/fall08/notes/lecture06.pdf Lecture 6] : Hashing II==== | ||
+ | Readings: CLRS 17, 32.2 | ||
+ | |||
+ | ==== Recitation 6 ==== | ||
+ | * (R01, R02, R05) [http://courses.csail.mit.edu/6.006/fall08/notes/rec06.pdf Rec 06] | ||
+ | |||
+ | ==== [http://courses.csail.mit.edu/6.006/fall08/notes/lecture07.pdf Lecture 7] : Hashing III==== | ||
+ | Readings: CLRS 11.4, 11.3.3, 11.5 | ||
+ | |||
+ | ==== Recitation 7 ==== | ||
+ | * [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] | ||
+ | * (R03, R04) [http://courses.csail.mit.edu/6.006/fall08/notes/jayant-r07-problems.pdf Jayant's Problems from Rec 07] | ||
+ | |||
+ | |||
+ | |||
+ | === Sorting === | ||
+ | ==== [http://courses.csail.mit.edu/6.006/fall08/notes/lecture08.pdf Lecture 8] : Insertion, Merge, and Heap Sort ==== | ||
+ | |||
+ | ==== Recitation 8 ==== | ||
+ | * (R01, R02) | ||
+ | ** [http://courses.csail.mit.edu/6.006/fall08/notes/rec08.pdf notes] | ||
+ | ** [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)] | ||
+ | * (R03, R04) [http://courses.csail.mit.edu/6.006/fall08/notes/jayant-r08-problems.pdf Jayant's Problems from Rec 08] | ||
+ | * (R06) [[Recitation08 Notes]] | ||
+ | |||
+ | ==== [http://courses.csail.mit.edu/6.006/fall08/notes/lecture09.pdf Lecture 9] : more heaps(heapsort, building), priority queues ==== | ||
+ | ==== Recitation 9 ==== | ||
+ | * (R1, R2) | ||
+ | ** [http://courses.csail.mit.edu/6.006/fall08/notes/rec09.pdf notes] | ||
+ | ** [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 | ||
+ | * (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 ==== | ||
+ | |||
+ | ==== Recitation 10 ==== | ||
+ | * (R1, R2) | ||
+ | ** [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] | ||
+ | * (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 ==== | ||
+ | |||
+ | |||
+ | |||
+ | === Quiz 1 Review (Recitation 11) === | ||
+ | * [http://courses.csail.mit.edu/6.006/fall08/handouts/H07-quiz_review.pdf quiz review handout] | ||
+ | * [http://courses.csail.mit.edu/6.006/fall08/notes/recurrans.pdf recurrences practise] | ||
+ | |||
+ | |||
+ | |||
+ | === Searching === | ||
+ | ==== [http://courses.csail.mit.edu/6.006/fall08/notes/lecture12.pdf Lecture 12] : Intro to Searching, Graphs, small Rubiks problem ==== | ||
+ | ==== Rectation 12 (canceled) ==== | ||
+ | |||
+ | ==== [http://courses.csail.mit.edu/6.006/fall08/notes/lecture13.pdf Lecture 13] : Graph Searching : BFS, DFS==== | ||
+ | ==== Recitation 13 ==== | ||
+ | * (R1, R2) [http://courses.csail.mit.edu/6.006/fall08/notes/rec13.pdf notes] | ||
+ | |||
+ | ==== [http://courses.csail.mit.edu/6.006/fall08/notes/lecture14.pdf Lecture 14] : Graph Searching II : DAGs, topological sort ==== | ||
+ | ==== Recitation 14 ==== | ||
+ | * (R1, R2) [http://courses.csail.mit.edu/6.006/fall08/notes/rec14.pdf notes] | ||
+ | |||
+ | |||
+ | |||
+ | |||
+ | === Shortest Paths === | ||
+ | ==== [http://courses.csail.mit.edu/6.006/fall08/notes/lecture15.pdf Lecture 15] : Intro Shortest Paths : weighted graphs & general structure ==== | ||
+ | ==== Recitation 15 ==== | ||
+ | * (R1, R2, R5) [http://courses.csail.mit.edu/6.006/fall08/notes/rec15.pdf notes] | ||
+ | |||
+ | ==== [http://courses.csail.mit.edu/6.006/fall08/notes/lecture16.pdf Lecture 16] : Shortest Paths II : Bellman-Ford ==== | ||
+ | ==== Recitation 16 ==== | ||
+ | * (R1, R2) [http://courses.csail.mit.edu/6.006/fall08/notes/rec16.pdf notes] | ||
+ | |||
+ | ==== [http://courses.csail.mit.edu/6.006/fall08/notes/lecture17.pdf Lecture 17] : Shortest Paths III : Dijkstra ==== | ||
+ | ==== Recitation 17 ==== | ||
+ | * (R1, R2) [http://courses.csail.mit.edu/6.006/fall08/notes/rec17.pdf notes] | ||
+ | |||
+ | ==== [http://courses.csail.mit.edu/6.006/fall08/notes/lecture18.pdf Lecture 18] : Shortest Paths IV : further improvements ==== | ||
+ | * [https://courses.csail.mit.edu/6.006/fall08/handouts/protected/wagner.pdf Wagner paper] | ||
+ | |||
+ | |||
+ | |||
+ | |||
+ | === Dynamic Programming === | ||
+ | ==== [http://courses.csail.mit.edu/6.006/fall08/notes/lecture19.pdf Lecture 19] : Dynamic Programming I : Introduction ==== | ||
+ | ==== Recitation 19 : Quiz review ==== | ||
+ | * review packet | ||
+ | * see quiz prep | ||
+ | |||
+ | ==== [http://courses.csail.mit.edu/6.006/fall08/notes/lecture20.pdf Lecture 20] : Dynamic Programming II : Longest Common Subsequence ==== | ||
+ | ==== Recitation 20 ==== | ||
+ | * The 0-1 Knapsack problem | ||
+ | |||
+ | ==== [http://courses.csail.mit.edu/6.006/fall08/notes/lecture21.pdf Lecture 21] : Dynamic Programming III : Image Resizing, Matrix Chain Multiplication ==== | ||
+ | * [http://www.faculty.idc.ac.il/arik/IMRet-All.mov Video from lecture] (or the [http://www.youtube.com/watch?v=vIFCV2spKtg same video on Youtube]) | ||
+ | * [http://www.faculty.idc.ac.il/arik/papers/imret.pdf Image Resizing Paper] | ||
+ | |||
+ | ==== Recitation 21 ==== | ||
+ | |||
+ | ==== [http://courses.csail.mit.edu/6.006/fall08/notes/lecture22.pdf Lecture 22] : Dynamic Programming IV ==== | ||
+ | |||
+ | ==== Recitation 22 ==== | ||
+ | |||
+ | |||
+ | |||
+ | |||
+ | <br/><br/> | ||
+ | === Computability Theory === | ||
+ | ==== [http://courses.csail.mit.edu/6.006/fall08/notes/lecture23.pdf Lecture 23] : Computability I : Reductions ==== | ||
+ | |||
+ | ==== Recitation 23 ==== | ||
+ | |||
+ | |||
+ | <br/><br/> | ||
+ | === Numerics === | ||
+ | ==== [http://courses.csail.mit.edu/6.006/fall08/notes/lecture24.pdf Lecture 24] : Numerics I : Linear Equations and Least Squares ==== | ||
+ | |||
+ | ==== Recitation 24 ==== | ||
+ | |||
+ | |||
+ | ==== [http://courses.csail.mit.edu/6.006/fall08/notes/lecture25.pdf Lecture 25] : Numerics II : Givens Rotation ==== | ||
+ | |||
+ | ==== Recitation 25 ==== | ||
+ | |||
+ | |||
+ | <br/><br/> | ||
+ | === Beyond 6.006 === | ||
+ | ==== [http://courses.csail.mit.edu/6.006/fall08/notes/lecture26.pdf Lecture 26] : Beyond 6.006 ==== | ||
+ | * a.k.a. "Things You Don't Have To Know For The Final Exam" | ||
+ | ==== Recitation 26 ==== |
Latest revision as of 02:47, 12 December 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)
- (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
Lecture 11 : Radix sort
Quiz 1 Review (Recitation 11)
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, R5) notes
Lecture 16 : Shortest Paths II : Bellman-Ford
Recitation 16
- (R1, R2) notes
Lecture 17 : Shortest Paths III : Dijkstra
Recitation 17
- (R1, R2) notes
Lecture 18 : Shortest Paths IV : further improvements
Dynamic Programming
Lecture 19 : Dynamic Programming I : Introduction
Recitation 19 : Quiz review
- review packet
- see quiz prep
Lecture 20 : Dynamic Programming II : Longest Common Subsequence
Recitation 20
- The 0-1 Knapsack problem
Lecture 21 : Dynamic Programming III : Image Resizing, Matrix Chain Multiplication
Recitation 21
Lecture 22 : Dynamic Programming IV
Recitation 22
Computability Theory
Lecture 23 : Computability I : Reductions
Recitation 23
Numerics
Lecture 24 : Numerics I : Linear Equations and Least Squares
Recitation 24
Lecture 25 : Numerics II : Givens Rotation
Recitation 25
Beyond 6.006
Lecture 26 : Beyond 6.006
- a.k.a. "Things You Don't Have To Know For The Final Exam"