Course Description -- COMP252 -- Algorithms and Data Structures

Computer Science 252
Algorithms and Data Structures
Last update: January 10, 2023

Winter 2023 --- Course Syllabus

New / Messages

The final will take place on April 17, 2023 from 9-12am in Leacock 219.

Instructor

Luc Devroye | Email to lucdevroye@gmail.com | McConnell Engineering Building, Room 300N | Office hours: Tuesday, Thursday, 4-5pm.

Time and location

Tuesday & Thursday, 2:30-4pm, McConnell Engineering 11.
January 5: First lecture
February 16, 2022: Midterm
February 27-March 3: Reading week
March 17: A special lecture that replaces the April 11 lecture.
April 6: Last lecture.
April 17, 9-12am, Leacock 219: Final examination.

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

Gavin McCracken, McConnell 311. Email: gavin.mccracken@mail.mcgill.ca. Office hours: Wednesday, 10-12am.
William Henderson. Email: williamzahary@gmail.com. Office hour (in McConnell 311): Monday, 1-2pm.

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%.
Just in case McGill panics: there will never be an online exam. If McGill orders an online final, then the grades will be calculated as follows: 60% on assignments, 40% on midterm. If McGill orders an online midterm and an online final, then 100% of the weight will be on the assignments.

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 (Third Edition), MIT Press, Cambridge, MA, 2009. Amazon link. Excellent pirated copies of this book are navigating the web. A free PDF file is available from McGill's Library. Github offers pages with solutions of all 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.
Stringology.
Introduction to information theory.
Shannon's theory.
Lempel-Ziv compression.
Graph algorithms (DFS, BFS).
MST and shortest paths.
Dags (directed acyclic graphs).
Flows.

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: January 10, 2023 Winter 2023 --- Course Syllabus

New / Messages	The final will take place on April 17, 2023 from 9-12am in Leacock 219.
Instructor	Luc Devroye \| Email to lucdevroye@gmail.com \| McConnell Engineering Building, Room 300N \| Office hours: Tuesday, Thursday, 4-5pm.
Time and location	Tuesday & Thursday, 2:30-4pm, McConnell Engineering 11. January 5: First lecture February 16, 2022: Midterm February 27-March 3: Reading week March 17: A special lecture that replaces the April 11 lecture. April 6: Last lecture. April 17, 9-12am, Leacock 219: Final examination.
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	Gavin McCracken, McConnell 311. Email: gavin.mccracken@mail.mcgill.ca. Office hours: Wednesday, 10-12am. William Henderson. Email: williamzahary@gmail.com. Office hour (in McConnell 311): Monday, 1-2pm.
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%. Just in case McGill panics: there will never be an online exam. If McGill orders an online final, then the grades will be calculated as follows: 60% on assignments, 40% on midterm. If McGill orders an online midterm and an online final, then 100% of the weight will be on the assignments.
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 (Third Edition), MIT Press, Cambridge, MA, 2009. Amazon link. Excellent pirated copies of this book are navigating the web. A free PDF file is available from McGill's Library. Github offers pages with solutions of all 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. Stringology. Introduction to information theory. Shannon's theory. Lempel-Ziv compression. Graph algorithms (DFS, BFS). MST and shortest paths. Dags (directed acyclic graphs). Flows.
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.