Syllabus

The design and analysis of data structures and algorithms. The description of various computational problems and the algorithms that can be used to solve them, along with their associated data structures. Proving the correctness of algorithms and determining their computational complexity.

Prerequisite: COMP 250 and MATH 240.

Restrictions: Open only to students registered in following programs: Honours in Computer Science, Joint Honours in Mathematics and Computer Science, Honours in Applied Mathematics, Honours in Mathematics. Not open to students who have taken or are taking COMP 251.

Note: COMP 252 can be used instead of COMP 251 to satisfy prerequisites.

Topics (non-exhaustive list)

Data Structures:

Algorithms: illustration

Binary tree


Course informations

Instructor: Jérôme Waldispühl
Teaching Assistant: Gheorghe Comanici.

Lectures: Tuesday-Thursday 2:35pm - 3:55pm in BURN 1B24.

Office hours:


Contact

If you have a question, comment or need to schedule an appointment,
email me at <firstname>.<lastname>@mcgill.ca.


Announces

First assignment delivered on Jan 14th.

Second assignment delivered on Jan 26th.

Second assignment delivered on Feb 9th (Due at Monday, Feb 15th).

Mid-term on Feb 18th.

Gheorghe Comacini will have office hours from 12pm to 17pm on Monday April 26th.


Schedule and Material

Lecture 0 (Jan. 5th, 2010):
General introduction. Simple Computer Models. Estimating the running time. Fibonnacci Example.

Lecture 1 (Jan. 7th, 2010):
Summation methods. Recursive techniques.

Lecture 2 (Jan. 12th, 2010):
Basic Data Structures: Stacks, Queues, Linked list, Linked list, Heap.

Lecture 3 (Jan. 14th, 2010):
Sorting I: Basic algorithms.

Lecture 4 (Jan. 19th, 2010):
Sorting II: Quicksort.

Lecture 5 (Jan. 21th, 2010):
Hashtables.

Lecture 6 (Jan. 26th, 2010):
Binary search trees.

Lecture 7 (Jan. 28th, 2010):
Discussion class.

Lecture 8 (Feb. 2nd, 2010):
Red-black trees.

Lecture 10 (Feb. 4th, 2010):
Dynamic programing.

Lecture 11 (Feb. 9th, 2010):
Greedy algorithms.

Lecture 12 (Feb. 11th, 2010):
Amortized analysis.

Lecture 13 (Feb. 16th, 2010):
B-trees.

Mid-term exam (Feb. 18th, 2010):

Lecture 14 (Mar. 2nd, 2010):
Data Structures for Disjoint Sets.

Lecture 15 (Mar. 4th, 2010):
Elementary graph algorithms.

Lecture 16 (Mar. 9th, 2010):
Graph algorithms: Shortest paths.

Lecture 17 (Mar. 11th, 2010):
Graph algorithms: Minimum spanning trees and maximum graph flow.

Lecture 18 (Mar. 16th, 2010):
Polynoms and Fast Fourier Transform.

Lecture 19 (Mar. 18th, 2010):
Number theory algorithms.

Lecture 20 (Mar. 23rd, 2010):
Motif search (Rabin-Karp, Knuth-Morris-Pratt, Boyer-Moore).

Lecture 21 (Mar. 25th, 2010):
Computational geometry: Elementary algorithms.

Lecture 22 (Mar. 30th, 2010):
NP-completeness: Definition and example and approximation Algorithms.

Lecture 23 (Apr. 1st, 2010):
Introduction to Formal Langage Theory.

Online Ressources

Notes from Winter 2009 by Alexandre Frechette.

Webpage of the previous Comp252 edition by Luc Devroye.
This outdated syllabus can be used as a reference. Variations may occur though.
An (Outdated) list of Luc Devroye's class notes (1997). Use at your own risk.


References

Introduction to Algorithms
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein

Book