


Computer Science 252
Algorithms and Data Structures
Last update: February 15, 2020
Winter 2020  Course Syllabus



New / Messages

February 15: You can look at your midterms in the TA office (MC311) during regular TA office hours next week. I will hand out a paper copy of the answers next Tuesday in class.
February 14: You can look at your midterms in the TA office (MC311) between 10 and 12 today and during regular TA office hours next week.
February 11: Change of strategy: future assignments will now be due at 9:55am, at the end of the lecture.
February 10: The midterm will cover all material up to and including the lecture given on February 11. It has eight questions, of which two ask for explicit algorithms, and are worth 40%.
February 6: Please note that Anna prefers hard copies for assignment 3.
February 4: Assignment 3 handed out. It is due on February 11 at 8:30am. This will be corrected by Anna Brandenberger. Hard copies in classno email submissions to Anna.
January 29: The 3hour final will be on April 30, at 9am.
January 24: Assignment 2 due by Thursday 8:30am. Email versions to Konrad Anand, or hand in a paper copy in class.
January 16: Assignment 1 due by Tuesday 8:30am. Email versions to Gavin McCracken, or hand in a paper copy in class.
January 9: Sentence about a TA strike added.
January 5: Course planlecture by lectureposted here.
January 5: This page launched. Welcome to COMP252, Winter 2020.

Instructor

Luc Devroye 
Email to lucdevroye@gmail.com 
Tel: (514) 3983738 (office) 
McConnell Engineering Building, Room 300N 
Office hours: Tuesday, 1011:30am, Thursday, 1011:30am, starting January 7, 2020.

Time and location

Tuesday & Thursday, 8:3010am, Trottier 0100.
January 7: First lecture
February 13: Midterm in Trottier 0100
March 26: Study break.
April 9: Last lecture.
April 30: Final exam, 9am.

The supplemental

Should you have to take the supplemental or a deferred final,
please take note that the supplemental or deferred
exam counts for 100 percent of the mark.

Teaching assistants 
Anna Brandenberger. Mail to anna.brandenberger@mail.mcgill.ca.
Gavin McCracken. Mail to gavin.mccracken@mail.mcgill.ca.
Konrad Anand. Mail to konrad.anand@mail.mcgill.ca.
The TA hours: Monday, Wednesday and Friday, 912am, McConnell 311.
The provisional schedule:
Monday: Anna Brandenberger, Wednesday: Gavin McCracken, Friday: Konrad Anand.

Lectures (2020)

Material covered in each lecture in 2020

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.
 Tries, suffix trees.
 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% (Six theoretical assignments will be given,
each worth 7% of the total mark.)
 Midterm: 8%
 Final: 50%
 We were asked to add the following sentence in case of a TA strike: In the event of extraordinary circumstances beyond the University's
control, the evaluation scheme in a Course is subject to change,
provided that there be timely communications to the students regarding
the change.

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, and 2019 and 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.


