Course Description -- COMP252 -- Algorithms and Data Structures

Computer Science 252
Honours Algorithms and Data Structures

Winter 2026 --- Course Syllabus

New / Messages
Aarrgghh---a typo in question 1 of assignment 1. The last two occurences of A_n in that question should read D_n.

Instructor

Luc Devroye | Email to lucdevroye@gmail.com | McConnell Engineering Building, Room 300N | Office hours for the Winter 2026 term:

Tuesday, 2:45-3:45 pm.
Thursday, 2:45-3:45 pm.

Time and location

Tuesday & Thursday, 1-2:30 pm, Stewart Biology Building (STBIO) N2/2.
January 6: First lecture
February 17: Midterm from 1-2:30 pm, room TBA.
March 2-6: Reading week.
April 9: Last lecture.

On the web

Link to myCourses for the Winter 2026 edition. We will not use myCourses for anything.

Special situations

If you write a supplemental or deferred final exam, then that exam will count for 100% towards your grade---midterms and assignments will be irrelevant. If you miss the midterm, then you will be given an oral examination within a few days.

Teaching assistants
The teaching assistants will meet in McConnell 310/311.

Nikola Katov. Email: nikola.katov@mail.mcgill.ca. Office hours: Monday, 2-3 pm, Wednesday, 3-4 pm.
Shan Gao. Email: shan.gao5@mail.mcgill.ca. Office hours: Friday, 10:15 am-12:15 pm.

Lectures (2026)

Material covered in each lecture in 2026 (file updated as we move along). For reference: Material covered in each lecture in 2025.

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, merge-find set and dictionary.

Heaps.

Binary search trees, balanced search trees.

Stringology: Tries, suffix trees, pattern matching.

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. Fast Fourier transform.

Dynamic programming. Examples such as Bellman-Ford network flow, sequence alignment, knapsack problems and Viterbi's algorithm.

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

Network flows and bipartite matching

Evaluation

Assignments: 25%, midterm: 25%, final: 50%.
Rubric: the assignments are theoretical (no programming involved) and are judged on correctness, insight, originality and readability. The midterm and final are judged on correctness and clarity of the answers. All assignments will be written by hand and returned in class.

Prerequisites

Computer Science 250. Mathematics 240 or Mathematics 235. 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 (Fourth Edition), MIT Press, Cambridge, MA, 2022. The Third Edition of this book, published in 2009, is almost equivalent. Github offers pages with solutions of most exercises.
Another appropriate text, with a different focus (more algorithms, fewer data structures) is by J. Kleinberg and E. Tardos: "Algorithm Design". Pearson, Boston, 2006.
Finally, scribes in 2017, 2018, 2019, 2020, 2022, 2023, 2024 and 2025 made notes on the following topics:

Landau symbols.
Divide and conquer I.
Divide and conquer II.
Divide and conquer III.
Dynamic programming .
Lower bounds.
ADTs, lists, stacks
Intro to trees
Dictionary, binary search tree
Red-black trees.
Augmented data structures.
Cartesian trees.
Priority queues.
Amortized analysis.
Splay trees.
Disjoint sets.
Hashing and Bloom filters.
Stringology.
Introduction to information theory.
Shannon's theory.
Lempel-Ziv compression.
Graph algorithms (DFS, BFS).
MST and shortest paths.
Dags (directed acyclic graphs).
Flows.
The Hungarian method.

Information for the scribes

We will use LaTeX to first create a TeX file (for the body of the text) and a bib file (for bibliography), and then create a PDF file from this. The prototypes below are courtesy of Ralph Sarkis.

A package handler can get you LaTeX, if you are not familiar with it. We use a particular brand of LaTeX, Tufte LaTeX, which is based on Edward Tufte's recommendations for handouts and course notes. Github link for Tufte LaTeX.
A sample TeX file.
A prototype bib file.
The PDF output for the sample TeX file.
A figure in png format, to be placed in the same directory as the TeX file.
Another figure in png format, to be placed in the same directory as the TeX file.


	Computer Science 252 Honours Algorithms and Data Structures Winter 2026 --- Course Syllabus

New / Messages	Aarrgghh---a typo in question 1 of assignment 1. The last two occurences of A_n in that question should read D_n.
Instructor	Luc Devroye \| Email to lucdevroye@gmail.com \| McConnell Engineering Building, Room 300N \| Office hours for the Winter 2026 term: Tuesday, 2:45-3:45 pm. Thursday, 2:45-3:45 pm.
Time and location	Tuesday & Thursday, 1-2:30 pm, Stewart Biology Building (STBIO) N2/2. January 6: First lecture February 17: Midterm from 1-2:30 pm, room TBA. March 2-6: Reading week. April 9: Last lecture.
On the web	Link to myCourses for the Winter 2026 edition. We will not use myCourses for anything.
Special situations	If you write a supplemental or deferred final exam, then that exam will count for 100% towards your grade---midterms and assignments will be irrelevant. If you miss the midterm, then you will be given an oral examination within a few days.
Teaching assistants	The teaching assistants will meet in McConnell 310/311. Nikola Katov. Email: nikola.katov@mail.mcgill.ca. Office hours: Monday, 2-3 pm, Wednesday, 3-4 pm. Shan Gao. Email: shan.gao5@mail.mcgill.ca. Office hours: Friday, 10:15 am-12:15 pm.
Lectures (2026)	Material covered in each lecture in 2026 (file updated as we move along). For reference: Material covered in each lecture in 2025.
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, merge-find set and dictionary. Heaps. Binary search trees, balanced search trees. Stringology: Tries, suffix trees, pattern matching. 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. Fast Fourier transform. Dynamic programming. Examples such as Bellman-Ford network flow, sequence alignment, knapsack problems and Viterbi's algorithm. 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 Network flows and bipartite matching
Evaluation	Assignments: 25%, midterm: 25%, final: 50%. Rubric: the assignments are theoretical (no programming involved) and are judged on correctness, insight, originality and readability. The midterm and final are judged on correctness and clarity of the answers. All assignments will be written by hand and returned in class.
Prerequisites	Computer Science 250. Mathematics 240 or Mathematics 235. 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 (Fourth Edition), MIT Press, Cambridge, MA, 2022. The Third Edition of this book, published in 2009, is almost equivalent. Github offers pages with solutions of most exercises. Another appropriate text, with a different focus (more algorithms, fewer data structures) is by J. Kleinberg and E. Tardos: "Algorithm Design". Pearson, Boston, 2006. Finally, scribes in 2017, 2018, 2019, 2020, 2022, 2023, 2024 and 2025 made notes on the following topics: Landau symbols. Divide and conquer I. Divide and conquer II. Divide and conquer III. Dynamic programming . Lower bounds. ADTs, lists, stacks Intro to trees Dictionary, binary search tree Red-black trees. Augmented data structures. Cartesian trees. Priority queues. Amortized analysis. Splay trees. Disjoint sets. Hashing and Bloom filters. Stringology. Introduction to information theory. Shannon's theory. Lempel-Ziv compression. Graph algorithms (DFS, BFS). MST and shortest paths. Dags (directed acyclic graphs). Flows. The Hungarian method.
Information for the scribes	We will use LaTeX to first create a TeX file (for the body of the text) and a bib file (for bibliography), and then create a PDF file from this. The prototypes below are courtesy of Ralph Sarkis. A package handler can get you LaTeX, if you are not familiar with it. We use a particular brand of LaTeX, Tufte LaTeX, which is based on Edward Tufte's recommendations for handouts and course notes. Github link for Tufte LaTeX. A sample TeX file. A prototype bib file. The PDF output for the sample TeX file. A figure in png format, to be placed in the same directory as the TeX file. Another figure in png format, to be placed in the same directory as the TeX file.