MPCS 55005 Advanced Algorithms (Spring 2024)

Section 1
Instructor(s) Brady, Geraldine (gb52)
Location Ryerson 276
Meeting Times Tuesday 5:30pm - 8:30pm
Fulfills Core Theory Elective

Syllabus

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
  • Methods of dealing with intractability: approximation algorithms and local search
  • Linear programming: duality, game theory, integer linear programming, rounding
  • Randomization and derandomization
  • Streaming algorithms: Morris counting, heavy-hitters, frequency estimation
  • Randomized data structures: Bloom filters, skip lists, multiplicative weights
  • Computational geometry: convex hulls, sweep-line algorithms, Delauney triangulation
  • Advanced data structures: Red-black trees, B-trees, segment trees, R-trees
  • String algorithms: Rabin-Karp algorithm, Knuth-Morris-Pratt algorithm, Boyer-Moore algorithm; tries data structure

with applications in computing, data science, and engineering.

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.

Course Prerequisites

B+ or better in MPCS 55001 Algorithms *or consent of instructor*

Other Prerequisites

This course requires competency in Unix, Linux, and GitHub. 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/.

Overlapping Classes

This class is scheduled at a time that conflicts with these other classes:

  • MPCS 56520-1 -- Advanced Security Topics
  • MPCS 55001-1 -- Algorithms
  • MPCS 53001-1 -- Databases
  • MPCS 51235-1 -- Advanced User Interface and User Experience Design

Eligible Programs

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