6.046J / 18.410J
Introduction to Algorithms
Spring 2003
Schedule
| |
|
6.046J / 18.410J |
| Sunday | Monday | Tuesday | Wednesday | Thursday | Friday | Saturday | |
|---|---|---|---|---|---|---|---|
| 5 | 26 | 27 | 28 | 29 | 30 | 31 | 1 |
| 6 | 2 | 3 | 4 Lecture 1: Intro, Insertion Sort, Mergesort Reading: Chapters 1-2 |
5
SIGN UP due by 8A.M. |
6 Lecture 2: Asymptotics, recurrences, master method Reading: Chapters 3-4, excluding 4.4 PS1 out |
7 Recitation: Correctness of Algorithms |
8 |
| 7 | 9 | 10 | 11 Lecture 3: Divide and Conquer: Strassen's algorithm, polynomial multiplication Reading: 28.2 , 30.1 |
12 | 13 Lecture 4: Randomized Algorithms: quicksort Reading: 5.1-5.3 and chapter 7 PS1 due, PS2 out |
14 Recitation: Randomized algorithms |
15 |
| 8 | 16 | 17 Presidents Day | 18
Monday Schedule No Class |
19 | 20 Lecture 5: Linear-time sorting, lower bounds, counting sort, radix sort Reading: 8.1-8.3 |
21 Recitation: Sorting, lower bounds |
22 |
| 9 | 23 | 24 | 25 Lecture 6:Median and Order Statistics Reading: Chapter 9 |
26 | 27 Lecture 7: Hashing Reading: 11.1-11.3 PS2 due, PS3 out |
28 Recitation: Quiz 1 review |
1 |
| Sunday | Monday | Tuesday | Wednesday | Thursday | Friday | Saturday | |
|---|---|---|---|---|---|---|---|
| 9 | 23 | 24 | 25 | 26 | 27 | 28 |
1 |
| 10 | 2 | 3 | 4 Quiz 1 |
5 | 6 Lecture 8:Binary Search Trees, Tree Walks Reading:12.1-12.3 |
7
ADD DATE Recitation: Relation of randomly built BSTs to quicksort Reading:12.4 |
8 |
| 11 | 9 | 10 | 11 Lecture 9: 2-3 Trees, B-trees Reading: 18.1 - 18.2 |
12 | 13 Lecture 10: Amortized Analysis: Disjoint sets Reading: Chapter 17 |
14 Recitation: Augmented Data Structures Reading: Chapter 14 |
15 |
| 12 | 16 | 17 | 18 Lecture 11: Greedy Algorithms, MST, Prim/Kruskal Reading: 16.1-16.3 ; 23 |
19 | 20 Lecture 12: Dynamic Programming, LCS, Optimal BST Reading: Chapter 15 PS3 due, PS4 out |
21 Recitation: Dynamic Programming vs Greedy |
22 |
| 13 | 23 | 24 spring break | 25
spring break No Class |
26 spring break | 27
spring break No Class |
28 spring break | 29 |
| 14 | 30 | 31 | 1 | 2 | 3 | 4 | 5 |
| Sunday | Monday | Tuesday | Wednesday | Thursday | Friday | Saturday | |
|---|---|---|---|---|---|---|---|
| 14 | 30 | 31 | 1 Lecture 13: Shortest path, Dijkstra, BFS Reading: 22.1, 22.2, pp 580-587, 24.3 |
2 | 3 Lecture 14: DFS, connected components Reading: 22.3 - 22.5 PS4 due, PS5 out |
4 Recitation: BFS, DFS |
5 |
| 15 | 6 | 7 | 8 Lecture 15: Network Flow, max-flow min-cut, Ford-Fulkerson Reading: 26.1 - 26.2 |
9 | 10 Lecture 16: Pattern matching Reading: chapter 32 PS5 due, PS6 out |
11 Recitation: Quiz 2 review |
12 |
| 16 | 13 | 14 | 15 Quiz 2 |
16 | 17 Lecture 17: FFT and polynomial multiplication Reading: 30.1 - 30.2 |
18 Recitation: Applications of FFT |
19 |
| 17 | 20 | 21 Patriot's Day | 22 Patriot's Other Day | 23 | 24
DROP DATE Lecture 18: Computational Number Theory Reading: 31.8 PS6 due, PS7 out |
25 Recitation: TBA |
26 |
| 18 | 27 | 28 | 29 Lecture 19: Computational Geometry I Reading: 33.2 |
30 | 1 | 2 | 3 |
| Sunday | Monday | Tuesday | Wednesday | Thursday | Friday | Saturday | |
|---|---|---|---|---|---|---|---|
| 18 | 27 | 28 | 29 | 30 | 1 Lecture 20: Computational Geometry II Reading: 33.4 |
2 Recitation: Computational Geometry |
3 |
| 19 | 4 | 5 | 6 Lecture 21: NP-completeness, poly-time reductions Reading: 34.1 - 34.2 |
7 | 8 Lecture 22: NP-Completeness II PS7 due |
9 Recitation: Example reductions |
10 |
| 20 | 11 | 12 | 13 Lecture 23: Approximation Algorithms Reading: 35.1 |
14 | 15 Lecture 24: Parallel Algorithms Reading: chapter 27 |
16 | 17 |
| 21 | 18 | 19 | 20 | 21 Final Exam Johnson Ice Rink 9:00-12:00 |
22 | 23 | 24 |
| 22 | 25 | 26 Memorial Day | 27 | 28 | 29 | 30 | 31 |