CS 840 - Fall 2020

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)

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.5CacheOblivious1