YRWVKX
)
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.
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.
YRWVKX
.
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.