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 |