


Computer Science 252
Algorithms and Data Structures
Last update: March 23, 2015
Winter 2015  Course Syllabus



Instructor

Luc Devroye 
Email to lucdevroye@gmail.com 
Tel: (514) 3983738 (office) 
McConnell Engineering Building, Room 300N 
Office hours: Tuesday, 13:0014:00pm, Wednesday, 1011:30am,
and any time my door is open.
You don't work for meI work for you.

Time and location

Tuesday, Thursday, 11:3013:00, January 6, 2015  April 2, 2015.
Room: Trottier 70.
Midterm: February 17, 2015, 11:3013:00am, Trottier 70.
Study break: March 26, 2015.
Extra lecture: Friday, February 27, 2015, 11:30am1pm, Leacock 14.
Extra lecture: Friday, March 27, 2015, 11:30am1pm, Trottier 2120.
These lectures replace those of April 7 and 9.
Final: April 27, 25pm, SADB 1/12.
Assignment 6:
Assignment 6 can be picked up Monday April 20 and Tuesday April 21 from 1112am in my office. Later pickups can be arranged by email.
If you just want to know your grade, email me.

The final

No cheat sheets, no devices.
The final comprises seven questions:
 Question 1. Algorithm from the early part of the course (30%)
 Question 2. Definition with a drawing (10%)
 Question 3. Six definitionsall answers should be short (12%)
 Question 4. Graph algorithm (20%)
 Question 5. Hashing (10%)
 Question 6. An algorithm from the latter part of the course (10%)
 Question 7. An algorithm from the latter part of the course (8%)

Teaching assistants 
Email to Maziar Gomrokchi.
Office hours: Monday, 11:30am1pm, Wednesday, 45:30pm. Office: McConnell South 110 (Quantum Information Theory Lab).
Email to Haomin (Calvin) Zheng.

Lectures (2015)

Material covered in each lecture in 2015.
Material covered in each lecture in 2014.
This is for your information only. The pace, order and contents in 2015
may be different.
In fact, some topics
will be skipped altogether, and at least two new ones will be
introduced.

Objectives

 Introduce the student to algorithmic analysis.
 Introduce the student to the fundamental data structures.
 Introduce the student to problem solving paradigms.

Contents

Part 1. Data types.
 Abstract data types.
 Lists. Linked lists. Examples such as sparse arrays.
 Stacks. Examples of the use of stacks in recursion and problem solving.
 Queues.
 Trees. Traversal. Implementations. Binary trees.
 Indexing methods. Hashing.
 Introduction to abstract data types such as mathematical set,
priority queue, mergefind set and dictionary.
 Heaps.
 Binary search trees, balanced search trees.
 Tries, suffix trees.
 Data structures for coding and compression.
Part 2. Algorithm design and analysis.
 The running time of a program.
 Worstcase and expected time complexity.
 Analysis of simple recursive and nonrecursive algorithms.
 Searching, merging and sorting.
 Amortized analysis.
 Lower bounds.
 Introductory notions of algorithm design:
 Divideandconquer. Recurrences. The master theorem. Quicksort. Other examples such as fast multiplication of polynomials and matrices. Fast Fourier transform.
 Dynamic programming. Examples such as BellmanFord network flow, sequence alignment, knapsack problems and Viterbi's algorithm.
 Greedy methods. This includes the minimal spanning tree algorithm and Huffman coding.
 Graph algorithms.
 Depthfirst search and breadthfirst search
 Shortest path problems
 Minimum spanning trees
 Directed acyclic graphs
 Network flows and bipartite matching

Evaluation

 Assignments: 42% (Six theoretical assignments will be given,
each worth 7% of the total mark.)
 Midterm: 8%
 Final: 50%

Prerequisites

Computer Science 250. Mathematics 240.
Recommended background: Mathematics, discrete mathematics, arguments by induction.
Restricted to Honours students in Mathematics and/or Computer Science.

Textbook

T.H. Cormen, C.E.Leiserson, R.L.Rivest, and C. Stein:
Introduction to Algorithms (Third Edition), MIT Press, Cambridge, MA, 2009. Amazon link.
There are several printings of the first
edition of this book. All are equivalent.
A list of errata of the second printing
is available online.
Excellent pirated copies of this book are navigating the web.
Another appropriate text, with a different focus (more algorithms, fewer data structures) is by J. Kleinberg and E. Tardos:
"Algorithm Design". Pearson, Boston, 2006.

Online resources

Class notes
(Outdated) class notes from 1997 compiled by students, listed below. Use at your own risk.
Old Assignments
Assignment 1 (Jan 18, 2000)
Assignment 2 (Feb 8, 2000)
Solution of assignment 2
Assignment 3 (Mar 14, 2000)
Solution of assignment 3
Assignment 4 (Mar 21, 2000)
Solution of assignment 4
Old Tutorials
Tutorial 2 (Feb 1, 2000)
Tutorial 4 (Mar 7, 2000)
Old Midterms
Midterm 1992: PostScript
Midterm 1996: PostScript
Midterm 1997: PostScript; PDF
Midterm 1999: PostScript; PDF
First midterm 2000: HTML
Second midterm 2000: HTML
Old Finals
Finals pre1996: PostScript
Final 1996: PostScript
Final 1997: PostScript; PDF
Final 1997 answers: ascii text
Final 1999: HTML
Final 2000: HTML
Practice questions
Practice questions set 1
Practice questions set 1: answers
Practice questions set 2
Practice questions set 2: answers
Practice questions set 3
Practice questions set 3: answers
Practice questions set 4
Practice questions set 4: answers
Practice questions set 5
Practice questions set 5: answers


