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

Winter 2023 --- Course Syllabus





New / Messages  


january 30, 2023: Gavin's office hours on February 1 will be from 11am-1pm (just this once).

December 27, 2022: Classes will be in person. There will not be parallel zoom sessions. No video recordings will be available.

October 19, 2022: I condemn in the strongest possible terms McGill University's decision not to require vaccinations for in-person classes.


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
April 11: Last lecture.


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


Lectures (2023)


Material covered in each lecture in 2023.


Lectures (2022)


Material covered in each lecture in 2022. The pace in 2023 will be similar, but the material may change slightly.


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 and 2022 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.