


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



New / Messages 
Luc will have onetime office hours on April 25 (from 25 pm) and on April 26 (from 45 pm).
The final will take place on April 29th from 912 am in Leacock 219.

Instructor 
Luc Devroye 
Email to lucdevroye@gmail.com 
McConnell Engineering Building, Room 300N 
Office hours:
 Tuesday, 2:453:45pm.
 Thursday, 11:3012:30am.
 Onetime office hours on April 25 (from 25 pm) and on April 26 (from 45 pm).

Time and location 
Tuesday & Thursday, 12:30pm, Stewart N2/2.
January 4: First lecture
February 15: Midterm from 12: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 am10:30 am in STBIO S3/3.
March 48: Reading week.
March 15: Extra lecture from 9 am10:30 am in STBIO S3/3.
March 26 and 28: No lectures.
April 9: Last lecture.
April 29: Final exam from 912am 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 grademidterms
and assignments will be irrelevant.

Teaching assistants: Office hours 

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, mergefind 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.
 Worstcase and expected time complexity.
 Analysis of simple recursive and nonrecursive algorithms.
 Searching, merging and sorting.
 Amortized analysis.
 Lower bounds.
 Introductory notions of algorithm design:
 Divideandconquer. Recurrences. The master theorem. Quicksort. Other examples such as fast multiplication of polynomials and matrices. Fast Fourier transform.
 Dynamic programming. Examples such as BellmanFord network flow, sequence alignment, knapsack problems and Viterbi's algorithm.
 Greedy methods. This includes the minimal spanning tree algorithm and Huffman coding.
 Graph algorithms.
 Depthfirst search and breadthfirst 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:

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.


