


Computer Science 251
Data Structures and Algorithms
Last update: March 17, 2018
Winter 2019  Course Syllabus



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 12,
and any time my door is open.

Time and location

Tuesday & Thursday, 12:30pm, McMED 522
January 7: First lecture
February 7: Midterm I in McMED 522
March 48: Reading week.
March 14: Midterm II in McMED 522
April 12: Last lecture.

The supplemental

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

Teaching assistants 
Tommy Reddad, McConnell Engineering 310.
Email to Tommy Reddad.
Office hours: Monday, 1012am. Wednesday 11am1pm.

Lectures (2019)

Material covered in each lecture in 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. 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: 0% (Six theoretical assignments will be given,
each worth 0% of the total mark.)
 Midterms I and II: 25% each.
 Final: 50%

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 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.
Scribes in 2017 and 2018 in the sister course, 252, made notes on the following topics:

Online resources

Class notes
(Outdated) class notes from 1997 compiled by students, listed below. Use at your own risk.


