Computer Science 252
Algorithms and Data Structures
Last update: January 24, 2020

Winter 2020 --- Course Syllabus





New / Messages  


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 plan---lecture by lecture---posted here.

January 5: This page launched. Welcome to COMP252, Winter 2020.


Instructor  


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


Time and location


Tuesday & Thursday, 8:30-10am, Trottier 0100.
January 7: First lecture
February 13: Midterm in Trottier 0100
March 2-6: Study break.
April 9: Last lecture.


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, 9-12am, 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, merge-find 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.
  • 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% (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.