Luc Devroye |
Email to firstname.lastname@example.org |
Tel: (514) 398-3738 (office) |
McConnell Engineering Building, Room 300N |
Office hours: Tuesday, 13:00-14:00pm, Wednesday, 10-11:30am,
and any time my door is open.
You don't work for me---I work for you.
Time and location
Tuesday, Thursday, 11:30-13:00, January 6, 2015 --- April 2, 2015.
Room: Trottier 70.
Midterm: February 17, 2015, 11:30-13:00am, Trottier 70.
Study break: March 2-6, 2015.
Extra lecture: Friday, February 27, 2015, 11:30am-1pm, Leacock 14.
Extra lecture: Friday, March 27, 2015, 11:30am-1pm, Trottier 2120.
These lectures replace those of April 7 and 9.
Final: April 27, 2-5pm, SADB 1/12.
Assignment 6 can be picked up Monday April 20 and Tuesday April 21 from 11-12am in my office. Later pick-ups can be arranged by email.
If you just want to know your grade, email me.
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
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.