Course Description -- COMP252 -- Algorithms and Data Structures

Computer Science 252
Honours Algorithms and Data Structures

Winter 2025 --- Course Syllabus

New / Messages

Instructor

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

Tuesday, 3:15-4:15 pm.
Thursday, 6:15-7:15 pm.

Time and location

Tuesday & Thursday, 4:30-6 pm, Stewart Bio S3/3.
January 6: First lecture
February 14: Extra Friday lecture from 8:30-10 am in a room to be announced.
February 18: Midterm from 4:30-6 pm in our usual classroom (STBIO S3/3).
March 3-7: Reading week.
March 21: Extra Friday lecture from 8:30-10 am in a room to be announced.
April 1 and 3: No lectures.
April 10: Last lecture.
Final exam to be announced.

On the web

Link to myCourses for the Winter 2025 edition. We will use myCourses for announcements, assignments and Ed Discussion (click on Content and then on Ed Discussion). We will not use it to keep track of marks, but we may announce grades on myCourses.

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

Rohit Vasishta. Email: rohit.vasishta@mail.mcgill.ca.
Will Henderson. Email: williamzahary@gmail.com.

Lectures (2024)

Material covered in each lecture in 2024. We will maintain a similar page 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 40%, midterm 10%, final 50%.
Rubric for zealous bureaucrats: 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.

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 (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 and 2024 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. Errata: page 6, line 5 of code for INSERT: The if statement is outside the while loop. The proof on page 7 needs fixing.
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 2025 --- Course Syllabus

New / Messages
Instructor	Luc Devroye \| Email to lucdevroye@gmail.com \| McConnell Engineering Building, Room 300N \| Office hours for the Winter 2025 term: Tuesday, 3:15-4:15 pm. Thursday, 6:15-7:15 pm.
Time and location	Tuesday & Thursday, 4:30-6 pm, Stewart Bio S3/3. January 6: First lecture February 14: Extra Friday lecture from 8:30-10 am in a room to be announced. February 18: Midterm from 4:30-6 pm in our usual classroom (STBIO S3/3). March 3-7: Reading week. March 21: Extra Friday lecture from 8:30-10 am in a room to be announced. April 1 and 3: No lectures. April 10: Last lecture. Final exam to be announced.
On the web	Link to myCourses for the Winter 2025 edition. We will use myCourses for announcements, assignments and Ed Discussion (click on Content and then on Ed Discussion). We will not use it to keep track of marks, but we may announce grades on myCourses.
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	Rohit Vasishta. Email: rohit.vasishta@mail.mcgill.ca. Will Henderson. Email: williamzahary@gmail.com.
Lectures (2024)	Material covered in each lecture in 2024. We will maintain a similar page 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 40%, midterm 10%, final 50%. Rubric for zealous bureaucrats: 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.
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 (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 and 2024 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. Errata: page 6, line 5 of code for INSERT: The if statement is outside the while loop. The proof on page 7 needs fixing. 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.