CS 401: Computer Algorithms I, Autumn 2026

Computer Algorithms I

Welcome to Computer Algorithms 1! You can find the tentative course schedule below. As the course progresses, each day's lecture slides will be attached, as well as recommended and relevant textbook readings.

But what is this course about?

This course is about algorithms: efficient, procedural, deterministic (in this course at least) ways of solving computational problems. Broadly, we're developing your ability to efficiently solve real-world computational problems. We view this as a three-step process:

Take a real-world problem and model it as a computational one, with appropriate data structures for the input and desired output.
Develop a procedure for performing it efficiently.
Verify that this procedure is correct and efficient.

A recurring undercurrent of this course is pushback on the idea that this process has one "correct" outcome or algorithm. Steps 1 and 3 especially are particularly design-oriented processes, and thus will always require human choices. Take Step 1, for example. Note that a "model" is, by definition, a simplification of a real thing. As an algorithm designer, you'll have to make human choices about what aspects of the real world to simplify, what the simplified representation should be, and how that impacts the algorithm you design. Or, in Step 3, we'll learn to verify that the procedure we develop is correct and efficient, but we have to decide what counts as "correct," what counts as "efficient," and whether those are even the right goals to be aiming for.

For this reason, you should not view this course as answering "how do I quickly solve this problem?" After all, AI can already do that, and before AI, search engines could already do it too. Instead, the goal of this course is for you to develop comfort thinking about and communicating about algorithms. You'll learn how to design, analyze, verify, and communicate about algorithms. You'll learn what makes them tick, where their limitations are, and what the human design choices mean for the algorithm's effectiveness. The goal is that, when it comes time to work with other people (and potentially AI) to solve the real-world problems that you're interested in, you'll have a proper seat at the table.

Unit 1

Algorithm Analysis

Homework

Week 1

#01

Tue Aug 25

Introducing: Algorithms

#02

Thu Aug 27

Stable Matching

[KT Chapter 1]

Homework 0

Due Fri Sep 4, 11:59pm

Week 2

#03

Tue Sep 1

Algorithmic Complexity and Ethics

#04

Thu Sep 3

Algorithmic Ethics 2

Homework 1

Due Fri Sep 11, 11:59pm

Unit 2

Divide and Conquer

Homework

Week 3

#05

Tue Sep 8

Recursion and Binary Search

#06

Thu Sep 10

Mergesort

—

Week 4

#07

Tue Sep 15

Divide and Conquer Runtimes

#08

Thu Sep 17

More Interesting Divide and Conquer Problems

Homework 2

Due Fri Sep 25, 11:59pm

Unit 3

Graph Algorithms

Homework

Week 5

#09

Tue Sep 22

Graph Traversals and Decompositions

#10

Thu Sep 24

BFS and Dijkstra's Algorithm

—

Week 6

#11

Tue Sep 29

Introduction to Reductions

#12

Thu Oct 1

Graph Layering

Homework 3

Due Fri Oct 9, 11:59pm

Week 7

#13

Tue Oct 6

Midterm review

Thu Oct 8

Midterm Exam — in class

—

Unit 4

Greedy Algorithms

Homework

Week 8

#14

Tue Oct 13

Interval Scheduling and Greedy Proofs

#15

Thu Oct 15

Minimum Spanning Trees

—

Week 9

#16

Tue Oct 20

Topic TBD

#17

Thu Oct 22

Heuristic Selection and Analysis

Homework 4

Due Fri Oct 30, 11:59pm

Unit 5

Dynamic Programming

Homework

Week 10

#18

Tue Oct 27

Dynamic Programming I

#19

Thu Oct 29

Dynamic Programming II

—

Week 11

#20

Tue Nov 3

Bellman-Ford

#21

Thu Nov 5

Knapsack and TSP

Homework 5

Due Fri Nov 13, 11:59pm

Unit 6

Intractable Problems

Homework

Week 12

#22

Tue Nov 10

Introduction to Problem Hardness

#23

Thu Nov 12

Reductions

—

Week 13

#24

Tue Nov 17

More Reductions

#25

Thu Nov 19

NP-Completeness and P vs. NP

Homework 6

Due Fri Dec 4, 11:59pm

Week 14

#26

Tue Nov 24

Coping with NP-hard Problems

Thu Nov 26

No class — Thanksgiving

—

Week 15

#27

Tue Dec 1

Final Review

#28

Thu Dec 3

Project Presentations

—

Exam week

Dec 7 – 11

Final Exam

Time and room to be announced

Cumulative.

No homework assigned.

Lecture topics and readings are posted here before each lecture.

Updated 19 Aug