**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:

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 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:**