# 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 4--5pm Tuesday 5-6 and Thursday 2:30-3:30 in McConnell 309. Or make an appointment, or send a question via email.

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

Evaluation:

• 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.
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 red-black 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. Divide-and-conquer 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 divide-and-conquer 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) Breadth-first 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. White-Path 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) Red-black trees: motivation and definition. Insertion for Red-Black trees. Lecture 20 (Ref: Chapter 13) Insertion procedure for Red-black trees. Lecture 21 Deletion in Red-black trees (Chapter 13). Test 2 November 17: include topics from Radix sort and Bucket sort to Red-black 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