Courses

Design and Analysis of Algorithms II

A second course in algorithm design and analysis, picking up where COMP 3804 leaves off. We work through advanced recurrence relations, algebraic complexity, advanced graph algorithms, amortized analysis, algorithms for NP-complete problems and randomized algorithms, drawing examples from randomized, graph and geometric algorithms, data structures and approximation algorithms. The emphasis throughout is on proving correctness and analysing complexity rigorously, and on writing a complete algorithmic argument in precise mathematical notation.

Meets

Tuesdays & Thursdays, 14:35–15:55

Term

10 September – 10 December 2026
No classes 26–30 October

Prerequisite

COMP 3804 or MATH 3804

Materials

No textbook to buy — readings and notes are posted on Brightspace

Undergraduate section COMP 4804, cross-listed as graduate section COMP 5703. The full outline, readings, notes, assignments and office hours are on Brightspace.

Fields Course: Graphs and Algorithms

This course provides a graduate-level exploration of graph algorithms and structural graph theory. The emphasis is on algorithm design, mathematical analysis, and theoretical foundations of problems on graphs. Topics include graph traversal, spanning trees, network flows, matchings, graph coloring, planar graphs, as well as advanced topics such as geometric graphs, spectral graph theory, random graphs, and tree-decompositions.

The course blends proofs of correctness and complexity with structural insights drawn from modern graph theory. Prerequisites include discrete mathematics and a basic background in algorithms. No advanced programming experience is required; basic familiarity with Python and the networkx library is helpful.

Co-taught with Bobby Miraftab. The lecture schedule, readings and paper options are on the course page.

Level

Graduate

Lectures

15 September – 3 December 2026

Instructors

Prosenjit Bose and Bobby Miraftab