Advanced Data Structures

Instructor:Jeff Erickson (jeffe@cs.uiuc.edu)Wed 3:30-5:00 at Bar Guiliani (formerly Green Street Coffee House)TentativeOffice Hours:Course Web Page:http://www.cs.uiuc.edu/~jeffe/teaching/573/Course Blog/Wiki: To be announced. Maybe.

Prerequisites:- This is an advanced graduate-level class, aimed primarily (but not exclusively!) at students interested in algorithms research. Students are expected to have a solid grounding in basic algorithm design and analysis techniques. A
minimalprerequisite is an introductory graduate-level algorithms course like CS 473G.Mathematically and/or algorithmically mature undergraduates are welcome.

Reading:- There is no required textbook for this class. (Sadly, there isn't even a good candidate.) Most of the lecture material will be taken from recent preprints, conference papers, and journal papers. I will provide pointers to electronic copies of these papers here whenever possible.

Coursework:

Written homework assignments.Teams of up to three students can submit common solutions. Students are encouraged to use any written or living resources at their disposal (with proper credit, of course). These will generally be fairly light, although I will throw in the occasional open problem.

Scribe notes.Each registered student is responsible for writing polished, illustrated notes for at least one lecture. Scribe notes must be written in LaTeX using Jeff's scribe package. (A sample source file is available.) Scribe notes are due 72 hours after the scribed lecture—Friday for Tuesday's lectures, Monday for Thursday's lectures—so that they can be made available quickly to the rest of the class. Notes will be posteduneditedto the course web page/blog/wiki. I'll provide each scribe with my written lecture notes and any source papers as a starting point.

A semester project.I'll give more details in class, but here's the basic structure:The

- Before the beginning of spring break, submit an interesting, non-trivial, and preferably open problem related to data structures. Each student must submit their own problem. Submitted problems need
notbe limited to the topics covered in class, but they must have some data-structure content. Experimental problems and problems related to your own primary research area are especially welcome. Above all, it should be a problem who solution youwantto know but don't.- Before the end of the semester, teams of up to three students will submit solutions for a small subset of the submitted problems, preferably excluding their own. Students are encouraged to collaborate with anyone in or out of class (with proper credit, of course). Each team will also give a short oral presentation of their results.
idealresult 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, promising approaches for solving the problem(s), and ideas that looked promising but weren't (and why).

Any student who actually publishes work done in this class automatically (and, if necessary, retroactively) gets an A+. This offer trumpsallother course requirements.