Computer Science 252
Algorithms and Data Structures
Last update: February 1, 2017
Winter 2017 --- Course Syllabus
Luc Devroye |
Email to firstname.lastname@example.org |
Tel: (514) 398-3738 (office) |
McConnell Engineering Building, Room 300N |
Office hours: Tuesday, 10-11:30am, Wednesday, 11:30am-1pm, until April 11,
and any time my door is open.
Extra office hours from 10-11:30 on April 18, 20 and 21.
Time and location
Tuesday & Thursday, 8:30-10am, Trottier 1090.
January 5: First lecture
February 16: Midterm in Trottier 1090
February 27-March 3: Study break
March 17: Extra lecture in Trottier 1080, 8:30-10am
March 17: Extra lecture (repeated) in my office, 10-11:30am
March 24: Extra lecture in Rutherford Physics 114, 9:30-11am
April 4: Lecture canceled.
April 6: Lecture canceled.
April 11: Last lecture
April 24: Final exam, 9-12am, Otto Maas Chemistry 10.
Email to Tommy Reddad.
Office hours: Monday 10:45-12:15 and Wednesday 12:15-13:45.
Office: McConnell 310.
Material covered in each lecture in 2017
Material covered in each lecture in 2016
[This is for your information only. The pace, order and contents in 2017
may be different.
In fact, some topics
will be skipped altogether, and at least two new ones will be
- Introduce the student to algorithmic analysis.
- Introduce the student to the fundamental data structures.
- Introduce the student to problem solving paradigms.
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.
- Trees. Traversal. Implementations. Binary trees.
- Indexing methods. Hashing.
- Introduction to abstract data types such as mathematical set,
priority queue, merge-find set and dictionary.
- 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
- Assignments: 42% (Six theoretical assignments will be given,
each worth 7% of the total mark.)
- Midterm: 8%
- Final: 50%
Computer Science 250. Mathematics 240.
Recommended background: Mathematics, discrete mathematics, arguments by induction.
Restricted to Honours students in Mathematics and/or Computer Science.
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.
(Outdated) class notes from 1997 compiled by students, listed below. Use at your own risk.
Assignment 1 (Jan 18, 2000)
Assignment 2 (Feb 8, 2000)
Solution of assignment 2
Assignment 3 (Mar 14, 2000)
Solution of assignment 3
Assignment 4 (Mar 21, 2000)
Solution of assignment 4
Tutorial 2 (Feb 1, 2000)
Tutorial 4 (Mar 7, 2000)
Midterm 1992: PostScript
Midterm 1996: PostScript
Midterm 1997: PostScript; PDF
Midterm 1999: PostScript; PDF
First midterm 2000: HTML
Second midterm 2000: HTML
Finals pre-1996: PostScript
Final 1996: PostScript
Final 1997: PostScript; PDF
Final 1997 answers: ascii text
Final 1999: HTML
Final 2000: HTML
Practice questions set 1
Practice questions set 1: answers
Practice questions set 2
Practice questions set 2: answers
Practice questions set 3
Practice questions set 3: answers
Practice questions set 4
Practice questions set 4: answers
Practice questions set 5
Practice questions set 5: answers