Note: This is the original class schedule, as planned for a fully face-to-face class. With the transition to online teaching, this is no longer accurate but is kept for reference. Please see the current schedule for current information.
The following gives a day-by-day breakdown of topics covered, readings assigned, and assignment handouts/due dates. Each topic includes several required readings that students should read before the topic is discussed in class – always look ahead a few days to see what readings you should be doing. Some topics also have supplemental (non-required) readings that students can look into if they want to delve more deeply into that topic.
The schedule in this class is flexible, and past dates will be updated to reflect what was actually covered. Future dates are always tentative and subject to change.
Topics: Class overview and syllabus review; introduction to the study of algorithms
Reading: Perrin Number Information and Chapter 1
Handout: Syllabus
Topics: Basics of algorithm analysis
Reading: Chapter 2
Topics: Asymptotic notation and summations
Reading: Chapter 3 and Appendix A
Assigned: Assignment 1
Topics: Divide-and-conquer basics
Reading: Sections 4.1 and Karatsuba Multiplication
Topics: Recurrences
Reading: Sections 4.3–4.5 (note: 4.3–4.4 are for review)
Due: Assignment 1
Topics: Divide-and-conquer in computational geometry: closest pair
Reading: Section 33.4
Assigned: Assignment 2
Topics: Randomized algorithms and quicksort basics
Reading: Sections 5.1–5.3 and 7.1–7.2
Topics: Randomized quicksort and selection
Reading: Sections 7.3–7.4 and Chapter 9
Topics: Lower bound for comparison-based sorting
Reading: Section 8.1
Due: Assignment 2
Topics: Revew/Problem solving day
Topics: Exam 1
Topics: Dynamic programming - day 1
Reading: Chapter 15
Assigned: Assignment 3
Topics: Dynamic programming - day 2
Topics: Dynamic programming - day 3
Topics: Greedy algorithms - day 1
Reading: Sections 16.1 – 16.3
Due: Assignment 3
Topics: Greedy algorithms – day 2
Topics: Basic graph algorithms
Reading: Chapter 22
Topics: Minimum spanning tree algorithms
Reading: Chapter 23
Topics: Revew/Problem solving day
Topics: Exam 2
Topics: Single-source shortest path algorithms
Reading: Chapter 24
Topics: All-pairs shortest path algorithms
Reading: Chapter 25
Topics: Maximum flow – day 1
Reading: Sections 26.1 – 26.3
Topics: Maximum flow – day 2
Topics: NP-completeness – day 1
Reading: Chapter 34
Topics: NP-completeness – day 2
Topics: NP-completeness – day 3
Topics: Comping with NP-completness – approximation algorithms
Reading: Sections 35.1 – 35.3
Topics: Last day of class – review
Friday, May 1, 7:00-10:00