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