This page provides a tentative schedule for the course.
All reading materials are from the course textbook:
Introduction to Algorithms - 3rd ed. (CLRS)
Date Lecture Topics Reading Jan 18 Lecture 1: Intro to Algorithms Ch. 1 Jan 20,23 Lecture 2: Insertion Sort Ch. 2.1-2.2 Jan 25 Lecture 3: Asymptotic Notation Ch. 3 Jan 27 Lecture 4: Merge Sort Ch. 2.3 Jan 30 Lecture 5: Master Theorem
Assignment 1 Due 1/30Ch. 4.5 Feb 1 Lecture 6: Recurrence Ch. 4.3-4.4 Feb 3,6 Lecture 7: Heapsort
Assignment 2 Due 2/6Ch. 6 Feb 8 EXAM I - Due Feb 13 Feb 10 Lecture 8: Quicksort Ch. 7 Feb 13,15 Lecture 9: Linear Sorting Ch. 8 Feb 17,20 Lecture 10: Probabilistic Analysis
Assignment 3 Due 2/20Ch. 5 Feb 22 Lecture 11: Hash Tables Ch. 11 Feb 24 Assignment 4 Due 2/24 Feb 27, Mar 1,3 NO CLASS - WINTER BREAK Mar 6 Lecture 12: Dynamic Programming - Rod Cutting Ch. 15 Mar 8 Exam II Review
Empirical Comparison Report Due 3/8Mar 10 EXAM II - Due Mar 15
Empirical Comparison Report Due 3/10Mar 13 Lecture 12: Dynamic Programming - Rod Cutting Ch. 15 Mar 15 Lecture 13: Dynamic Programming - LCS Ch. 15 Mar 17 Lecture 14: Greedy Algorithms - Activity Selection Ch. 16 Mar 20 Lecture 15: Graph Theory
Assignment 5 Due 3/20Appendix B.4 Mar 22 Lecture 16: Breadth-First Search Ch. 22.2 Mar 24 Lecture 17: Depth-First Search
Assignment 6 Due 3/24Ch. 22.3 Mar 27 Lecture 18: DFS Applications Ch. 22.4-22.5 Mar 29 Exam III Review
Assignment 7 Due 3/29Mar 31 Exam III - Due Apr 5 Apr 3 Lecture 19: Minimum Spanning Trees - Kruskal Ch. 23.1 Apr 5 Lecture 20: Minimum Spanning Trees - Prim Ch. 23.2 Apr 7 Lecture 21: Shortest Path - Bellman-Ford Ch. 24.1-24.2 Apr 10 Lecture 22: Shortest Path - Dijkstra
SSSP Practice Activity SSSP SolutionCh. 24.3 Apr 10 Lecture 23: Shortest Path - Floyd-Warshall Ch. 25 Apr 12 Lecture 24: Maximal Flow Ch. 26.1 Apr 14, 17 NO CLASS - SPRING BREAK Apr 19 Lecture 25: Maximal Flow- Ford-Fulkerson
Max Flow Practice Activity Max Flow Solution
Assignment 8 Due 4/19Ch. 26.2 Apr 21 Lecture 26: NP Completeness Ch. 34.1-34.3 Apr 24 Lecture 27: NP Complete Problems Ch. 34.4 Apr 26 Lecture 28: More NP Complete Problems
Assignment 9 Due 4/26Ch. 34.5 Apr 28 Exam IV - Due May 3 May 1 Lecture 29: Approximation Algorithms Ch. 35.1-35.2 May 8,10 Final Project Presentations
