CS 598 JGE: Advanced Data Structures (Spring 2011)

   About    Schedule    Projects   

Submitted Proposals

Carl Evans

(Relaxed) concurrent priority queues on multicore machines

Dan Larkin

Experimental comparison of efficient priority queues

HaoHui Mai

Alias analysis in subquadratic time and space

Joe Di Febo

Experimental evaluation of hashing schemes

Justin Kopinsky

Kinetic shortest path trees

Kyle Fox

Dynamic-finger and unified bounds for greedy binary search trees

Phil Miller

Efficient integer sorting on GPUs

Rohan Sharma

Fully persistent word-RAM predecessor search

Smit Shah

Succinct data structures for one- and two-dimensional minimum range queries

Will Setchell

Experimental analysis of competitive dynamic binary search trees for data compression

Final Projects

The bulk of the grade in this class is based on the final project. Projects may be submitted by teams of up to three students. Students are strongly encouraged to collaborate outside their teams, with anyone in or out of class (with proper credit, of course). Each team will submit a written document (by default, about 10-15 pages) and give a short presentation (by default, about 30 minutes). Projects can take any of the following forms. Students are strongly encouraged to work on projects motivated by their primary research/development interests. In particular, project topics need not be limited to the specific topics covered in class, as long as they focus on data structures. Especially for theoretical projects, you should work on problems whose solution you want to know but don't.

One month before the end of the semester, each student will submit a project proposal. Project proposals are due Friday, April 8. This is a hard deadline. Proposals should be 2-3 pages in length, and should include a crisp self-contained statement of the proposed topic, a brief survey of known results, a potential plan of attack, and one or two half-baked ideas that probably won't work but what the heck you might get lucky. After everything is submitted, I will post all submitted proposals to this web page as inspiration for final projects; however, the final projects themselves need not focus on any of the proposed topics.

The ideal result of the project is something that can be polished into a publishable paper. This ideal is meant to be an attractive goal, not an absolute requirement—not all research is successful! If you do not find a complete solution, your writeup and presentation should describe partial results (for example, incremental improvements for some interesting special cases), promising approaches for ongoing work, remaining questions where you're still stumped, and most importantly, ideas that initially looked promising but weren't (and why). I prefer creative failure to straightforward success. No, really.

Hey, wait! How do we find good problems?

Excellent question! Here are a few hopefully useful suggestions. This list is nowhere near exhaustive, nor will every suggestion work equally well (or at all) for everybody. If you have other ideas for finding good research problems, I'd love to hear them!