Advanced Data Structures

CS 598 JGE, Spring 2025

---

Announcements

Apr 17

Please fill out the project team registration form by Monday, April 21. Exactly one member of each team should submit the form. Please submit even if you aren't sure about all the details of your project; you can revise your submission later if necessary. (Also, please remember that the presentations are progress reports, not summaries of the final projects.) I plan to announce a tentative project presentation schedule on Tuesday, April 22. The first presentation will be on the following Tuesday, April 29.

Apr 3

All proposal submissions 🔐 are available. (I will continue to update this document as proposals are submitted or revised.)

Mar 23

• All paper-chase submissions 🔐 are available.
  (The lock emoji 🔐 indicates that the linked file is in a secure directory; login info has been emailed to all students.)
• Project proposals are due next Monday, March 31. This is a hard deadline. This is the second stage of the semester project.

Feb 10

The paper chase assignment is due Monday, March 4. This is the first stage of the semester project. (I tried to make the list of suggested papers as short as possible, honest!)

Feb 6

Homework 0 solutions 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.

---