Introduction to Algorithms Massachusetts Institute of Technology Professors Shafi Goldwasser and Silvio Micali
September 3, 2003 6.046J/18.410J Handout 2
Course Outline September Wed
3
Lecture 1 Administrivia. Introduction: analysis of algorithms, insertion sort. Reading: Chapter 1, 2.1, 2.2.
Reg. out. Reg. due 4:30pm
Fri
5
Recitation 1 Correctness of algorithms. Reading: Kingston chapter.
PS 1 out.
Mon
8
Lecture 2 Asymptotic notation. Recurrences: substitution, iteration, master method. Reading: Chapters 3–4, excluding Section 4.4.
Wed
10
Lecture 3 Divide and conquer: merge sort, Strassen’s algorithm, polynomial and integer multiplication. Reading: 2.3. 28.2, and 30.1
Fri
12
Recitation 2 Recurrences, Divide and conquer examples.
Mon
15
Lecture 4 Randomized algorithms: quicksort. Reading: 5.1-5.3; Chapter 7.
Wed
17
Lecture 5 Sorting Lower Bounds, Linear time sorting, counting sort, radix sort. Reading: Sections 8.1-8.3
Fri
19
Recitation 3 Sorting: heapsort, priority queues, dynamic sets. Reading: Chapter 6
Mon
22
Student Holiday–No class
Wed
24
Lecture 6 Median and order statistics Reading: Chapter 9
Fri
26
Recitation 4 Bucket Sort; Applications of median.
Mon
29
Lecture 7 Hashing Reading: 11.1-11.3
October
PS 1 due. PS 2 out.
PS 2 due. PS 3 out.
Handout 2: Course Outline
2
Wed
1
Lecture 8 Binary search trees, tree walks, relation to quicksort. Reading: Sections 12.1–12.3
Fri
3
Recitation 5 Quiz 1 Review. ADD DATE.
Mon
6
Lecture 9 Balanced search trees: AVL, Red-Black Trees. Reading: Chapter 18.1–18.2
Wed
8
QUIZ 1: in-class test.
Fri
10
Recitation 6 Additional balanced search trees. Reading: Chapter 13.
Mon
13
Columbus Day–No class
Wed
15
Lecture 10 Augmenting data structures: dynamic order statistics, interval trees. Reading: Chapter 14.
Fri
17
Recitation 7 Examples of augmentation. Reading: Chapter 14.
Mon
20
Lecture 11 Greedy algorithms: minimum-spanning trees, Prim’s and Kruskal’s algorithms. Reading: Sections 16.1–16.3, Chapter 23.
Wed
22
Lecture 12 Dynamic programming: optimal binary search trees, longest common subsequence. Reading: Chapter 15.
Fri
24
Recitation 8 Examples of greedy algorithms and dynamic programming.
Mon
27
Lecture 13 Amortized analysis: table doubling, potential method. Reading: Chapter 17.
Wed
29
Lecture 14 Graph algorithms: depth-first search, topological sort, strongly-connected components. Reading: Sections 22.3–5.
Fri
31
Recitation 9 Competitive Analysis, self-organizing lists.
November
PS 3 due.
PS 4 out.
PS 4 due. PS 5 out.
PS 5 due. PS 6 out.
Handout 2: Course Outline
Mon
3
Lecture 15 Graph algorithms: single-source shortest paths, Dijkstra’s algorithm, Bellman-Ford algorithm. Reading: Sections 25.1–3.
Wed
5
Lecture 16 Graph algorithms: all-pairs shortest paths, matrix multiplication, Floyd-Warshall algorithm, difference constraints. Reading: Sections 25.1, 25.2.
Fri
7
Recitation 10 Graph algorithms. Reading: Chapters 23–26
Mon
10
Veterans Day–No class
Wed
12
Lecture 17 Matching algorithms. Reading: Section 26.3.
Fri
14
Recitation 11 Quiz 2 Review. Reading: Section 26.3.
Mon
17
Lecture 18 Network flow: max-flow min-cut, Ford-Fulkerson algorithm, augmenting paths. Reading: Sections 26.1–2.
Wed
19
In class quiz
Fri
21
Recitation 12 Network Flow, Bipartite Matching. Reading:
Mon
24
Lecture 19 Computational Number Theory. Reading: Sections 31.1-31.5.
Wed
26
Lecture 20 Computational Number Theory, RSA, Probabilistic Algorithms, Primality. Reading: Section 31.7,31.8.
Fri
28
Thanksgiving–No class
December Mon
1
Lecture 21 Fast Fourier Transform, Integer Multiplication. Reading: Sections 30.1,30.2.
Wed
3
Lecture 22 Complexity: P vs. NP, efficient verification. Reading: Sections 34.1, 34.2.
3
PS 6 due. PS 7 out.
PS 7 due. PS 8 out.
Handout 2: Course Outline
4
Fri
5
Recitation 13 FFTs and basic NP-completeness notions
Mon
8
Lecture 23 NP-completeness 1, Polynomial time reductions. Reading: Chapter 34.3–34.5.
Wed
10
Lecture 24 NP-Completeness and approximation algorithms. Reading: Chapter 35.1.
Thur
18
FINAL EXAM
PS 8 due. PS 9 out.
9:00–12:00 duPont
