Note: This schedule is being updated for the transition to online teaching, and so is a little uncertain at the moment. For reference and list of topics in the originally-planned course, see the original schedule.
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
In the online class structure that follows, topics are organized by week rather than by lecture-day. Each week corresponds to a module in Canvas, and the module (with quiz) must be completed by the end of the week.
Due: Assignment 3 is still due on Monday, March 16. Submit electronically in Canvas!
Classes temporarily suspended this week as we move to online teaching.
Topics: Final part of Greedy algorithms and basic graph algorithms
Reading: Sections 16.1–16.3 (from earlier) and Chapter 22
Assigned: Assignment 4
Topics: Minimum spanning tree algorithms and Single-Source Shortest Path algorithms
Reading: Chapters 23 and Sections 24.1–24.3
Due Wednesday, April 8: Assignment 4 – due before 5:30pm, when we will discuss problems in the review session
Reading: Sections 25.1–25.2
Monday Topics: All-pairs shortest path algorithms
Wednesday Topics: Review session for exam
Monday: Mid-term Exam 2 (more information in Canvas)
Wednesday: Start NP-completeness
Reading: Chapter 34
Assigned: Assignment 5
Topics: NP-completeness
Due: Assignment 5 – due Wednesday, April 29 at 5:30pm
Reading: Sections 35.1 – 35.3
Monday: Coping with NP-completness – approximation algorithms
Wednesday: Final exam review
Friday, May 1, 7:00-10:00