Computer Science 251
Data Structures and Algorithms
Last update: February 14, 2019

Winter 2019 --- Course Syllabus





New / Messages  


New (handwritten) notes on dictionaries posted.

Assignment 3 posted.

Midterm 1: the mark (out of 100)=mark on your exam sheet, plus 6.


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, until April 15. Office hours of Tuesday Feb 5 replaced by Monday Feb 4, 11:30am-1pm.


Auxiliary instructor  


Erin McLeish


Time and location


Duplicate lectures will be given every Tuesday and Thursday. There is a smaller room (Bronfman 422) for an 8:30-10am lecture, and a larger room (McMed 522) for a 1-2:30pm lecture.
The same lecturer will give both on the same day. Most lectures will be by Luc Devroye, and some by Erin McLeish.
January 8: First lecture
February 5: Midterm I.
March 4-8: Study break.
March 11: Midterm II. There are no lectures on March 12. The exam for both sections will be held from 6-8pm in Leacock 132.
April 11: Last lecture.
April 16: Final exam, 2-5pm.


Teaching assistants  



TA office and hours  


Trottier 3110.

  • Mo 4-5pm. (Konrad Anand)
  • Tu 4-5pm. (Anna Brandenberger)
  • We 4-5pm. (Gavin McCracken and Xoey Zhang)
  • Thu 4-6pm. (Ravi Chunduru)
  • Fri 9-10am. (Hang Li)
  • Fri 10-11:30am. (Shanqing Zhu and Ben Yu)

Trottier 3120.

  • Mo: 10:00-11:30am. (Konrad Anand and Gavin McCracken)
  • Tue: 2:30--4pm. (Auguste Lalande)
  • We: 10:00-11:30am. (Hang Li, Shanqing Zhu and Ben Yu)
  • Thu: 2:30--4pm. (Auguste Lalande)


The supplemental


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


Lectures (2019)


Material covered in each lecture in 2019


Assignments


Assignment 1 (Divide-and-conquer). January 10, 2019.
Solutions of Assignment 1 (Divide-and-conquer). January 21, 2019. Updated January 29, 2019.
Assignment 2 (Dynamic programming). January 22, 2019.
Solutions of Assignment 2 (Dynamic programming). January 31, 2019.
Solutions of Midterm1. February 5, 2019.
Assignment 3 (Trees). February 12, 2019.


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.
    • Dynamic programming.
    • 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


Evaluation


  • Assignments: 0% (Six theoretical assignments will be given. Please solve them alone or in study groups, and consult the TAs if necessary.)
  • Midterms: Two midterms will be given, each worth 15%.
  • Final: 70%


Prerequisites


Computer Science 250. Mathematics 240. Recommended background: Mathematics, discrete mathematics, arguments by induction.


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. There are several printings of the earlier editions of this book. These will do too. A list of errata of the second printing is available on-line. Excellent pirated copies of this book can be found via Google Search.

Finally, scribes in 2017, 2018 and 2019 made notes on the following topics: