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.


(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)


118 AbanIntroduction
220 AbanStable Matching Problem1.1
325 AbanInterval scheduling and the “greedy stays ahead” analysis technique4.1
427 AbanMinimize lateness and the “exchange argument” analysis technique4.2
52 AzarMinimum spanning tree algorithms4.5, 4.6
64 AzarDynamic programming: Sequence alignment6.6
79 AzarDynamic programming: Weighted interval scheduling, Bellman-Ford6.1, 6.8
811 AzarDivide-and-conquer: Closest pair of points5.4
916 AzarFast multiplication of integers and matrices5.5
1018 AzarFast Fourier Transform (FFT)5.6
1123 Azar Network Flow: The Ford-Fulkerson Algorithm7.1
1225 AzarMax-Flow Min-Cut, Bipartite Matching7.2, 7.5
1330 AzarImage Segmentation, Project Selection7.10, 7.11
142 DeyExtensions to network flow7.7, 7.9
157 DeyPolynomial-time max-flow algorithms7.3
169 DeyPolynomial-time Reductions 8.1, 8.2
1714 DeyFormal Definition of the Class NP8.3
1816 DeyThree-Dimensional Matching8.6
1921 DeyColorability and Hamiltonian Cycle 8.5, 8.7
2023 DeyNP-complete numerical problems8.8
2125 DeyOther complexity classes. (L, PSPACE)8.10, 8.11
2229 DeyLoad balancing greedy approximation11.1
2330 Deyk-center selection approximation11.2
242 BahmanWeighted set cover approximation11.3
255 BahmanPolynomial-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