Advanced Algorithms

About This Course  

Algorithm design and analysis is a fundamental and important part of any discipline of computer science including data science.This course assumes that every student has passed an undergraduate course in this area, or has an equivalent background. Compared to the undergraduate algorithms course, the goal of the course is to study some topics more deeply and to learn more advanced algorithms.

Learning Objectives  

The topics we plan to cover include network flow, linear programming and duality theory, hard problems (NP and PSpace), Tree decomposition and tree width, Approximation algorithms, and Randomized algorithms.

Announcements

(No information at the moment, a place holder for future announcements.)

Reading Material

Required Reading

• “Algorithm Design”, Jon Kleinberg and Éva Tardos (Cornell University)

Recommended Reading

• “Introduction to Algorithms”, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein (MIT)

Schedule

	Date	Lecture	Readings
1	18 Aban	Introduction
2	20 Aban	Stable Matching Problem	1.1
3	25 Aban	Interval scheduling and the “greedy stays ahead” analysis technique	4.1
4	27 Aban	Minimize lateness and the “exchange argument” analysis technique	4.2
5	2 Azar	Minimum spanning tree algorithms	4.5, 4.6
6	4 Azar	Dynamic programming: Sequence alignment	6.6
7	9 Azar	Dynamic programming: Weighted interval scheduling, Bellman-Ford	6.1, 6.8
8	11 Azar	Divide-and-conquer: Closest pair of points	5.4
9	16 Azar	Fast multiplication of integers and matrices	5.5
10	18 Azar	Fast Fourier Transform (FFT)	5.6
11	23 Azar	Network Flow: The Ford-Fulkerson Algorithm	7.1
12	25 Azar	Max-Flow Min-Cut, Bipartite Matching	7.2, 7.5
13	30 Azar	Image Segmentation, Project Selection	7.10, 7.11
14	2 Dey	Extensions to network flow	7.7, 7.9
15	7 Dey	Polynomial-time max-flow algorithms	7.3
16	9 Dey	Polynomial-time Reductions	8.1, 8.2
17	14 Dey	Formal Definition of the Class NP	8.3
18	16 Dey	Three-Dimensional Matching	8.6
19	21 Dey	Colorability and Hamiltonian Cycle	8.5, 8.7
20	23 Dey	NP-complete numerical problems	8.8
21	25 Dey	Other complexity classes. (L, PSPACE)	8.10, 8.11
22	29 Dey	Load balancing greedy approximation	11.1
23	30 Dey	k-center selection approximation	11.2
24	2 Bahman	Weighted set cover approximation	11.3
25	5 Bahman	Polynomial-time approximation scheme (PTAS)	11.8

Assessment and Feedback 

(will links to a separate page)

Marking Criteria 

• 30% Homework assignments
• 10% Programming Assignment
• 20% Midterm
• 40% Final