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
• homework 4
• 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.
• UMD CMSC420: Advanced Data Structures.
• Harvard CS224: Advanced 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	Max flow II	Lecture 8	CLRS Chapter 26.5, KT Chapter 7.4 COS 423 Lecture on "Maximum Flow" NEU CS5800 Lecture 13
Data Structures
9	3/4	K-d tree	Lecture 9	UMD CMSC420 Lecture 10, 11, 12
	3/9	Spring break
	3/11	Spring break
10	3/16	Van Emde Boas tree and x-fast trie	Lecture 10	CLRS Chapter 20 UIUC CS598 JGE "van Emde Boas trees and x-fast tries" Harvard CS224 Lecture 1
11	3/18	y-fast tries and fusion trees	Lecture 11	UIUC CS598 JGE "y-fast tries and fusion trees", "Fusion tree details" Harvard CS224 Lecture 2
12	3/23	Disjoint set union	Lecture 12	CLRS Chapter 21 UMD CMSC420 Lecture 04 CMU 15-451/651 v2 Lecture 8
13	3/25	Fibonacci heap	Lecture 13	CLRS Chapter 19 MIT 6.854 Lecture 1,2 CMU 15-451/651 v3 Lecture 14 Harvard CS224 Lecture 6,7
14	3/30	Splay trees	Lecture 14	Harvard CS224 Lecture 7,8 MIT 6.854 Lecture 4 CMU 15-451/651 v1 Lecture 6 UIUC CS598 JGE Lecture on "splay trees" UMD CMSC420 Lecture 13
15	4/1	Suffix trees and suffix arrays	Lecture 15	CMU 15-451/651 v1 Lecture 23,24 CMU 15-451/651 v3 Lecture 25
	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