


Computer Science 251
Data Structures and Algorithms
Last update: April 29, 2019
Winter 2019  Course Syllabus



New / Messages

Second viewing of the final: June 13, 2019, from 12pm in Luc's office, McConnell 300.
Viewing of the final: May 1, 2019, from 12pm in Luc's office, McConnell 300.
Grades have been posted on Minerva.
Solution of the final posted.

Instructor

Luc Devroye 
Email to lucdevroye@gmail.com 
Tel: (514) 3983738 (office) 
McConnell Engineering Building, Room 300N 
Office hours: Tuesday, 1011:30am, Thursday, 1011:30am, until April 15.

Auxiliary instructor

Erin McLeish

Time and location

Duplicate lectures will be given every Tuesday and Thursday.
There is a smaller room (Bronfman 422) for an 8:3010am lecture,
and a larger room (McMed 522) for a 12:30pm lecture.
The same lecturer will give both on the same day.
Most lectures will be by Luc Devroye, and some by Erin McLeish.
January 8: First lecture
February 5: Midterm I.
March 48: Study break.
March 11: Midterm II.
April 11: Last lecture.
April 16: Final exam, 25pm.

Teaching assistants


TA office and hours

Trottier 3110.
 Mo 45pm. (Konrad Anand)
 Tu 45pm (Anna Brandenberger)
 We 45pm. (Gavin McCracken (except April 10) and Xoey Zhang)
 Thu 46pm. (Ravi Chunduru)
 Fri 910am. (Hang Li)
 Fri 1011:30am. (Shanqing Zhu and Ben Yu)
Trottier 3120.
 Mo: 10:0011:30am. (Konrad Anand and Gavin McCracken)
 Tue: 2:304pm. (Auguste Lalande)
 We: 10:0011:30am. (Hang Li, Shanqing Zhu and Ben Yu)
 Thu: 2:304pm. (Auguste Lalande)

The supplemental

Should you have to take the supplemental, please take note that the supplemental
exam counts for 100 percent of the mark.

Lectures (2019)

Material covered in each lecture in 2019

Assignments

Assignment 1 (Divideandconquer). January 10, 2019.
Solutions of Assignment 1 (Divideandconquer). January 21, 2019. Updated January 29, 2019.
Assignment 2 (Dynamic programming). January 22, 2019.
Solutions of Assignment 2 (Dynamic programming). January 31, 2019.
Solutions of Midterm1. February 5, 2019.
Assignment 3 (Trees). February 12, 2019.
Assignment 4 (Redblack trees, augmented trees). February 19, 2019.
Solution of assignment 3 (Trees). February 25, 2019.
Solution of assignment 4 (Redblack trees, augmented trees). March 6, 2019.
Solutions of Midterm2. March 11, 2019.
Practice questions by Henri Mertens. March 13, 2019. TeXed version of the practice questions (courtesy of Gemma Huang).
Assignment 5 (Compression, greedy algorithms). March 16, 2019.
Solution of assignment 5 (Compression, greedy algorithms). April 4, 2019.
Solution of the final exam. April 18, 2019.

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.
 Dynamic programming.
 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

Evaluation

 Assignments: 0% (Six theoretical assignments will be given.
Please solve them alone or in study groups, and consult the TAs if necessary.)
 Midterms: Two midterms will be given, each worth 15%.
 Final: 70%

Prerequisites

Computer Science 250. Mathematics 240.
Recommended background: Mathematics, discrete mathematics, arguments by induction.

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 earlier
editions of this book. These will do too.
A list of errata of the second printing
is available online.
Excellent pirated copies of this book can be found via Google Search.
Finally, scribes in 2017, 2018 and 2019 made notes on the following topics:


