6.046J / 18.410J |
Sunday | Monday | Tuesday | Wednesday | Thursday | Friday | Saturday | |
---|---|---|---|---|---|---|---|
5 | 27 | 28 | 29 | 30 | 31 | 1 | 2 |
6 | 3 | 4 | 5
Lecture 1: Intro, Insertion Sort, Mergesort Reading: Chapters 1-2 PS0 out |
6
PS0 due by 8A.M. |
7
Lecture 2: Asymptotics, recurrences, master method Reading: Chapters 3-4, excluding 4.4 PS1 out |
8
Recitation: Correctness of Algorithms |
9 |
7 | 10 | 11 | 12
Lecture 3: Divide and Conquer: Strassen's algorithm, polynomial multiplication Reading: 28.2 , 30.1 |
13 | 14
Lecture 4: Randomized Algorithms: quicksort Reading: 5.1-5.3 and chapter 7 PS1 due, PS2 out |
15
Recitation: Recurrences, Akra-Bazzi |
16 |
8 | 17 | 18 Presidents Day | 19 Monday Schedule
No Class |
20 | 21
Lecture 5: Linear-time sorting, lower bounds, counting sort, radix sort Reading: 8.1-8.3 |
22
Recitation: |
23 |
9 | 24 | 25 | 26
Lecture 6:Median and Order Statistics (randomized, deterministic) Reading: Chapter 9 |
27 | 28
Lecture 7: Hashing in expected constant time, universal hashing Reading: 11.1-11.3 PS2 due |
1 | 2 |
Sunday | Monday | Tuesday | Wednesday | Thursday | Friday | Saturday | |
---|---|---|---|---|---|---|---|
9 | 24 | 25 | 26 | 27 | 28 | 1
Recitation: Quiz 1 review |
2 |
10 | 3 | 4 | 5
Quiz 1 |
6 | 7
Lecture 9:Binary Search Trees, Tree Walks Reading:12.1-12.3 PS3 out |
8
Recitation: Relation of randomly built BSTs to quicksort |
9 |
11 | 10 | 11 | 12
Lecture 10: Balanced Trees: B-trees Reading: Chapter 18 |
13 | 14
Lecture 11: Amortized Analysis: table doubling, potential method Reading: Chapter 17 |
15
Recitation: Red-Black trees Reading: Chapter 13 |
16 |
12 | 17 | 18 | 19
Lecture 12: Dynamic Programming: Optimal Binary Search Trees, Longest Common Subsequence Reading: Chapter 15 |
20 | 21
Lecture 13: Priority Queues, Heaps, Dynamic Sets Reading: Chapter 6 PS3 due, PS4 out |
22
Recitation: |
23 spring break |
13 | 24 spring break | 25 spring break | 26 spring break
No Class |
27 spring break | 28 spring break
No Class |
29 spring break | 30 spring break |
14 | 31 spring break | 1 | 2 | 3 | 4 | 5 | 6 |
Sunday | Monday | Tuesday | Wednesday | Thursday | Friday | Saturday | |
---|---|---|---|---|---|---|---|
14 | 31 | 1 | 2
Lecture 14: Disjoint Set Data Structure Reading: Chapter 21 |
3 | 4
Lecture 15: Minimum Spanning Tree: Prim, Kruskal, Greedy Algorithms Reading: 16.2 and chapter 23 PS4 due, PS5 out |
5
Recitation: Greedy Algorithms: Huffman codes, activity selection. Reading: 16.1 and 16.3 |
6 |
15 | 7 | 8 | 9
Lecture 16: Graph Algorithms: DFS, strongly connected components Reading: 22.1, 22.3, and 22.5 |
10 | 11
Lecture 17: Shortest Path: Dijkstra, Bellman-Ford Reading: 22.2, pages 580-587, 24.3, 24.1 PS5 due, PS6 out |
12
Recitation: Topological Sort and Shortest Path in DAGs Reading: 22.4 and 24.2 |
13 |
16 | 14 | 15 Patriots Day | 16 Patriots other day
No Class |
17 | 18
Lecture 18: Network flows: Max-flow min-cut theorem, Ford-Fulkerson Algorithm Reading: 26.1-26.2 |
19
Recitation: Edmonds-Karp Algorithm |
20 |
17 | 21 | 22 | 23
Lecture 19: Pattern Matching Reading: Chapter 32 except 32.3 |
24 | 25
Lecture 20: Quiz 2 preparation; attendance mandatory Quiz 2 out; PS6 due |
26
No Recitation |
27 |
18 | 28 | 29 | 30
Lecture 21: Computational Geometry I: closest pair Reading: 33.4 Quiz 2 due |
1 | 2 | 3 | 4 |
Sunday | Monday | Tuesday | Wednesday | Thursday | Friday | Saturday | |
---|---|---|---|---|---|---|---|
18 | 28 | 29 | 30 | 1 | 2
Lecture 22: Computational Geometry II: segment Intersection Reading: 33.1-33.2 PS7 out |
3
Recitation |
4 |
19 | 5 | 6 | 7
Lecture 23: Complexity Theory I: polynomial-time reductions, SAT as a hard problem, reductions to SAT, intuition about NP Reading: 34.1 - 34.2 |
8 | 9
Lecture 24: Complexity Theory II: reductions from SAT, NP-completeness Reading: 34.3-34.5 PS7 due |
10
Recitation |
11 |
20 | 12 | 13 | 14
Lecture 25: Approximation Algorithms: set cover, TSP Reading: 35.2-35.3 |
14 | 16
Lecture 26: Parallel Algorithms Reading: chapter 27 |
17 | 18 |
21 | 19 | 20 | 21 | 22 | 23 | 24 | 25 |
22 | 26 | 27 Memorial Day | 28 | 29 | 30 | 31 | 1 |