COMP 251: Data Structures and Algorithms
McGill University, Fall 2009
Announcements
Tentative final exam: Dec 17, 9 am. Click
here for the exam schedule.
Lectures: Tuesday and Thursday 10  11:30 in ENGTR 1100 ENGTR 2120.
Instructor:
Phuong Nguyen
Office: McConnell 309, phone: 514 398 7073,
email: pnguyen@cs.mcgill.ca.
For emails, please include in the subject ``COMP251''.
Office Hours: Tuesday and Thursday 45pm Tuesday 56 and Thursday 2:303:30 in McConnell 309.
Or make an appointment, or send a question via email.
Text:
Cormen, Leiserson, Rivest, Stein
Introduction to Algorithm (2nd edition) McGrawHill (2001), ISBN: 0070131511.
Available online at http://library.books24x7.com/ (with McGill ID). The book ID is 3444.
Evaluation:
 4 assignments worth 10% each, due at the beginning of lectures on September 17, October 1, October 29, and November 12.
 2 closedbook midterm tests (60 minutes each) worth 10% each, in lecture on October 6 and November 17.
 final exam (3 hours, closedbook) worth 40%. You must obtain at least 40% to pass the course.
Click here for the course information sheet (.pdf file).
Assignments
Assignment 1
Assignment 2
Assignment 3
some statistics
Assignment 4
some statistics
Tests
Test 1
Test 2
Practice exercises
Practice exercises
Additional notes and handouts
Outline of Proof of correctness for BFS
Strassen's algorithm for matrix multiplication
The counting sort algorithm
The quick sort algorithm
Exercises on proof by induction
Master Theorem
DFS algorithm using stack
Some properties of DFS
Some applications of DFS
(this does not include discussion about algorithm for strongly connected components and its correctness)
Algorithm for strongly connected components
Correctness of the algorithm for SCC
Lecture notes on redblack tree
Lectures
The references are from the 2nd edition of the textbook.
Lecture summary
Lecture 1 
(Ref: Chapters 1,2)
Introduction to COMP251, course outline, etc.
Some basic definitions (problems, algorithms, size of the instance)
A simple algorithm (finding max in a list) and its analysis (best case, worst case, average case).

Lecture 2 
(Ref: Chapters 2)
Finishing finding max analysis. Usual parameters used for analyzing algorithms
(e.g., when inputs are graphs or sequences of numbers)
Sorting problem, and the insertion sort algorithm. Brief proof of correctness and analysis. 
Lecture 3 
(Ref: Section 2.3.1 and Chapter 3)
Growth of functions, asymptotic notations.
Divideandconquer algorithms.
Merge sort. 
Lecture 4 
(Ref: Chapter 4, Chapter 7)
Analysis of Mergesort. Recurrence trees.
Quicksort algorithms and analysis. 
Lecture 5 
(Ref: Section 8.1)
Finish the analysis of Quicksort. Correctness of Quicksort.
Omega(nln n) lower bound for comparison sort: Define comparison sorts and decision tree model for comparison sorts.

Lecture 6 
(Ref: Sections 28.1, 28.2)
Complete the argument for Omega(nln n) lower bound for comparison sort.
Matrix and some basic operations on matrices and their properties.
An obvious algorithm for computing AxB in cubic time.
A straightforward divideandconquer algorithm that also runs in cubic time.

Lecture 7 
(Ref: Sections 28.1, 28.2, Chapter 6)
Strassen's algorithm for matrix multiplication and analysis.
Start on the Heap sort algorithm (Chapter 6).

Lecture 8 
(Ref: Sections 8.2)
Counting sort.

Lecture 9 
(Ref: Sections 8.3, 8.4) Radix sort and Bucket sort.

Lecture 10 
Analysis of Bucket sort. Start on data structures: Danymic sets and operations on dynamic sets (see Introduction to Part III, page 197 of the textbook). 
Test 1 
October 6, 2009. Covers materials upto (including) Counting sort. 
Lecture 11 
(Ref: Chapter 10)
Stack and Queue and their implementations. Applications of stacks and queues: recursive programs, graph searchs (more later).
Linked list, binary trees. An example of binary tree: mathematical expressions.

Lecture 12 
Datastructure for rooted trees (Section 10.4). Graphs: basic definitions and notations (see Appendex B.4), and graph searchs (Chapter 22).

Lecture 13 
(Ref: Section 22.2) Breadthfirst search algorithm and the proof of correctness. 
Lecture 14 
(Ref: Sections 22.2, 22.3) Finish the proof of correctness of BFS. Examples of BFS. Two implementations of DFS. 
Lecture 15 
(Ref: Section 22.3) DFS algorithm using stack. Parenthesis Theorem and its corollary. WhitePath Theorem. 
Lecture 16 
(Ref: Sections 22.4, 22.5)
Applications of DFS: Checking for acyclicity, topological sort, strongly connected components. 
Lecture 17 
(Ref: Section 22.5)
An algorithm for strongly connected component. 
Lecture 18 
(Ref: Sections 12.1, 12.2, 12.3)
Binary search tree: search, min, max, predecessor, successor, insert 
Lecture 19 
(Ref: Section 12.3) Deletion in BST.
(Ref: Chapter 13) Redblack trees: motivation and definition. Insertion for RedBlack trees.

Lecture 20 
(Ref: Chapter 13) Insertion procedure for Redblack trees.

Lecture 21 
Deletion in Redblack trees (Chapter 13).

Test 2 
November 17: include topics from Radix sort and Bucket sort to Redblack tree (insertion).

Lecture 22 
Hashing, resolving collisions by chaining and some analysis (Chapter 11) 
Lecture 23 
Continue on hash table: analysis of chaining, some hash functions (division method, multiplication method),
open addressing.

Lecture 24 
Open addressing: linear probing, quadratic probing, double hashing.
Perfect hashing. (Ref: Chapters 11.) Start reviewing.

Lecture 25  Review 
