Go back to Main Class Page

CS 160 Algorithms

Lecture And Reading Schedule

All times on this page are Eastern Time.

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)