Computer Science 252
Algorithms and Data Structures
Last update: April 20, 2018

Winter 2018 --- Course Syllabus





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 19, and any time my door is open.


Time and location


Tuesday & Thursday, 8:30-10am, Trottier 1090.
January 9: First lecture
February 15: Midterm in Trottier 1090
March 5-9: Study break.
March 16: Extra lecture, 8:30-10am, Strathcona Dentistry 2-36.
March 23: Extra lecture, 8:30-10am, Strathcona Dentistry 2-36.
April 3: Lecture canceled.
April 5: Lecture canceled.
April 12: Last lecture.
April 27, 9-12am: Final, Otto Maass 10.


The supplemental


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

Teaching assistants

Tommy Reddad, McConnell Engineering 310. Email to Tommy Reddad.

Office hours: Monday, 10-12am. Wednesday 11am-1pm. Tommy will extend his office hours until the final exam.


Lectures (2018)


Material covered in each lecture in 2018
Material covered in each lecture in 2017 [This is for your information only. The pace, order and contents in 2018 may be different. In fact, some topics will be skipped altogether, and some new ones will be introduced.]


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%


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. There are several printings of the first edition of this book. All are equivalent. A list of errata of the second printing is available on-line. Excellent pirated copies of this book are navigating the web.

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


On-line resources


Class notes

  • (Outdated) class notes from 1997 compiled by students, listed below. Use at your own risk.