Go back to Main Class Page

CS 160 Class Schedule

We assume that the first time a topic such as "N.1 Introduction" is listed, the corresponding Chapter N introduction is also included. The last two sections of each Goodrich & Tamassia chapter (ie. Exercises and Chapter Notes) are are also not explicitly listed, but should be included by the student.

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.

Schedule/Syllabus

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