6.046J / 18.410J
Introduction to Algorithms
Spring 2002

Schedule
February 2002
 SundayMondayTuesdayWednesdayThursdayFridaySaturday
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


March 2002
 SundayMondayTuesdayWednesdayThursdayFridaySaturday
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


April 2002
 SundayMondayTuesdayWednesdayThursdayFridaySaturday
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


May 2002
 SundayMondayTuesdayWednesdayThursdayFridaySaturday
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