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.

**Data Structures:**

- Heap, stacks, linked list,
- Hash tables,
- Binary search trees,
- Red black trees,
- B-trees,
- Data Structures for Disjoint Sets,
- Graphs,

- Sorting: Heapsort, quicksort.
- Searching: Algorithms on trees,
- Graph algorithms: Shortest paths...
- Polynoms and Fast Fourier Transform,
- Motif search,
- Computational geometry: Elementary algorithms,
- Introduction to Formal langage theory.

**Instructor:**
Jérôme Waldispühl

**Teaching Assistant:** Gheorghe Comanici.

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

**Office hours:**

- Jérôme Waldispühl: Tuesday and Thursday 4:30pm-5:30pm in Trottier 3106.
- Gheorghe Comanici:
**Monday April 26th 12:00pm-17:00pm in McConnell 111.**

If you have a question, comment or need to schedule an appointment,

email me at `<firstname>.<lastname>@mcgill.ca`.

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.

**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.

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.

- 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.

**Introduction to Algorithms**

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