Computer Science 252
Algorithms and Data Structures
Last update: March 27, 2020

Winter 2020 --- Course Syllabus





New / Messages  


March 27: Luc's post-corona office hours announced on myCourses.

March 23: About the final. The Faculty of Science asked me to change the parameters of my assessment slightly. So here we go (and this should be definitive):

  • Assignment 6 will be emailed to you on April 9, 2020. It will also appear on our web site. It will be due on April 15 at noon. Please email it back to me by the deadline, and place a copy on myCourses for backup (instructions to follow). Assignment 6 will carry more weight and will have to be carried out individually. There will be questions on amortized analysis, compression and graph algorithms. Some have sub-questions that refer back to earlier parts of the course.
  • Assignment 5 is still due on March 31 at 10am. please subkit to myCourses!!!!
  • There is no formal final.
  • The weights are as follows:
    • Assignments 1 through 5: 12% each.
    • Midterm: 15%.
    • Assignment 6: 25%.

    March 20: Scribed notes on amortized analysis posted.

    March 20: In assignment 5, question 1, there is a misprint. The sweepline algorithm should take time O(n log n).

    March 17: About the final. We finally got instructions from McGill. So, I have a bit of good news for COMP 252, which is one of my favourite courses. We will end the course without any final, period. That is, you will have to complete assignments 5 and 6, and that will be it. Assignment 5 is due on March 31 at 10am, electronically. Assignment 6 will be given on April 9 by email broadcast, and is due on April 12, at 12 noon. The short deadline makes it a mini-take-home exam. Expect questions that will test your maturity. The questions will cover the lectures on amortized analysis, compression, and graph algorithms. The weight of assignment 6 will be as planned, the same as all other assignments. Thus, each assignment is worth 7, the midterm 8, and the total will be out of 50.

    March 16: All videos for the four remaining lectures have now been posted. The last two together cover one lecture. The others are full lectures. A big thank you to Mike Gao for assistance with the compression.

    March 15: McGill will very likely not lengthen the term. This would mean that the next 4 lectures will be canceled. We were asked to prioritize our 4 remaining lectures (4 instead of 8). I am opting for two lectures on compression (already posted) and two lectures on graph algorithms (one of which is already up). I will also prepare more lectures on graph algorithms, "just in case". We were given extraordinary powers to change the grading scheme. What is sure is that the final will be on-line. As a consequence, we will give it much less weight than 50 percent. McGill's leadership will give us instructions in the next few days. But be aware that I am tilting towards a lightly-weighted final. In the meantime, assignments 5 and 6 will become much more important, relatively speaking. Please stay safe.

    March 14: McGill just sent this email: All classes, teaching labs, exams and other assessments are suspended for two weeks except theses defenses. We will continue to work on resuming most teaching and other academic activities online by the end of this two-week period. Instructors will be in touch with students during this period to prepare for resuming academic activities. As per clarifications from the Ministry of Education and Higher Education, McGill will remain operational during the two weeks, but only necessary functions and activities will be provided on campus. And here is what I will do:

    • Assignment 5 will be due on the first day of re-opening, i.e., probably the end of next week. Stay tuned for this here.
    • I will put all future lectures on my site as videos at the rate of one per day or so. When classes resume in on-line mode, some of you will already be familiar with the material.
    • Office hours are not permitted by the McGill decree. Same for tutorials.
    • Please feel free to email the TAs or me with questions about the course material.
    • I will post assignment 6 during the down period, and make the due deadline a week after classes resume. It will effectively give you more than two weeks to work on it.
    • Discussions about the format of the final are ongoing and outside my control, but we will keep you informed on that as well.

    March 14: Assignment 5 will be submitted and corrected electronically. I will let you know which TA to mail it to later this week-end.

    March 14: I have already taped two lectures in my office, for March 17 and 19, respectively. There is a section below entitled video lectures / Corona virus. The videos are large---we will provide smaller .mp4-format videos asap.

    March 10: Assignment 5 will be handed out. It will be due on March 17 at 9:55am.

    February 25: Assignment 4 due on Thursday, February 27, at 9:55am either in class or by emailing the solution to Konrad Anand.

    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 class---no email submissions to Anna.

    January 29: The 3-hour 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 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 | Pre-corona office hours: Tuesday, 10-11:30am, Thursday, 10-11:30am, starting January 7, 2020. Post-corona office hours: Tuesday, 10-11am, Thursday, 10-11am, starting March 31, 2020, via Zoom. Zoom link on myCourses, under "announcements".


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.
April 30: Final exam, 9-12am, McConnell Engineering 204.


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


Original (now defunct) evaluation


  • Assignments: 42% (Six theoretical assignments will be given, each worth 7% of the total mark.)
  • Midterm: 8%
  • Final: 50%


Corona virus: new evaluation


  • Assignments 1 through 5: 12% each. (Teams of two)
  • Midterm: 15%.
  • Assignment 6: 25%. (Individual work only.)


Prerequisites


Computer Science 250. Mathematics 240. Recommended background: Mathematics, discrete mathematics, arguments by induction. Restricted to Honours students in Mathematics and/or Computer Science.


Video lectures / Corona Virus


Video-taped B-movies featuring a bad actor. These videos together cover the last four lectures in COMP 252 this term. These lectures are the on-line lectures McGill University is asking us to give.

  • Compression part I. [869MB]
  • Compression part II. [993MB] .
  • Graphs: DFS. [266MB].
  • Graphs: BFS. [66MB]. 20 minutes.
  • Graphs: Shortest paths and MST. [209MB]. 63 minutes.


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.