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 1-2pm in Luc's office, McConnell 300.

Viewing of the final: May 1, 2019, from 1-2pm in Luc's office, McConnell 300.

Grades have been posted on Minerva.

Solution of the final posted.


Luc Devroye | Email to | Tel: (514) 398-3738 (office) | McConnell Engineering Building, Room 300N | Office hours: Tuesday, 10-11:30am, Thursday, 10-11: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:30-10am lecture, and a larger room (McMed 522) for a 1-2: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 4-8: Study break.
March 11: Midterm II.
April 11: Last lecture.
April 16: Final exam, 2-5pm.

Teaching assistants  

TA office and hours  

Trottier 3110.

  • Mo 4-5pm. (Konrad Anand)
  • Tu 4-5pm (Anna Brandenberger)
  • We 4-5pm. (Gavin McCracken (except April 10) and Xoey Zhang)
  • Thu 4-6pm. (Ravi Chunduru)
  • Fri 9-10am. (Hang Li)
  • Fri 10-11:30am. (Shanqing Zhu and Ben Yu)

Trottier 3120.

  • Mo: 10:00-11:30am. (Konrad Anand and Gavin McCracken)
  • Tue: 2:30--4pm. (Auguste Lalande)
  • We: 10:00-11:30am. (Hang Li, Shanqing Zhu and Ben Yu)
  • Thu: 2:30--4pm. (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


Assignment 1 (Divide-and-conquer). January 10, 2019.
Solutions of Assignment 1 (Divide-and-conquer). 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 (Red-black trees, augmented trees). February 19, 2019.
Solution of assignment 3 (Trees). February 25, 2019.
Solution of assignment 4 (Red-black trees, augmented trees). March 6, 2019.
Solutions of Midterm2. March 11, 2019.
Practice questions by Henri Mertens. March 13, 2019. TeX-ed 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.


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


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, merge-find 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.
  • Worst-case and expected time complexity.
  • Analysis of simple recursive and nonrecursive algorithms.
  • Searching, merging and sorting.
  • Amortized analysis.
  • Lower bounds.
  • Introductory notions of algorithm design:
    • Divide-and-conquer. 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.
    • Depth-first search and breadth-first search
    • Shortest path problems
    • Minimum spanning trees
    • Directed acyclic graphs


  • 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%


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


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 on-line. 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: