**CS 840 – Fall 2020**

**Topics in Data Structures:
Time and Space Efficiency**

Instructor:
I. Munro

(Note: this page is under renovation, some of the
material is from an older version of the course)

Phone:
ext 34433 (probably not relevant)

Email:
imunro (at) uwaterloo (dot)
ca

Time: I have currently scheduled synchronous sessions for
1:30 to 3:00 Wednesday and Fridays. I am in the process of moving more files
directly on line so the course will be much more asynchronous than I had
originally planned. I expect to have a synchronous session either September 16
or 18 (probably the 16^{th}. More here later.

Place: On line with TEAMS, more to be announced

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

· comparison based complexity (e.g. sorting and selection)

· 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) plus some
very sort assignments ~45

Project – paper review/start ~10

- written ~25

- presentation in class ~10

Class participation ~10 (details to be worked
out)

Project: Read several fairly recent papers, attempt to improve or apply
results, and report in class and written report. Projects can involve
implementations. Groups of two are certainly encouraged for the project, but we
will see how feasible this. (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: **(The last two listed below
are from a previous version of the course, they give the idea, but will
probably be updated; the first two are from this year)

**Notes, references etc:**

Unit 1:
Models, Lower Bounds and getting around Lower Bounds

Power Point
presentations for Unit 1

Unit2.2Self Organizing Linear
Search1

Unit2.3Self Organizing Linear
Search2

Unit2.4Self Organizing Linear
Search3

Unit2.5Self Organizing Linear
Search4

Unit3.1Optimal Binary Search Trees

Unit3.2Approximately Optimal Binary
Search Trees

Unit3.3.Self Organizing Binary Search Trees

Unit4.3Space Efficient
Structures

Unit4.4Succinct Data Structures

More Power Point
presentations for Unit 4 … coming soon

Unit 1
Searching

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 and Binary Search Trees

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