Course Description -- COMP252 -- Algorithms and Data Structures

Computer Science 252
Algorithms and Data Structures
Last update: April 24, 2024

Winter 2024 --- Course Syllabus

New / Messages

Luc will have one-time office hours on April 25 (from 2-5 pm) and on April 26 (from 4-5 pm).
The final will take place on April 29th from 9-12 am in Leacock 219.

Instructor

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

Tuesday, 2:45-3:45pm.
Thursday, 11:30-12:30am.
One-time office hours on April 25 (from 2-5 pm) and on April 26 (from 4-5 pm).

Time and location

Tuesday & Thursday, 1-2:30pm, Stewart N2/2.
January 4: First lecture
February 15: Midterm from 1-2:30 pm in our usual classroom (STBIO N2/2). An overflow room, ENGTR 1090, will be used for students whose last name starts with S, T, U, V, W, X, Y or Z.
February 23: Extra lecture from 9 am-10:30 am in STBIO S3/3.
March 4-8: Reading week.
March 15: Extra lecture from 9 am-10:30 am in STBIO S3/3.
March 26 and 28: No lectures.
April 9: Last lecture.
April 29: Final exam from 9-12am in Leacock 219.

On the web

Link to myCourses. 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.
Ed Discussion.

The supplemental

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.

Teaching assistants: Office hours

Rohit Vasishta. Email: rohit.vasishta@mail.mcgill.ca. Will run tutorials on Monday 1-2pm and Wednesday 5:30-6:30pm (repeat of the Monday tutorial), in room McConnell 321. First tutorial on Monday, January 15.
Mehran Shakerinava. Email: mehran.shakerinava@mail.mcgill.ca. Tuesday 11:30-12:30, Thursday 10-11. Room: McConnell 310. Starting January 15.
Shishir Sharma. Email: shishir.sharma@mail.mcgill.ca. Thursday, 5-7 pm, McConnell 310. Starting January 15.

Lectures (2024)

Material covered in each lecture in 2024.

Lectures (2023)

Material covered in each lecture in 2023.

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 42%, midterm 8%, final 50%.

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 and 2023 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 Algorithms and Data Structures Last update: April 24, 2024 Winter 2024 --- Course Syllabus

New / Messages	Luc will have one-time office hours on April 25 (from 2-5 pm) and on April 26 (from 4-5 pm). The final will take place on April 29th from 9-12 am in Leacock 219.
Instructor	Luc Devroye \| Email to lucdevroye@gmail.com \| McConnell Engineering Building, Room 300N \| Office hours: Tuesday, 2:45-3:45pm. Thursday, 11:30-12:30am. One-time office hours on April 25 (from 2-5 pm) and on April 26 (from 4-5 pm).
Time and location	Tuesday & Thursday, 1-2:30pm, Stewart N2/2. January 4: First lecture February 15: Midterm from 1-2:30 pm in our usual classroom (STBIO N2/2). An overflow room, ENGTR 1090, will be used for students whose last name starts with S, T, U, V, W, X, Y or Z. February 23: Extra lecture from 9 am-10:30 am in STBIO S3/3. March 4-8: Reading week. March 15: Extra lecture from 9 am-10:30 am in STBIO S3/3. March 26 and 28: No lectures. April 9: Last lecture. April 29: Final exam from 9-12am in Leacock 219.
On the web	Link to myCourses. 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. Ed Discussion.
The supplemental	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.
Teaching assistants: Office hours	Rohit Vasishta. Email: rohit.vasishta@mail.mcgill.ca. Will run tutorials on Monday 1-2pm and Wednesday 5:30-6:30pm (repeat of the Monday tutorial), in room McConnell 321. First tutorial on Monday, January 15. Mehran Shakerinava. Email: mehran.shakerinava@mail.mcgill.ca. Tuesday 11:30-12:30, Thursday 10-11. Room: McConnell 310. Starting January 15. Shishir Sharma. Email: shishir.sharma@mail.mcgill.ca. Thursday, 5-7 pm, McConnell 310. Starting January 15.
Lectures (2024)	Material covered in each lecture in 2024.
Lectures (2023)	Material covered in each lecture in 2023.
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 42%, midterm 8%, final 50%.
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 and 2023 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.