Time and location

Tuesday, Thursday, 1011:30 am, January 7, 2014  April 10, 2014.
Room: Trottier 60.
Midterm: February 18, 2014, 1011:30am, Trottier 60.
Study break: March 37, 2014.
Extra lectures: Friday, March 14, 2014, 36pm, Trottier 1080.
Final exam: April 16, 2014, 912am, Trottier 1100.
Final: TBA
Moodle:
students log in with their CS username,
and the password is their McGill ID.
This secure site has PDF copies of some assignments
and some solutions.

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, mergefind 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.
 Worstcase and expected time complexity.
 Analysis of simple recursive and nonrecursive algorithms.
 Searching, merging and sorting.
 Amortized analysis.
 Lower bounds.
 Introductory notions of algorithm design:
 Divideandconquer. Recurrences. The master theorem. Quicksort. Other examples such as fast multiplication of polynomials and matrices. Fast Fourier transform.
 Dynamic programming. Examples such as BellmanFord network flow, sequence alignment, knapsack problems and Viterbi's algorithm.
 Greedy methods. This includes the minimal spanning tree algorithm and Huffman coding.
 Graph algorithms.
 Depthfirst search and breadthfirst search
 Shortest path problems
 Minimum spanning trees
 Directed acyclic graphs
 Network flows and possibly bipartitie matching

Textbook

T.H. Cormen, C.E.Leiserson, R.L.Rivest, and C. Stein:
"Introduction to Algorithms (Third Edition)", MIT Press, Cambridge, MA, 2009.
There are several printings of the first
edition of this book. All are equivalent.
A list of errata of the second printing
is available online.
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.
