CS 840 - Fall 2018

Topics in Data Structures 

 

 

Instructor: I. Munro

Phone: ext 34433

Email: imunro@...here

Time: 10 to 11:50 Mondays and Wednesdys (Note this is "4 hours" per week, some classes will be cancelled due to my travels, giving an average of "3 hours" per week)

Place: DC 2585

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.

Requirements:

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.

Assignments:

Assignment 1 Due Friday (logical Wednesday), October 12, in class

Assignment 2 Due Wednesday, October 31, by email or in class

Assignment 3 Due Wednesday, November 21, by email or 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 and Demaine's Survey on Cache Oblivious Structures There is also an example of the vEB layout for binary search

Unit 2: Self Organizing Linear Search

Unit 3: Self Organizing Binary Search Trees

Unit 4: Text Search and Succicnt Data Structures

For succinct data structures see also succinct slides , Succinct DS survey and Chapter Two of David Clark's Thesis

Project:

Project info