CS 401 / MCS 401 - Computer Algorithms I
University of Illinois - Chicago
Fall 2025

This course will cover the important principles behind the design and analysis of computer algorithms. We will study techniques such as divide-and-conquer, dynamic programming, and greedy methods, as well as algorithms for sorting, searching, graph computations, and pattern matching. We will also discuss the theory of NP-completeness.

Basic Information

Syllabus: pdf
Time and Location: M-W-F 2:00–2:50pm, 180G Thomas Beckham Hall (TBH)
Instructor: Lev Reyzin, SEO 417
Instructor's Office Hours: Mondays 9-9:50 am, Tuesdays 8-8:50am (online)
TA/Grader: Belal Mutabagani, MSLC
TA/Grader Office Hours: Wednesdays 4-6pm
Textbook: J. Kleinberg and É. Tardos, Algorithm Design, 1st edition
Piazza site: please sign up via this link

Exam Dates

midterm exam 1: TBD
midterm exam 2: TBD
final exam: 1:00am-3:00pm on Wednesday 12/10/25

Problem Sets

problem set 1, due 9/17/25

Lectures and Readings

Note: lectures will have material not covered in the readings.

Lecture 1 (8/25/25)
covered material: intro to the course, overview of covered material, introduction to stable marriage problem
reading: preface

Lecture 2 (8/27/25)
covered material: the Gale-Shapley stable marriage algorithm
reading: chapter 1.1
optional reading: chapter 1.2

Lecture 3 (8/29/25)
covered material: properties of Gale-Shapely, implementing Gale-Shapley
reading: chapter 2.3
optional reading: chapter 2.4

Lecture 4 (9/3/25)
covered material: measuring algorithm complexity, efficient algorithms, asymptotic analysis
reading: chapters 2.1 and 2.2

Lecture 5 (9/5/25)
covered material: priority queues, implementation with heaps
reading: chapter 2.5

Lecture 6 (9/8/25)
covered material: graph algorithms, graph connectivity, bredth-first search (BFS), depth-frst search (DFS)
reading: chapter 3

Lecture 7 (9/10/25)
covered material: introduction to greedy algorithms, interval scheduling, "greedy stays ahead" argument
reading: chapter 4.1

Lecture 8 (9/12/25)
covered material: scheduling to minimize maximum lateness, an exchange argument
reading: chapter 4.2