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

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

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

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