CS 5800 (Algorithms) Schedule

CS 5800: Algorithms
Schedule for Spring 2026

The semester has 66 non-holiday weekdays. I have partitioned those days into four sections, corresponding to the four exams of this course, as follows.

January 7 to 29 (16 weekdays, excluding the 19th)
Exam 1 is on February 5
January 30 to February 24 (17 weekdays, excluding the 16th)
Exam 2 is on March 10
February 25 to March 25 (16 weekdays, excluding spring break)
Exam 3 is on March 31
March 26 to April 17 (17 weekdays)
Exam 4 is on April 21

I recommend trying to maintain a pace such that all primary studying for each exam is done within the corresponding time frame listed above. For example, most studying for exam 1 should be done by approximately January 29. In the week that follows, it makes sense to keep reviewing, but your schedule should allow some time to begin working on new topics related to exam 2.

Before the semester begins:

Review discrete math and data structures. (Resources: section 1)

Week 1
January 7-9
- Insertion sort. Big-O notation. (Resources: section 2)
Week 2
January 12-16
- Merge sort. Analyzing recurrences: (i) with trees; (ii) by induction; (iii) via master method (Resources: section 3.1 & 3.2)
Week 3
January 20-23. (holiday on 19, add/drop on 20)
- Heap building and heap sort (Resources: section 4.3)
- The sorting lower bound (Resources: section 4.4)
- Counting sort and Radix sort. (Resources: section 4.5)
Week 4
January 26-30
- Deterministic Selection. (Resources: section 6.3)
- RandSelect (Resources: section 8.2, without the longer derivation)
- Quicksort (Resources: section 8.1.a) -- You don't need to focus on the details of how to partition in-place.
- January 29th is Day 16 of the course. You should be done with primary studying for exam 1 by now. Keep reviewing but starting looking into topics related to exam 2 as well.
Week 5
February 2-6
- Hashing. (Resources: section 5)
- Binary search tree (BST) intro. (Resources: section 9.1)
- Expected time to build a random BST, and expected depth of a BST. (Resources: section 9.2)
- Exam 1, Thursday, February 5, covering weeks 1,2,3,4.
Week 6
February 9-13
- Red-black trees (Resources: section 9.3) -- The objective here is not so much to memorize the various cases, it's to understand why these trees are balanced, and that it's possible to keep them balanced.
- Augmenting BSTs (Resources: section 10)
Week 7
February 17-20 (holiday on 16)
- Continue: Augmenting BSTs (Resources: section 10)
- Tentative special topic: Linear programming; Megiddo's algorithm. This is not usually part of the course. Material will be posted soon.
Week 8
February 23-27
- Keep focusing on exam 2 topics (weeks 5,6,7) until the 24th (Day 33 of the course). Start looking at exam 3 topics on the 25th.
- Amortized analysis (Resources: section 11) -- This is the first topic for exam 3.
Spring break
Week 9
March 9-13
- Exam 2, Tuesday, March 10, covering weeks 5,6,7.
- Continue: Amortized analysis (Resources: section 11)
- Dynamic programming (Resources: section 12)
Week 10
March 16-20
- Continue dynamic programming (Resources: section 12)
Week 11
March 23-27
- Keep focusing on exam 3 topics (weeks 8.9.10) until the 25th (Day 49 of the course). Start looking at exam 4 topics on the 26th.
- Graphs: Intro, BFS & DFS. (Resources: 13.1, 13.2) (First topic for exam 4)
- Topological sort (Resources: 13.3)
Week 12
March 30 - April 3
- Exam 3, Tuesday, March 31, covering weeks 8,9,10. (All about amortization and dynamic programming)
- Minimum spanning trees (MST). (Resources: section 14)
Week 13
April 6-10
- Single-source shortest paths (SSSP) (Resources: section 15)
Week 14
April 13-17
- Tentative special topic: All-pairs shortest paths (APSP) - Johnson's algorithm. This is not usually part of the course. Material will be posted soon.
Exam Week
- Exam 4, Tuesday, April 21 covering weeks 11,12,13,14. (All about graphs)
Topics from the Resources page that we won't cover
- Indicator random variables (Resources: section 7)
- Strongly connected components. (SCC; Resources: 13)
- P vs NP (Resources: section 16)
  - I recommend taking a look at P vs NP at some point. Nobody should get a CS degree without knowing some of the basic concepts. Ideally it will be covered in greater detail in another course (on theory of computation).
Topics that you might find in other intro to Algorithms courses, that we probably won't cover.
Not to imply that this course is easier; we emphasize some things that others don't.
- Network flow
- Approximation algorithms
- String matching
- ...