CS 598 TMC, Fall 2023

Advanced Data Structures


Timothy Chan (tmc "at" illinois.edu, office hours: Thu 3:30-4:30, Siebel 3230)

TA: Yuancheng Yu (yyu51 "at" illinois.edu, office hr: Wed 6:00pm-7:00pm on zoom)

Meeting Time

Wed & Fri 11:00am-12:15pm, Loomis Lab 136

Course Overview

This is a CS theory/algorithms course, covering selected topics in data structures, which go beyond what are typically taught in 2nd and 3rd-year undergraduate classes. Potential topics include: balanced search trees, priority queues (e.g., Fibonacci heaps), amortized analysis, the union-find problem, hashing, geometric data structures (e.g., range searching), approximate nearest neighbor search (e.g., locality-sensitive hashing), bit-packing techniques (e.g., fusion trees and succinct data structures), persistent data structures, dynamic graph algorithms (e.g., dynamic connectivity and shortest paths), distance oracles, strings and text indexing (e.g., suffix trees), I/O-efficient data structures, and (conditional) lower bounds.

Prerequisites: Solid background in algorithm design and analysis, at the level of CS 374. (CS 473 is not required, though some previous exposure to randomized algorithms might be helpful.) Undergraduate students who did well in 374 or 473 are welcomed, and may request for an UG petition.

Course Work

(Homeworks, presentations, and projects may be done in groups of at most 3.)

See guidelines for presentation and project.

Tentative Outline


(There is no textbook; I'll provide links to relevant references below, and also scribbles from class.)

Other Resources