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 16th. 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)

Microassignment1

Assignment 1 Due October 8

Assignment 2 Due November 2

Assignment 3 Due November 30

 

Notes, references etc:

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

Power Point presentations for Unit 1

Unit1.1Searching

Unit1.2MoreSearching

Unit1.3vEB1

Unit1.4vEB2

Unit1.5CacheOblivious1

Unit1.6CacheOblivious2

Unit2.1Competitive_Paging

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.1.One Shot Text Search

Unit4.2 Suffix Trees

Unit4.3Space Efficient Structures

Unit4.4Succinct Data Structures

Unit4.5SuccinctTrees2

Unit5PersistentDataStructures

Unit6.1Sorting

Unit6.2Selection.pptx

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:

Project info