| DATE | ACTIVITY | TOPIC | READINGS (CLRS 4th ed.) | |
| WEEK 1 | ||||
| Thu. Jan. 18 | Lecture 0 | Intro to design and analysis of algorithms | 1.1, 1.2, 2.1 (review A.1–2) | |
| Thu.-Fri. Jan. 18-19 | Recitation 0 | Prepare for HW 0 (due 11:59pm, Monday Sep. 12) | ||
| WEEK 2 | ||||
| Tue. Jan. 23 | Homework 0 | Submit on Gradescope by 11:59pm | ||
| Tue. Jan. 23 | Lecture 1A | InsertionSort, asymptotic complexity (big-O etc.) | 2.2, 2.3, 3.1, 3.2 (skim 3.3) | |
| Thu. Jan. 23 | Lecture 1B | MergeSort, Recurrence relations, proving recurrence by induction, recursion trees | 4.1–4.4 | |
| Thu.-Fri. Jan. 23-24 | Recitation 1 | Prepare for HW 1 | ||
| WEEK 3 | ||||
| Tues. Jan 30 | Homework 1 | Submit on Gradescope by 11:59pm | ||
| Tue. Jan 30 | Lecture 2A | Master method for solving recurrences; heaps | 4.5, Part II intro, 6.1 | |
| Thu. Feb. 1 | Lecture 2B | Heapsort and Quicksort | 6.2–6.5, 7.1, 7.2 | |
| Thu.-Fri. Feb. 1-2 | Recitation 2 | Prepare for HW 2 | ||
| WEEK 4 | ||||
| Tue. Feb. 6 | Homework 2 | Submit on Gradescope by 11:59pm | ||
| Tue. Feb. 6 | Lecture 3A | Decision Trees, Sorting Lower Bound, Counting Sort, Radix Sort | 8.1–8.3 | |
| Thu. Feb. 8 | Lecture 3B | Selection, Randomized algorithms (Quicksort, Selection) | 9.1–9.3, 7.3, 7.4 | |
| Thu.-Fri. Feb 8-9 | Recitation 3 | Prepare for HW 3 | ||
| WEEK 5 | ||||
| Tue. Feb. 13 | Homework 3 | Submit on Gradescope by 11:59pm; | ||
| Tue. Feb. 13 | Lecture 4A | Catchup and Review | ||
| Thu. Feb. 15 | EXAM 1 | Midterm Exam 1 (Lectures 0--4) | ||
| Thu.-Fri, Feb. 15-16 | Recitation 4 | go over exam? introduce greedy/DP? | ||
| WEEK 6 (and beyond) TBD | ||||
| Tue. Feb. 20 | Lecture 5A | Greedy Algorithms, Dynamic Programming | CLRS 4th ed., 14.1–14.3 (CLRS 3rd ed., 15.1-15.3) | |
| Thu. Feb. 22 | NO CLASS | TUFTS MONDAY SCHEDULE | ||
| Thu-Fri. Feb. 22-23 | NO Recitation | TUFTS MONDAY SCHEDULE | ||
| WEEK 7 | ||||
| Tue. Feb. 27 | Homework 4 | Submit on Gradescope by 11:59pm | ||
| Tue. Feb. 27 | Lecture 6A | More Dynamic Programming | CLRS 4th ed., 14.4 (CLRS 3rd ed., 15.4) | |
| Thu. Feb. 29 | Lecture 6B | Amortized Analysis | CLRS 4th ed., 16.1–16.4 (CLRS 3rd ed., 17.1–17.4) | |
| Thu.-Fri Feb. 29-Mar. 1. | Recitation 5 | Prepare for HW 5 | ||
| WEEK 8 | ||||
| Tue. Mar. 5 | Homework 5 | Submit on Gradescope by 11:59pm | ||
| Tue. Mar. 5 | Lecture 7A | Binary search trees | CLRS 4th ed., Intro to Part III, 12.1–12.3 (CLRS 3rd ed., Intro to Part III, 12.1–12.3) | |
| Thu. Mar. 7 | Lecture 7B | Red-Black Trees and other balanced trees | CLRS 3rd or 4th ed., 13.1–13.4 | |
| Thu.-Fri. Mar. 7-8 | Recitation 6 | Prepare for HW 6 | ||
| WEEK 9 | ||||
| Tue. Mar. 12 | Homework 6 | Submit on Gradescope by 11:59pm | ||
| Tue. Mar. 12 | Lecture 8A | Augmenting data structures | CLRS 4th ed., 17.1–17.3 (CLRS 3rd ed., 14.1-14.3) | |
| Thu. Mar. 14 | Lecture 8B | Hashing | CLRS 3rd or 4th ed., 11.1–11.4 | |
| Thu.-Fri. Mar. 14-15 | Recitation 7 | Prepare for HW 7 | ||
| WEEK 10 | ||||
| Tue. Mar. 26 | Homework 7 | Submit on Gradescope by 11:59pm; | ||
| Tue. Mar. 26 | Lecture 9A | Catchup and Review | ||
| Thu. Mar 28 | EXAM | Midterm Exam 2 (Lectures 6--9) | ||
| Thu.-Fri. Mar. 28-29 | Recitation (optional; go over exam) | |||
| WEEK 11 | ||||
| Tue. Apr. 2 | Lecture 10A | Graphs, Breadth First Search, Depth First Search | CLRS 4th ed., 20.1–20.3 (CLRS 3rd ed., 22.1-22.3) | |
| Thu. Apr. 4 | Lecture 10B | Cut vertices, Biconnected components | CLRS 4th ed., Problem 20.2, pp. 582–583) (CLRS 3rd ed., Problem 22.2, pp. 621–622) | |
| Thu.-Fri. Apr. 4-5 | Recitation 8 | Prepare for HW 8 | ||
| WEEK 12 | ||||
| Tue. Apr. 9 | Homework 8 | Submit on Gradescope by 11:59pm; | ||
| Tue. Apr. 9 | Lecture 11A | Topological sort, Strongly Connected Components | CLRS 4th ed., 20.4–20.5 (CLRS 3rd ed., 22.4–22.5) | |
| Thu. Apr. 11 | Lecture 11B | Single Source Shortest Paths | CLRS 4th ed., Intro chapter 22, 22.1–22.3 (CLRS 3rd ed., Intro chapter 24, 24.1–24.3) | |
| Thu.-Fri. Apr 11-12 | Recitation 9 | Prepare for HW 9 | ||
| WEEK 13 | ||||
| Tue. Apr. 16 | Homework 9 | Submit on Gradescope by 11:59pm | ||
| Tue. Apr. 16 | Lecture 12A | Minimum Spanning Trees | CLRS 4th ed., 21.1–21.2 (CLRS 3rd ed., 23.1–23.2) | |
| Thur. Apr. 18 | Lecture 12B | TBD (All Pairs Shortest Path? Fibonacci Heaps?) | TBD | |
| Thur-Fri. Apr. 18-19 | Recitation 10 | Prepare for HW 10 | ||
| WEEK 14 | ||||
| Tue. Apr. 23 | Homework 10 | Submit on Gradescope by 11:59pm | ||
| Tue. Apr. 23 | Lecture 13A | TBD (NP-completeness? Reduction? String-matching?) | TBD | |
| Thu. Apr. 25 | Lecture 13B | Final exam review | ||
| Thu.-Fri. Apr. 25-26 | Recitation 11 | Prepare for HW 11 | ||
| WEEK 15 | ||||
| Mon. Apr. 29 | Homework 11 | Submit on Gradescope by 11:59pm | ||
| FINALS WEEK | ||||
| Wed. May 8 | FINAL EXAM | Cumulative Final (Lectures 0–-13) | Exam is held 9:00-11:00AM in Pearson 104 | |