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: out ~2/2
• homework 2: out ~2/16
• homework 3: out ~3/4
• homework 4: out ~3/23
• homework 5: out ~4/8

Lecture notes and schedule

Below is a tentative schedule.

Lecture #	Date	Topic	Lecture notes and additional reading
Graph Algorithms
1	1/26	Cancelled
2	1/28	Minimum spanning trees I
3	2/2	Minimum spanning trees II
4	2/4	Shortest paths
5	2/9	Shortest paths II
6	2/11	Matchings
7	2/16	Matchings II
8	2/18	Strongly connected components
9	2/23	Midterm #1
10	2/25	No lecture
11	3/2	Max flow
Data Structures
12	3/4	Quadtree and KD tree
	3/9	Spring break
	3/11	Spring break
13	3/16	Range trees
14	3/18	Van Emde Boas trees
15	3/23	Disjoint set union
16	3/25	Fibonacci heap
17	3/30	Splay trees
18	4/1	Suffix trees and suffix arrays
19	4/6	Midterm #2
Other Algorithmic Topics
20	4/8	String matching algorithms
21	4/13	Integer sorting algorithms
22	4/15	Approximation algorithms
23	4/20	External memory algorithms
24	4/22	Cell-probe lower bounds