Instructor	Huacheng Yu
Lectures	Monday/Wednesday 10:40-12:00pm
TAs	Zhongtian He, Ilya Maier, Pachara Sawettamalya
Location	Lewis Library 120
Office hours	Huacheng: Monday 1:30-3:30pm @ CS310

For course description, grading policy, etc., please see the course infosheet.

Ed

We will use Ed for course discussion. The link is: https://edstem.org/us/courses/95086/discussion. If you are enrolled in the course, you should have access to Ed. Please email the instructor if you cannot access Ed.

Grading

You earn five points of participation for attending each 1-1 coaching sessions. You may earn up to 40 points this way. There will be two in-class Midterms, and a scheduled Final. Suppose you earn p participation points, get m₁, m₂ points from the two Midterms respectively and f points from the Final. Then your grade is p + (1-p/100)(min(m₁,m₂)/6+max(m₁,m₂)/3+f/2).

Homework

Homeworks will be posted below when they become available.

• homework 1
• homework 2
• homework 3: out ~3/4
• homework 4: out ~3/23
• homework 5: out ~4/8

Supplemental reading and related courses

• CLRS: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms 3rd Edition.
• KT: Jon Kleinberg, Éva Tardos. Algorithm Design.
• COS 423: A previous offering by Prof. Robert Tarjan.
• MIT 6.046J: Design and Analysis of Algorithms.
• MIT 6.854: Advanced Algorithms.
• CMU 15-451/651: Algorithms. v1: Fall 2020 v2: Fall 2024 v3: Spring 2015
• UIUC CS598 JGE: Advanced Data Structures.
• NEU CS5800: Algorithms.

Lecture notes and schedule

Below is a tentative schedule.

Lecture	Date	Topic	Notes	Supplemental reading
Graph Algorithms
	1/26	Cancelled
1	1/28	Minimum spanning trees I	Lecture 1	CLRS Chapter 23, KT Chapter 4.5 COS 423 Lecture on "Minimum Spanning Trees"
2	2/2	Minimum spanning trees II	Lecture 2	COS 423 Lecture on "Minimum Spanning Trees Faster" David Karger, Philip Klein, Robert Tarjan. "A randomized linear-time algorithm to find minimum spanning trees".
3	2/4	Shortest paths	Lecture 3	CLRS Chapter 25 MIT 6.046J Lecture 11, NEU CS5800 Lecture 12
4	2/9	Matchings	Lecture 4	CLRS Chapter 26.3, KT Chapter 7.5 COS 423 Lecture on "Graph Matching"
5	2/11	Matchings II	Lecture 5	COS 423 Lecture on "Nonbipartite Matching" CMU 15-451/651 v3 Lecture 11
6	2/16	Strongly connected components	Lecture 6	CLRS Chapter 22.5, KT Chapter 3.5 COS 423 Lecture on "Strong Components and Blocks" CMU 15-451/651 v3 Lecture 9 NEU CS5800 Lecture 11
7	2/18	Max flow	Lecture 7	CLRS Chapter 26.4, KT Chapter 7.4 COS 423 Lecture on "Maximum Flow" NEU CS5800 Lecture 13
	2/23	Midterm #1
	2/25	No lecture
8	3/2	TBD
Data Structures
9	3/4	Quadtree and KD tree
	3/9	Spring break
	3/11	Spring break
10	3/16	Range trees
11	3/18	Van Emde Boas trees
12	3/23	Disjoint set union
13	3/25	Fibonacci heap
14	3/30	Splay trees
15	4/1	Suffix trees and suffix arrays
	4/6	Midterm #2
Other Algorithmic Topics
16	4/8	String matching algorithms
17	4/13	Integer sorting algorithms
18	4/15	Approximation algorithms
19	4/20	External memory algorithms
20	4/22	Cell-probe lower bounds