


Computer Science 308610A
CS308610A: Information Structures
Last update: January 3, 2014
Winter 2014  Course syllabus



Instructor

Luc Devroye
 Email to lucdevroye@gmail.com
 Tel: (514) 3983738 (office)
 McConnell Engineering Building, Room 300N
 Office hours: Monday, Wednesday, 10am11:30am

Teaching assistant

Hang Ma

Location

Monday, Wednesday, 8:3010:00. McConnell 320.

Description

We cover all the fundamental data structures
and algorithms.
The performance of each algorithm is
analyzed, and the students can practice
their skills on many interesting problems
and exercises.
There is no programming component.

Contents

Material seen in 2014, lecture by lecture.

Elements from discrete mathematics (parts of chapters 15).
Examples of recurrences.

Lower bounds. Informationtheoretic methods.
Adversary methods.

Elementary data structures: lists, stacks, queues, trees,
hash tables, binary search trees, redblack trees, heaps,
augmenting data structures (chapters 6, 1014).

Sorting and selection: quicksort, mergesort, bucket sort, linear
time selection (chapters 79).

Advanced data structures: binomial heaps (chapter 19),
Fibonacci heaps (chapter 20),
disjoint set structures (chapter 21), leftist heaps,
fractional cascading, Van Emde Boas trees,
Willard's trees,
Iacono's working set data structure,
splay trees and pagodas (from notes).
Amortizing (chapter 17).

Data structures in compression: Huffman trees,
digital trees and tries, LempelZiv compression,
movetofront compression, Kraft's inequality, entropy.

Paradigms for algorithms (superficial coverage): greedy methods,
heuristics, dynamic programming, string matching.

Graph algorithms. Minimal spanning tree, shortest path, matching.

Fast Fourier transform (chapter 30). Polynomial multiplication.
Convolution. String alignment.

Evaluation

Regularly, a set of problems will be assigned.
These include ordinary textbook problems
as well as data structure problems drawn from a variety
of application fields.
In all, eight assignments are planned.
There is no formal final examination.

Textbook

We will follow Cormen, Leiserson, Rivest and Stein (2009).
Occasionally, there will be a handout about
a topic that is not covered in the textbook,
such as leftist heaps (Tarjan),
splay trees (Tarjan and Sleator),
Willard's trees (Willard),
Van Emde Boas trees,
skip lists (Pugh),
the working set data structure (Iacono),
movetofront compression (Bentley, Sleator, Tarjan, Wei),
space partition trees for graphics (Samet)
or suffix trees for string searching (Stephen).
T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein: "Introduction to
Algorithms Third Edition", MIT Press, Cambridge, MA, 2009.


