Introduction to Algorithms  - Fall 2007 (Calendar) 

• Week 1:
• Lecture 01 (09/05): Administrivia, Course overview, Insertion Sort, Mergesort. (Reading: CLRS Chapters 1, 2).  PS 1 Out
• Week 2:
  
• Lecture 02 (09/10): Correctness of  algorithms (invariants, induction). (Reading: Chapters 2.1,  31.1, 31.2).
  
• Lecture 03 (09/12): Analysis of algorithms: Worst-case, big-Oh notation, Recurrences. (Reading: Chapters 3, 4.1-4.3).
  
• Week 3:
  
• Lecture 04 (09/17): Divide and Conquer algorithms. (Reading: Chapters 28.2 and 30.1).  PS 1 Due, Ps 2 Out.
• Lecture 05 (09/19): Randomized Quick Sort. (Reading: Chapter 7).
  
• Week 4:
  
• Monday 09/24: Student Holiday - No lecture
• Lecture 06 (09/26): Linear time median. (Reading: Chapters 9.2, 9.3).
  
• Week 5:
  
• Lecture 07 (10/01): Lower bounds on algorithms: in comparison-based model. Counting sort. (Reading: Chapter 8). PS 2 Due.
  
• Lecture 08 10/03: Data Structures for Priority Queues: Heaps. (Reading: Chapter 6).
  
• Friday 10/05: Add date
• Week 6:
  
• Monday 10/08: Columbus Day Holiday - No lecture
• Wednesday (10/10): Quiz 1.
• Week 7:
  
• Lecture 09 (10/15): Dynamic Programming - 1. (Reading: Chapter 15.1, 22.1, 22.2). Ps 3 Out.
  
• Lecture 10 (10/17): Dynamic Programming - 2. (Reading: Chapter 15.4).
• Week 8:
  
• Lecture 11 (10/22): Greedy algorithm for MST (Reading: Chapter 23).
  
• Lecture 12 (10/24): Data Structures: Balanced Trees, 2-3 Trees. (Reading: Chapters 12.1, 12.2, 12.3). PS 3 Due, PS 4 Out.
• Week 9:
  
• Lecture 13 (10/29): 2-3 Trees (contd.) (Reading: Lecture Notes).
  
• Lecture 14 (10/31): Data Structure Augmentation. (Reading: Chapter 14).
  
• Friday (11/02): Quiz 2 Review in Recitation. PS 4 Due.
• Week 10:
  
• Lecture 15 (11/05): Mandatory lecture - Take home Quiz 2 given out.
  
• Wednesday 11/07: No lecture due to Quiz 2
• Friday 11/09: Quiz 2 due at noon. No recitations.
• Week 11:
  
• Monday 11/12: Veteran's Day Holiday - No lecture
• Lecture 16 (11/14):  Hash tables. (Reading: Chapters 11.1, 11.2, 11.3). PS 5 Out.
• Week 12:
  
• Lecture 17 (11/19): Shortest Path Algorithms. (Reading: Chapter 24).
• Lecture 18 (11/21): Shortest Path Algorithms. (Reading: Chapter 24). Drop Date
• Friday 11/23: Thanksgiving (no recitation)
• Week 13:
  
• Lecture 19 (11/26): Lower bounds on algorithms: "hierarchy" theorems, NP-completeness. (Reading: Chapter 34). PS 5 Due, PS 6 Out.
  
• Lecture 20 (11/28): NP problems, Reductions, Completeness. (Reading: Chapter 34).
  
• Week 14:
  
• Lecture 21 (12/03): Independent set is NP-Complete (assuming NP-completeness of SAT). (Reading: Chapter 34).
• Lecture 22 (12/05): Approximation?
• Friday (12/07): PS 6 Due in Recitation.
• Week 15:
  
• Lecture 23 (12/10): Clustering algorithms
  
• Lecture 24 (12/12): Sublinear algorithms (Last day of classes - no recitation on Friday).
  
• Week 16:
  
• Final Exam (12/18): Final Exam -- Tuesday, December 18, 1:30-4:30pm, Johnson Track