Instructors: NirShavit and Danny Hendler
Important information: The hours are Mon 11-13, if you plan to miss the first meeting you should email Danny Hendler! Nir Shavit will be on vacation during the second group meeting.
Workshop Goals
This workshop is intended to educate students in understanding the relation between the theoretical and practical algorithmic aspects of designing advanced data structures. Many students, when finally arriving in the workplace, see that the accepted norm is to avoid using ``sophisticated'' state of the art structures and instead use ``simpler'' structures, many times at the price of a performance decrese. Is this phenomena justified? How hard is it really to code up a theoretically complex structure? How much of a performance improvement can one expect in practice from a strcuture that has theoretically superior worst or average case bounds? How can one check if a structure is a good fit or not.
This workshop will attempt to give students a better understanding of the issues raised by such questions.
Workshop Methodology
The students will split into groups of 2 or 3. The first part of the "workshop" will be devoted to collecting,
reading and understanding several theoretically advanced data strcutures. The second part of the course will be devoted
to
implementing and analyzing the relative performance of the algorithms. Students
will be required to submit a
detailed final report that will explain how they implemented and empirically
compared the algorithms.
Emphasis will be placed on the process of designing a complete set of tests to
complete our
understanding of how the algorithms can be expected to perform in practice,
which algorithms are suited to which
scenario and so on. The projects will be written on the university's computers.
Details on class times and course requirements.
Anybody taking this workshop is requested to register by sending mail to Danny Hendler, this can be done simply by clicking here.
List of Student Project
Reports