CS 598 JGE: Advanced Data Structures (Spring 2011)
Jeff Erickson
TuTh 12:30–1:45, 203 Transportation
Announcements
 Thu May 12
 Project presentations will be held in Siebel 4407 at the following times:
 Thursday, May 12, 13ish
 Friday, May 13, 1012ish
Each project group should plan for a 20minute presentation, but there is enough slack for 30 minutes if necessary.
 Mon Apr 25
 This Thursday, April 28, I'll ask for working titles and group members for the final projects, along with everyone's free times during finals week (May 913), so that we can schedule the project presentations. Also, at the end of Thursday's class, I'll distribute ICES forms.
 Mon Apr 11
 Oneline summaries of the submitted project proposals are now available. I will describe the proposals in detail in class tomorrow. At least one student has asked me not to post their proposal on the web site; to respect this request, I will not post any proposals until next week. If you do not want me to post your proposal, please let me know by April 15. Alternately, if you send me a revision of your proposal this week, I will post that instead.
 Mon Mar 28
 Project proposals are due Friday, April 8. This is a hard deadline! The project reports will be due Friday, May 13 (the day our final exam would be held if we had one). If you haven't already submitted Homework 1, please do that soon, so you don't have to work on homework and your project at the same time.
 Tue Mar 2

LaTeX source for Homework 1 is available.
 Tue Feb 22
 A few people have asked for lecture notes; unfortunately, I just don't have time to write up lecture notes this semester. Erik Demaine and his students have written notes for almost all the topics I've covered so far, for a similar class at MIT.
 Tue Feb 15
 Homework 1 is due Thursday, March 3. Ish.
 Wed Jan 19
 Class is canceled next Tuesday, January 23; Jeff will be at SODA.
 Mon Jan 17
 I incorrectly listed the class time as 11:00–12:15 on the posters advertising the class. The class actually meets 12:30–1:45. Sorry about the screwup. Enjoy an early lunch tomorrow!
About this class
This course will survey important developments in data structures that have not (yet) worked their way into the standard computer science curriculum. The precise topics will depend on the interests and background of the course participants; see the current schedule for details. Potential topics include include selfadjusting binary search trees, dynamic trees and graphs, persistent data structures, geometric data structures, kinetic data structures, I/Oefficient and cacheoblivious data structures, hash tables and Bloom filters, data structures that beat informationtheoretic lower bounds, and applications of these data structures in computational geometry, combinatorial optimization, systems and networking, databases, and other areas of computer science.
Students in all areas of computer science and related disciplines are welcome, including algorithmically mature undergraduates. CS 573 is recommended as a prerequisite, but not required; specific background material will be introduced as needed.