CS 840 - Fall 2016
Topics in Data Structures
Instructor: I. Munro
Class Time: Tuesdays and Thursdays 9:30 - 10:50 in DC 2568
Phone: ext 34433
This course will cover a number of recent results, as well as some older ones, on data structures and the algorithms acting upon them. Of particular interest will be the idea of using lower bounds, not to establish the impossibility of performing a task quickly, but to focus on the primitive operations one must have in order to achieve the desired bound. Particular interest: Lower bounds as a means to find algorithms
· priority queues,
· techniques on search trees such as splay trees,
· "competitive" search structures,
· time and space efficient structures for text search,
· space efficient representations of trees,
· issues in memory management for data structures,
· specialized techniques for data compression
· a variety of other issues depending on interests of the class.
A great starting point for theses/essays
Prerequisites: Solid undergraduate knowledge of basic data structures required (like CS 240). An "algorithms course" like CS 666 helpful, but is not necessary.
Organization: First part - lectures primarily by the instructor. Later classes - seminars by members of the class.
Assignments/short paper review (3) ~45
Project – paper review/start ~10
- written ~25
- presentation in class ~10
Class participation ~10
Project: Read several recent papers, attempt to improve or apply results, and report in class and written report. Projects can involve implementations. Groups of two are encouraged for the project. (see also below)
Text etc: There is no formal text, most of the material covered will come from the recent literature in the field of algorithms and data structures. A standard advanced level text such as Introduction to Algorithms by Cormen, Leiserson, Rivest and Stein will, however, be a useful reference. Most of the lectures will follow the online references below. In cases where the material comes from several sources, or the papers are not online, lecture notes will (generally) be provided.
Notes, references etc:
van Emde Boas “priority queue” see Chapter 20 of CLRS (edition 3)
Rambo model see Rambo slides
Cache oblivious data structures see Frigo et al