COMP 251: Data Structures and Algorithms
McGill University, Fall 2009
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.
Office: McConnell 309, phone: 514 398 7073,
For emails, please include in the subject ``COMP251''.
Tuesday and Thursday 4--5pm Tuesday 5-6 and Thursday 2:30-3:30 in McConnell 309.
Or make an appointment, or send a question via email.
Cormen, Leiserson, Rivest, Stein
Introduction to Algorithm (2nd edition) McGraw-Hill (2001), ISBN: 0-07-013151-1.
Available online at http://library.books24x7.com/ (with McGill ID). The book ID is 3444.
Click here for the course information sheet (.pdf file).
- 4 assignments worth 10% each, due at the beginning of lectures on September 17, October 1, October 29, and November 12.
- 2 closed-book midterm tests (60 minutes each) worth 10% each, in lecture on October 6 and November 17.
- final exam (3 hours, closed-book) worth 40%. You must obtain at least 40% to pass the course.
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
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 red-black tree
The references are from the 2nd edition of the textbook.
||(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).
||(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.
||(Ref: Section 2.3.1 and Chapter 3)
Growth of functions, asymptotic notations.
||(Ref: Chapter 4, Chapter 7)
Analysis of Mergesort. Recurrence trees.
Quicksort algorithms and analysis.
||(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.
||(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 divide-and-conquer algorithm that also runs in cubic time.
||(Ref: Sections 28.1, 28.2, Chapter 6)
Strassen's algorithm for matrix multiplication and analysis.
Start on the Heap sort algorithm (Chapter 6).
||(Ref: Sections 8.2)
(Ref: Sections 8.3, 8.4) Radix sort and Bucket sort.
||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).
||October 6, 2009. Covers materials upto (including) Counting sort.
||(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.
Datastructure for rooted trees (Section 10.4). Graphs: basic definitions and notations (see Appendex B.4), and graph searchs (Chapter 22).
||(Ref: Section 22.2) Breadth-first search algorithm and the proof of correctness.
||(Ref: Sections 22.2, 22.3) Finish the proof of correctness of BFS. Examples of BFS. Two implementations of DFS.
||(Ref: Section 22.3) DFS algorithm using stack. Parenthesis Theorem and its corollary. White-Path Theorem.
||(Ref: Sections 22.4, 22.5)
Applications of DFS: Checking for acyclicity, topological sort, strongly connected components.
||(Ref: Section 22.5)
An algorithm for strongly connected component.
||(Ref: Sections 12.1, 12.2, 12.3)
Binary search tree: search, min, max, predecessor, successor, insert
||(Ref: Section 12.3) Deletion in BST.
(Ref: Chapter 13) Red-black trees: motivation and definition. Insertion for Red-Black trees.
||(Ref: Chapter 13) Insertion procedure for Red-black trees.
Deletion in Red-black trees (Chapter 13).
||November 17: include topics from Radix sort and Bucket sort to Red-black tree (insertion).
||Hashing, resolving collisions by chaining and some analysis (Chapter 11)
||Continue on hash table: analysis of chaining, some hash functions (division method, multiplication method),
Open addressing: linear probing, quadratic probing, double hashing.
Perfect hashing. (Ref: Chapters 11.) Start reviewing.