MPCS 55005 Advanced Algorithms (Spring 2026)

Advanced Algorithms is a course on the design and analysis of efficient algorithms on a series of challenging topics. This course presents many interesting and relevant algorithms and data structures and gives students the tools to recognize and rigorously solve algorithmic problems often encountered in industry and engineering. 

Topics include:

• Intractability. Theory of NP Completeness. Problems and Reductions: Hamilton Cycle to Traveling Salesman, Vertex Cover to Independent Set to Clique, SAT to 3SAT, 3SAT to Vertex Cover, Circuit-SAT to SAT.
• Approximation algorithms. Metric k-center problem, Metric traveling salesman problem. Set Cover problem.
• Online and streaming algorithms. Online counting algorithms. Potential functions. Heavy-hitters algorithms. Sketching algorithms. Multiplicative weights algorithm.
• Advanced data structures. Skip lists, Segment trees, Tries, Advanced hashing.
• String algorithms. KMP algorithm. Rabin’s rolling hash fingerprinting algorithm. Aho-Corasick algorithm.
• Advanced linear programming. LP duality. Integer linear programming and rounding.
• Advanced dynamic programming. Knuth optimization and divide-and-conquer optimization.
• Computational geometry. Convex hull algorithms. Line-segment intersection algorithm. Voronoi Diagrams and Delaunay Triangulations.
• Optimization.

Engaging weekly homework assignments involve designing new algorithms in pseudocode and solving algorithmic programming problems in python. Course goal is to prepare students with skills necessary to tackle algorithmic problems they are likely to encounter in industry and engineering.

Must have completed MPCS 55001 Algorithms, CMSC 27200, a pass on the Algorithms placement exam, or instructor consent.

This class can count as a Core Theory class for students with a waiver for Algorithms based on CMSC coursework or passing the Algorithms placement exam. This class can also count as a 6th Core class for 12-course students.

This course requires competency in Unix and Linux. If you attended the MPCS Unix Bootcamp you covered the required material. If you did not, please review the UChicago CS Student Resource Guide here: https://uchicago-cs.github.io/student-resource-guide/.

Course request information for non-MPCS students: https://masters.cs.uchicago.edu/student-resources/non-mpcs-student-course-requests/

This class is scheduled at a time that does not conflict with any other classes this quarter.

MS in Computational Analysis in Public Policy (Year 2) MS in Molecular Engineering MA in Computational Social Science (Year 2) Bx/MS in Computer Science (Option 1: Research-Oriented) Bx/MS in Computer Science (Option 2: Professionally-oriented - CS Majors) Bx/MS in Computer Science (Option 3: Profesionally-oriented - Non-CS Majors) Masters Program in Computer Science