Course Description -- Information Structures

Computer Science 308-610A
CS308-610A: Information Structures
Last update: January 8, 2013

Winter 2013 -- Course syllabus

Instructor

Luc Devroye

Email to lucdevroye@gmail.com
Tel: (514) 398-3738 (office)

McConnell Engineering Building, Room 300N

Office hours: Tuesday, 10am-11:30am

Teaching assistant

Shi Tai Liu

Office hours: Mon 10:30-11:30am, Wed 1:30-2:30pm.
Office: McConnell 224.
Email to shitai.liu@cs.mcgill.ca.

Location

Tuesday, Thursday 8:30-10:00. McConnell 300.

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

Elements from discrete mathematics (parts of chapters 1-5). Examples of recurrences.
Elementary data structures: lists, stacks, queues, trees, hash tables, binary search trees, red-black trees, heaps, augmenting data structures (chapters 6, 10-14).
Sorting and selection: quicksort, mergesort, bucket sort, linear time selection (chapters 7-9).
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, Lempel-Ziv compression, move-to-front compression, Kraft's inequality, entropy.
Paradigms for algorithms (superficial coverage): greedy methods, heuristics, dynamic programming, string matching.
Lower bounds. Information-theoretic methods. Adversary methods.
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, nine assignments are planned.

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), move-to-front 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.


	Computer Science 308-610A CS308-610A: Information Structures Last update: January 8, 2013 Winter 2013 -- Course syllabus

Instructor	Luc Devroye Email to lucdevroye@gmail.com Tel: (514) 398-3738 (office) McConnell Engineering Building, Room 300N Office hours: Tuesday, 10am-11:30am
Teaching assistant	Shi Tai Liu Office hours: Mon 10:30-11:30am, Wed 1:30-2:30pm. Office: McConnell 224. Email to shitai.liu@cs.mcgill.ca.
Location	Tuesday, Thursday 8:30-10:00. McConnell 300.
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	Elements from discrete mathematics (parts of chapters 1-5). Examples of recurrences. Elementary data structures: lists, stacks, queues, trees, hash tables, binary search trees, red-black trees, heaps, augmenting data structures (chapters 6, 10-14). Sorting and selection: quicksort, mergesort, bucket sort, linear time selection (chapters 7-9). 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, Lempel-Ziv compression, move-to-front compression, Kraft's inequality, entropy. Paradigms for algorithms (superficial coverage): greedy methods, heuristics, dynamic programming, string matching. Lower bounds. Information-theoretic methods. Adversary methods. 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, nine assignments are planned.
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), move-to-front 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.