6.046 Course Calendar - Spring 2004

[back to homepage]
February      
Tuesday 3 Lecture 1
Introduction, Analysis of algorithms, insertion sort.
Reading: Chapter 1, 2.1, 2.2.
Register Online
PS1 Out
Thursday 5 Lecture 2
Asymptotic notation. Recurrences: substitution, iteration, recursion trees, master method, integer multiplication.
Reading: Chapters 3 and 4, excluding Section 4.4.
 
Friday 6 Recitation 1
Recurrences, sloppiness, Akra-Bazzi.
Reading: Akra-Bazzi Handout.
 
Tuesday 10 Lecture 3
Divide and conquer: merge sort, binary search, powering a number, computing Fibonacci numbers, Strassen's algorithm.
Reading: 2.3. 28.2, and 30.1
 
Thursday 12 Lecture 4
Quicksort, randomized algorithms.
Reading: 5.1-5.3; Chapter 7.
 
Friday 13 Recitation 2
Randomized quicksort high-probability analysis, Divide and Conquer examples.
PS1 Due
PS2 Out
Tuesday 17 No Lecture
 
Thursday 19 Lecture 5
Median and order statistics.
Reading: Chapter 9
 
Friday 20 Recitation 3
Sorting, heapsort, priority queues, applications of median.
Reading: Chapter 6
 
Tuesday 24 Lecture 6
Sorting Lower Bounds, Linear time sorting, counting sort, radix sort.
Reading: 8.1-8.3
PS2 Due
PS3 Out
Thursday 26 Lecture 7
Computational Number Theory.
Reading: 31.1-31.5
 
Friday 27 Recitation 4
Bucket Sort. Polynomial Identity Testing.
 
March      
Tuesday 2 Lecture 8
Computational Number Theory, RSA, Probabilistic Algorithms, Primality.
Reading: 31.7-31.8.
 
Thursday 4 Lecture 9
Fast Fourier Transforms
Reading: 30.1-30.2
 
Friday 5 Recitation 5
Computational Number Theory and FFT
PS3 Due
Tuesday 9 In-Class Quiz Review  
Wednesday 10 Quiz 1
7:30-9:30 PM, Room 2-190
 
Thursday 11 Lecture 10
Hashing
Reading: 11.1-11.3
PS4 Out
Friday 12 Recitation 6
Perfect Hashing.
 
Tuesday 16 Lecture 11
BSTs, B-Trees and 2-3 Trees
Reading: 12.1-12.3, 18.1-18.2
 
Thursday 18 Lecture 12
Skip Lists
Reading: Possible Handout
 
Friday 19 Recitation 7
Augmenting Data Structures
Reading: Chapter 14
PS4 Due
PS5 Out
Mon-Fri 22-26 Spring Break
 
Tuesday 30 Lecture 13
Computational Geometry, Range Queries.
Reading: 33.1-33.2.
 
April      
Thursday 1 Lecture 14
Amortized analysis: table doubling, potential method.
Reading: Chapter 17.
 
Friday 2 Recitation 8
Amortized Data Structures, Union-Find
Reading: Chapter 17.
PS5 Due
PS6 Out
Tuesday 6 Lecture 15
Dynamic programming: optimal binary search trees, longest common subsequence.
Reading: Chapter 15.
 
Thursday 8 Lecture 16
Graphs and Greedy algorithms: minimum-spanning trees, Prim's and Kruskal's algorithms.
Reading: 16.1-16.3, Chapter 23.
 
Friday 9 Recitation 9
Greedy vs. Dynamic Programming.
 
Tuesday 13 Lecture 17
Shortest Paths: Dijkstra's Algorithm, Breadth-First Search
Reading: 22.1-22.3, pages 580-587, 24.3
 
Thursday 15 Lecture 18
Shortest Paths: Bellman-Ford Reading: 24.1-24.2, 24.4-24.5
 
Friday 16 Recitation 10
Quiz 2 Review
PS6 Due
Tuesday 20 No Lecture: Patriot's Day
 
Wednesday 21 Evening Quiz 2
Thursday 22 Lecture 19
Graph algorithms: all-pairs shortest paths, matrix multiplication, Floyd-Warshall algorithm, difference constraints.
Reading: 25.1-25.2.
Drop Day
Friday 23 Recitation 11
Graph Algorithm Review
Reading: 26.3
PS7 Out
Tuesday 27 Lecture 20
Complexity: P vs. NP, efficient verification.
Reading: 34.1-34.2.
 
Thursday 29 Lecture 21
NP-Completeness, Polynomial-time reductions.
Reading: 34.3-34.5.
 
Friday 30 Recitation 12
NP-Completeness, Approximation Algorithms.
 
May      
Tuesday 4 Lecture 22
NP-Completeness, Approximation Algorithms.
Reading: 35.1.
 
Thursday 6 Lecture 23
Network Flow, Max-Flow Min-Cut Theorem, Ford-Fulkerson
Reading: 26.1-26.1
 
Friday 7 Recitation 13
Matching algorithms. Hard Problems.
Reading: 26.3
PS7 Due
Practice PS8 Out
Tuesday 11 Lecture 24
Floating Point Arithmetic
Guest Lecturer: Alan Edelman
 
Thursday 13 Lecture 25
Folding and Unfolding in Computational Geometry
 
Monday 17 Final Exam
Johnson (Ice Rink), 9-12am