Words in parentheses (like this) are hints that will advise the student on the relative importance of a given topic, and are not part of the section titles in the respective books.
| Date | Activity | Topic | GT Readings | CLRS Readings |
| Tue Jan 18 | Lecture 0: | Required Background material | - 27.1 - 27.2 - 27.3 - 27.5 |
|
| Wed Jan 19 | Lecture 1: | Intro to design and analysis of algorithms | - 27.4 - 1.1 - 1.2 - 1.3 - 1.4 |
Review CLRS A.1. Read CLRS 1.1-2 \& 2.1. |
| Mon Jan 24 | Lecture 2A: | Asymptotic complexity; recurrences; design techniques: incremental, divide \& conquer, two-finger. | - 4.0 - 4.1 - 4.2 - 15.0 - 15.1 |
Review CLRS A.2, Read CLRS 2.2-2.3, 3.1, 4.0, and skim 3.2. |
| Wed Jan 26 | Lecture 2B: | Solving recurrences: recursion tree, proof by induction | - 15.2 |
CLRS 4.4, 4.3, 4.5 (we recommend reading in that order). |
| Mon Jan 31 | Lecture 3A: | Master Method and More Sorting Strategies | - 3.0 - 3.1 - 3.2 - 3.3 - 3.4 - 3.5 - 4.3 |
Review CLRS 4.5. Read the Introduction to Part II, pp 147-150. Begin reading 6.1, 6.4, 7.1, 7.2, 8.1. |
| Wed Feb 02 | Lecture 3B: | Asymptotic Complexity of the Sorting Problem and Sorting Algorithms | (empty) | CLRS 6.1-6.4, 7.1-7.2, 8.1 Begin reading C.1, C.2, 5.1. |
| Mon Feb 07 | Lecture 4A: | Decision Tree Model, Sorting Problem Lower Bound, Counting Sort, Radix Sort | - 4.4 - 5.0 - 5.1 - 5.2 |
CLRS 8.1-8.3 |
| Wed Feb 09 | Lecture 4B: | Indicator Random Variables, Randomized Quicksort, Selection | - 5.3 |
CLRS 5.2-5.3, 9.1-9.3 |
| Mon Feb 14 | Lecture 4C: | Catchup and Review Block 1 | (empty) | Introduce Block 2 |
| Wed Feb 23 | Lecture 5A: | Dynamic Programming: Branch \& Bound, Greedy Algorithms | - 6.0 - 6.1 - 18.5 - 7.0 - 7.1 - 7.2 - 7.3 - 7.6 |
CLRS 15.1-15.4 |
| Thu Feb 24 | Lecture 5B: | Optimal binary search trees AND Dynamic Programming Recitation | (empty) | CLRS 15.5 |
| Mon Feb 28 | Lecture 6A: | Algorithmic Paradigms Review. Backtrack Programming. KMP String Matching. | (empty) | CLRS 32.1, 32.4. |
| Wed Mar 02 | Lecture 6B: | Review of Types of Analysis. Amortized Analysis. | - 1.5 |
CLRS 17.1-17.4 |
| Mon Mar 07 | Lecture 7A: | Dynamic abstract data types amd candidate data structures. | - 2.0 - 2.1 - 2.2 - 2.3 - 2.4 - 8.0 - 8.1 - 8.2 - 8.3 - 8.4 - 8.5 |
CLRS Intro to Part III, Chapter 10.1-10.3, and Chapter 12.1-12.3. |
| Wed Mar 09 | Lecture 7B: | Red-Black Trees and other balanced trees | - 9.0 - 9.1 - 9.2 - 9.3 - 20.3 - 9.4 |
CLRS 13.1-13.4 |
| Mon Mar 14 | Lecture 8A: | Augmenting data structures | (empty) | CLRS 14.1-14.3 |
| Wed Mar 16 | Lecture 8B: | Hashing | - 10.0 - 10.1 - 10.2 - 10.3 - 10.4 - 10.6 |
CLRS 11.1-11.4 |
| Mon Mar 28 | Lecture 9A: | Graphs, Breadth First Search, Depth First Search | - 11.0 - 11.1 - 11.2 - 11.3 - 11.4 |
CLRS 22.1-22.3 |
| Wed Mar 30 | Lecture 9B: | Cut vertices, Biconnected components | - 11.6 |
CLRS Problem 22.2, pp. 621ff. |
| Mon Apr 11 | Lecture 10A | Topological sort, Strongly Connected Components | - 11.5 |
CLRS 22.4, 22.5 |
| Wed Apr 13 | Lecture 10B: | Minimum spanning trees (and needed data structure) | - 12.0 - 12.1 - 12.2 - 14.0 - 14.1 - 14.3 - 12.3 - 3.6 - 12.4 |
CLRS 23. CLRS 21.1, 21.2. |
| Wed Apr 20 | Lecture 11A: | Single Source Shortest Paths: Two Algorithms | - 13.0 - 13.1 - 13.2 - 13.3 - 13.4 - 13.5 |
CLRS 24.1-24.3 |
| Fri Apr 22 | Lecture 11B: | Tufts Virtual Monday: All Pairs Shortest Path | - 13.6 |
CLRS Intro to 25, 25.2. |
| Mon Apr 25 | Lecture 12A: | Fibonacci heaps | (empty) | CLRS 19.1-19.4 (note: ch. 20 in 2nd ed.) |
| Wed Apr 27 | Lecture 12B: | Lower bounds, upper bounds, reduction, NP-completeness | - 17.0 - 17.1 - 17.2 - 17.3 - 17.4 - 17.5 - 17.6 - 17.7 |
CLRS 34.1-34.5 |
| Mon May 02 | Final Lecture: | - 17.7 - 18.0 - 18.1 - 18.2 - 18.4 |