Computer Science 308-252B Algorithms and Data Structures Last update: December 20, 2011 Winter 2011 --- Course Syllabus
Instructor	Luc Devroye | Email to lucdevroye@gmail.com | Tel: (514) 398-3738 (office) | McConnell Engineering Building, Room 300N | Office hours: Tuesday and Thursday, 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, 8:30-10:00 am, January 4, 2011 --- April 7, 2011. Room: McConnell 103. Gheorghe's pre-final office hours: Wednesday, April 6: 9-10. Friday, April 8: 11:30-13:30. Monday, April 11: 11:30-2:30. Final: April 12, 2011, 2-5pm, RPHYS 114. New: Moodle: students log in with their CS username, and the password is their McGill ID. This site has PDF copies of the assignments and solutions (which I do not want to post on my regular web site).
Teaching assistant	Gheorghe Comanici. Email to gheorghe.comanici@mail.mcgill.ca. Office hours: Monday 11:30am-1:30pm, Wednesday 9-10am. Office: McConnell 111
Lectures (2011)	Material covered in each lecture in 2011. For reference only: Material covered in each lecture in 2009, if you want to see what is coming. However, the pace and order may be different. in fact, some topics will be skipped altogether, and at least two 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 possibly bipartitie matching
Evaluation	Assignments: 42% (Six theoretical assignments will be given, each worth 7% of the total mark.) Note: As announced in class, the worst of the four assignments will be dropped. That 7% "void" will be filled by the maximum of two things: (1) The average in your other five assignments, (2) The prorated score on your final. 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. 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. 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.
On-line resources	Class notes (Outdated) class notes from 1997 compiled by students, also listed below. Use at your own risk. Abstract data types. Models of computation. Complexity. Analysis: O, THETA, OMEGA. Summations. Recursion and recurrences. Linear time selection. Stacks, queues and lists. Suffix trees. Introduction to trees. Binary search trees. Random binary search trees and quicksort. Game trees. Alpha-beta search. Hashing by chaining. Hashing by open addressing. Hashing: overview and applications. Priority queues: overview and applications. Standard heaps. Discrete event simulation. Red-black trees. Balanced search trees: overview. Augmented data structures. Coding and compression. Huffman trees. Lempel-Ziv compression. Disjoint set structures. Graphs: introduction. Graphs: depth-first search. Graphs: breadth-first search. Minimal spanning trees. Shortest path algorithms. Directed acyclic graphs. Lower bounds. Notes for Winter 2009 (PDF file) compiled by Alexandre Fréchette. Old Assignments 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 Old Tutorials Tutorial 2 (Feb 1, 2000) Tutorial 4 (Mar 7, 2000) Old Midterms Midterm 1992: PostScript Midterm 1996: PostScript Midterm 1997: PostScript; PDF Midterm 1999: PostScript; PDF First midterm 2000: HTML Second midterm 2000: HTML Old Finals Finals pre-1996: PostScript Final 1996: PostScript Final 1997: PostScript; PDF Final 1997 answers: ascii text Final 1999: HTML Final 2000: HTML Practice questions 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