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

Email: https://cs.uwaterloo.ca/%7Eimunro/ian.GIF

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

Specific topics:

·         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.


Assignment 1 Due Thursday, October 13, in class

Assignment 2 Due Thursday, November 8, in class

Assignment 3 Due Thursday, November 24, in class

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

Succinct data structures see succinct slides and Succinct DS survey

Unit 2: Text Search and Succinct Data Structures

Unit 3: Self Organizing Linear Search

Unit 4: Self Organizing Binary Search Trees


Project info