Advanced Data Structures

CS 598 JGE, Spring 2025

Instructor
Jeff Erickson (jeffe@illinois.edu)
Lectures
TTh 3:30–4:45, 3038 Campus Instructional facility (floor plans)
Office Hrs
Friday 2:00-3:00 (tentative), open area next to 3237 Siebel
Links


Announcements

Feb 6
Homework 0 zolutions are available.

I will be traveling during finals week, so I have moved the project presentations to the last week and a half of classes, and moved the project proposal deadline back one week (to March 31). The paper chase deadline is unchanged.

Jan 24
A LaTeX solution template is available. (You are not required to use this template, or Jeff's latex packages that it depends on.)
Jan 20
Homework 0 is due next Tuesday at 9pm. (I'll post the LeTeX template soon.)
Jan 11
Hello and welcome! Please forgive the dust and construction noises. First some logistics:
  • The class is completely full. There are 40 chairs in the room and 40 registered students. Moving to a larger room is not a realistic possibility.

    Unfortunately, I do not expect that everyone who wants to take the class will eventually get in. So far registration has been limited to computer science graduate students. In principle, registration will open to all students by the first week of the semester; in practice, however, registration slots will open only if currently registered students drop. Registration will be on a first-come-first-served basis, and I cannot promise that late registration will be possible.

    Students who are still interested in taking the class are welcome to attend the lectures if and only if seats are available. All lectures will be recorded.

  • We are using Gradescope to submit assignments. You can enroll yourself using the entry code YRWVKX.
  • We are using Ed Discussion as an online discussion forum. You can enroll yourself using your university login credentials; no entry code is necessary.
  • There will be a Homework Zero, due on Monday, January 27. This is primarily meant as a self-assessment tool to make sure you have the necessary background/experience/maturity to take this class, but it will count toward your course grade. Stay tuned for details.

About this class

This course will survey important developments in data structures that go beyond the typical undergraduate computer science curriculum. 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. The precise topics will depend on the interests and background of the course participants.

Prerequisites: Students in all areas of computer science and related disciplines are welcome, including algorithmically mature undergraduates. Undergraduates interested in taking this course should petition for a registration override as soon as possible. A theoretically-oriented undergraduate algorithms course at the level of CS 473 is a prerequisite; however, specific background material will be introduced as needed.

This course does not satisfy the "Theory and Algorithms" breadth requirement for MCS and MS students, but it can be used to satisfy the Advanced Coursework requirement.