| Date | Activity | Topic | GT Readings | Auxiliary CLRS Readings |
| WEEK 1 | ||||
| Tue Jan 17 | Pre-Reading: | Required Background material | GT 1.1-1.4 | |
| Wed Jan 18 | Lecture 1: | Intro to design and analysis of algorithms | GT 2.1-2.6 | Review CLRS A.1. Read CLRS 1.1-2 \& 2.1. |
| Thu Jan 19 | Recitation 0: | Prepare for Homework 0 (due 11:59pm, Mon Jan 23) | ||
| WEEK 2 | ||||
| Mon Jan 23 | Homework 0: | Submit on GradeScope by 11:59pm | ||
| Mon Jan 23 | Lecture 2A: | Asymptotic complexity; recurrences; design techniques: incremental, divide \& conquer, two-finger. | GT 3.1-3.3, 3.5 | Review CLRS A.2, Read CLRS 2.2-2.3, 3.1, 4.0, and skim 3.2. |
| Wed Jan 25 | Lecture 2B: | Solving recurrences: recursion tree, proof by induction | GT 3.6, 3.7 | CLRS 4.4, 4.3, 4.5 (we recommend reading in that order). |
| Thu Jan 26 | Recitation 1: | Prepare for Homework 1 (due 11:59pm, Mon Jan 30) | ||
| WEEK 3 | ||||
| Mon Jan 30 | Homework 1: | Submit on GradeScope by 11:59pm | ||
| Mon Jan 30 | Lecture 3A: | Master Method and More Sorting Strategies | GT 4.1-4.7 | 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 01 | Lecture 3B: | Asymptotic Complexity of the Sorting Problem and Sorting Algorithms | GT 4.5 | CLRS 6.1-6.4, 7.1-7.2, 8.1 Begin reading C.1, C.2, 5.1. |
| Thu Feb 02 | Recitation 2: | Prepare for Homework 2 (due 11:59pm, Mon Feb 06) | ||
| WEEK 4 | ||||
| Mon Feb 06 | Homework 2: | Submit on GradeScope by 11:59pm | ||
| Mon Feb 06 | Lecture 4A: | Decision Tree Model, Sorting Problem Lower Bound, Counting Sort, Radix Sort | GT 5.1-5.3 | CLRS 8.1-8.3 |
| Wed Feb 08 | Lecture 4B: | Indicator Random Variables, Randomized Quicksort, Selection | GT 5.4, 5.5 | CLRS 5.2-5.3, 9.1-9.3 |
| Thu Feb 09 | Recitation 3: | Prepare for Homework 3 (due 11:59pm, Mon Feb 13) | ||
| WEEK 5 | ||||
| Mon Feb 13 | Homework 3: | Submit on GradeScope by 11:59pm | ||
| Mon Feb 13 | Lecture 4C: | Catchup, Review Block 1 and Introduce Dynamic Programming | GT 6.1-6.3 | Introduce Block 2 |
| Wed Feb 15 | Exam 1: | Covers Block 1 (Lectures 1-4) | ||
| Thu Feb 16 | Recitation 4: | Prepare for Homework 4 (due 11:59pm, Mon Feb 20) | NO TOKENS | |
| Thu Feb 16 | Project 1: | Will be assigned and due with Homework 4. | ||
| WEEK 6 | ||||
| Mon Feb 20 | Homework 4: | Submit on GradeScope by 11:59pm | ||
| Mon Feb 20 | No Class: | Presidents' Day Observed (University Holiday) | ||
| Wed Feb 22 | Lecture 5A: | Dynamic Programming: Branch \& Bound, Greedy Algorithms | GT 6.4-6.7 | CLRS 15.1-15.4 |
| Thu Feb 23 | Lecture 5B: | Optimal binary search trees AND Dynamic Programming Recitation (readings from CLRS) | CLRS 15.5 | |
| Thu Feb 23 | Begin Homework 5 (due 11:59pm, Mon Feb 27) | |||
| Thu Feb 23 | Project 2: | Will be assigned and due with Homework 7. | ||
| WEEK 7 | ||||
| Mon Feb 27 | Homework 5: | Submit on GradeScope by 11:59pm | ||
| Mon Feb 27 | Lecture 6A: | Algorithmic Paradigms Review. Backtrack Programming. KMP String Matching. | GT 7.1-7.4 | CLRS 32.1, 32.4. |
| Wed Mar 01 | Lecture 6B: | Review of Types of Analysis. Amortized Analysis. | GT 7.6 | CLRS 17.1-17.4 |
| Thu Mar 02 | Recitation 6: | Prepare for Homework 6 (due 11:59pm, Mon Mar 06) | ||
| WEEK 8 | ||||
| Mon Mar 06 | Homework 6: | Submit on GradeScope by 11:59pm | ||
| Mon Mar 06 | Lecture 7A: | Dynamic abstract data types amd candidate data structures. | GT 8.1-8.5, 8.7-8.12 | CLRS Intro to Part III, Chapter 10.1-10.3, and Chapter 12.1-12.3. |
| Wed Mar 08 | Lecture 7B: | Red-Black Trees and other balanced trees (consult CLRS also) | GT 9.1-9.6 | CLRS 13.1-13.4 |
| Thu Mar 09 | Recitation 7: | Prepare for Homework 7 (due 11:59pm, Mon Mar 13) | ||
| WEEK 9 | ||||
| Mon Mar 13 | Homework 7: | Submit on GradeScope by 11:59pm | ||
| Mon Mar 13 | Lecture 8A: | Augmenting data structures | CLRS 14.1-14.3 | |
| Wed Mar 15 | Lecture 8B: | Hashing | GT 10.1-10.6 | CLRS 11.1-11.4 |
| Thu Mar 16 | Recitation 8: | Prepare for Homework 8 (due 11:59pm, Mon Mar 27) | ||
| WEEK 10 | ||||
| Mon Mar 20 | No Class: | Spring Break | ||
| Wed Mar 22 | No Class: | Spring Break | ||
| WEEK 11 | ||||
| Mon Mar 27 | Homework 8: | Submit on GradeScope by 11:59pm | NO TOKENS | |
| Mon Mar 27 | Lecture 9A: | Graphs, Breadth First Search, Depth First Search | GT 11.1-11.5 | CLRS 22.1-22.3 |
| Wed Mar 29 | Exam 2: | Covers Block 2 (Lectures 5-8) | ||
| Thu Mar 30 | Recitation 9: | Prepare for Homework 9 (due 11:59pm, Mon Apr 03) | ||
| WEEK 12 | ||||
| Mon Apr 03 | Homework 9: | Submit on GradeScope by 11:59pm | ||
| Mon Apr 03 | Lecture 10A: | Cut vertices, Biconnected components | GT 12.1 | CLRS Problem 22.2, pp. 621ff. |
| Wed Apr 05 | Lecture 10B | Topological sort, Strongly Connected Components | GT 12.2 | CLRS 22.4, 22.5 |
| Thu Apr 06 | Recitation 10: | Prepare for Homework 10 (due 11:59pm, Mon Apr 10) | ||
| WEEK 13 | ||||
| Mon Apr 10 | Homework 10: | Submit on GradeScope by 11:59pm | ||
| Mon Apr 10 | Lecture 11A: | Minimum spanning trees (and needed data structure) | GT 13.1-13.8, 13.10 | CLRS 23. CLRS 21.1, 21.2. |
| Wed Apr 12 | Lecture 11B: | Single Source Shortest Paths: Two Algorithms | GT 14.1-14.6 | CLRS 24.1-24.3 |
| Thu Apr 13 | Recitation 11: | Prepare for Homework 11 (due 11:59pm, Mon Apr 17) | ||
| WEEK 14 | ||||
| Mon Apr 17 | Homework 11: | Submit on GradeScope by 11:59pm | ||
| Wed Apr 19 | No Class: | Make-up Day | ||
| Thu Apr 20 | Recitation 11: | Prepare for Homework 11 (due 11:59pm, Mon Apr 24) | ||
| Fri Apr 21 | Lecture 12A: | All Pairs Shortest Path (Tufts Monday Schedule) | GT 15.1 | CLRS Intro to 25, 25.2. |
| WEEK 15 | ||||
| Mon Apr 24 | Homework 11: | Submit on GradeScope by 11:59pm | ||
| Mon Apr 24 | Lecture 13A: | Fibonacci heaps (readings from CLRS only) | CLRS 19.1-19.4 (note: ch. 20 in 2nd ed.) | |
| Wed Apr 26 | Lecture 13B: | Lower bounds, upper bounds, reduction, NP-completeness | GT 16.1-16.8 | CLRS 34.1-34.5 |
| Thu Apr 27 | Recitation 12: | Prepare for Homework 12 (due 11:59pm, Mon May 01) | ||
| WEEK 16 | ||||
| Mon May 01 | Homework 12: | Submit on GradeScope by 11:59pm | ||
| Mon May 01 | Final Lecture: | Approximation Algorithms and Final Summary | GT 16.7, 17.1-17.3 | |
| WEEK 17 | ||||
| Wed May 10 | Final Exam: | Cumulative Exam with extra focus on Block 3 (7pm-9pm) | ||