Computer Science COMP 251B
Data Structures and Algorithms

Winter 2011, Schedule: MW 16:00-17:30 MDHAR G-10

EXAM is OPEN BOOK -- ALL DOCUMENTATION PERMITTED

Instructor: Prof. Claude Crépeau
Office Hours: Thursday 12h30-15h30 McConnell Eng. Bldg. room 110N
Guest Lecturer: Dr. Simon Pierre Desrosiers

Send comments to crepeau@cs.mcgill.ca
avoid sending me HomeWork questions directly; uses links below for faster replies...

T.A.s: Giulia Alberini, Amjad Almahairi, Ladan Mahabadi, Athena Kardehi Moghaddam, Raphael Mannadiar

T.A.'s Office Hours:
Giulia, Tue 14:30 - 16:00, McConnell 235, resp. HW #1.
Amjad, Fri 10:00 - 11:30, Trottier 3110, resp. HW #4.
Ladan, Thu 9:30-11, McConnell 104, resp. HW #3.
Athena, Tue 11-12:30, McConnell 111, resp. HW #2.

FOR ALL CLASS MATTERS CONTACT cs251@cs.mcgill.ca or WebCT disucssion group

Follow this link to get ORIGINAL Course slides.

L E C T U R E S
Follow this link to get MY VERSION of the Course slides. Lecture 1. Course Outline. Book Sections 1.1 : Stable Matching Lecture 2. Book Sections 1.2 : 5 Representative Problems Book Sections 2.1, 2.2, 2.4 : Analysis of Algorithms Lecture 3. Book Sections 5.1, 5.2 : Recurrence Relations Useful links: Sorting Out Sorting (part 1), Sorting Out Sorting (part 2), Sorting Out Sorting (part 3). Lecture 4. Book Sections 5.4: Divide-and-Conquer algorithms AUDIO version (53Mb mp3). Lecture 5. Book Sections 5.4, 5.5 : Divide-and-Conquer algorithms AUDIO version (54Mb mp3). Lecture 6. Book Sections CLRS 4.3: Master Theorem AUDIO version (59Mb mp3). Lecture 7. Book Sections 3.1, 3.2, 3.4 : Introduction to graphs AUDIO version (67Mb mp3). Lecture 8. Book Sections 3.5, 3.6, 4.1 : Introduction to graphs + Greedy Algorithms AUDIO N/A Lecture 9. Book Sections 4.1, 4.2 : Greedy Algorithms AUDIO version (58Mb mp3). Lecture 10. Book Sections 4.3, 6.0, 6.1 : Greedy Algorithms; Dynamic Programming AUDIO version (58 Mb mp3). Lecture 11. Book Sections 6.8, 6.2 : Dynamic Programming AUDIO N/A Lecture 12. Book Sections 6.3, 6.5 : Dynamic Programming AUDIO version (58Mb mp3). Lecture 13. (Feb 16, 2011) In class MID-TERM EXAM	Follow this link to get MY VERSION of the Course slides. Lecture 14. Book Sections 7.1, 7.2 : Max Flow and Min Cut AUDIO version (61Mb mp3). Lecture 15. Book Section 7.3 : Max Flow and Min Cut AUDIO version (55Mb mp3). Lecture 16. Book Section 7.3,7.5,7.6,7.12 : Max Flow and Min Cut + Applications AUDIO version (56Mb mp3). Lecture 17. Book Section 7.12,7.7,7.8,7.10 : Max Flow Applications AUDIO version (62Mb mp3). Lecture 18 (Lecturer SPD). Book Chapter 4.5 : Minimum spanning tree AUDIO version (32Mb mp3). Lecture 19 (Lecturer SPD). Book Chapter 4.6 : Data Structure for Disjoint Sets AUDIO version (51Mb mp3). Lecture 20. Book Chapter 13 : Randomized Algorithms AUDIO version (58Mb mp3). Lecture 21. Book Chapter 13 : Randomized Algorithms + Hashing AUDIO version (53Mb mp3). Lecture 22. Book Chapter 13 : Hashing + Quantum Computing AUDIO version (55Mb mp3). Lecture 23. Quantum Computing + CLRS Book Chapter 8 : n log n lower bound on comparison sorting AUDIO version (56Mb mp3). Lecture 24. CLRS Book Chapter 8 : Sorting in O(n) time ! CLRS Book Chapter 13 : Red-Black Trees AUDIO version (53Mb mp3). Lecture 25. CLRS Book Chapter 13 : Red-Black Trees AUDIO version (59Mb mp3). Lecture 26. (Fri Apr 8, 2011) Review of course material AUDIO N/A

L E C T U R E S

Follow this link to get MY VERSION of the Course slides.

Lecture 1. Course Outline. Book Sections 1.1 : Stable Matching

Lecture 2. Book Sections 1.2 : 5 Representative Problems
Book Sections 2.1, 2.2, 2.4 : Analysis of Algorithms

Lecture 3. Book Sections 5.1, 5.2 : Recurrence Relations
Useful links:
Sorting Out Sorting (part 1), Sorting Out Sorting (part 2), Sorting Out Sorting (part 3).

Lecture 4. Book Sections 5.4: Divide-and-Conquer algorithms AUDIO version (53Mb mp3).

Lecture 5. Book Sections 5.4, 5.5 : Divide-and-Conquer algorithms AUDIO version (54Mb mp3).

Lecture 6. Book Sections CLRS 4.3: Master Theorem AUDIO version (59Mb mp3).

Lecture 7. Book Sections 3.1, 3.2, 3.4 : Introduction to graphs AUDIO version (67Mb mp3).

Lecture 8. Book Sections 3.5, 3.6, 4.1 : Introduction to graphs + Greedy Algorithms AUDIO N/A

Lecture 9. Book Sections 4.1, 4.2 : Greedy Algorithms AUDIO version (58Mb mp3).

Lecture 10. Book Sections 4.3, 6.0, 6.1 : Greedy Algorithms; Dynamic Programming AUDIO version (58 Mb mp3).

Lecture 11. Book Sections 6.8, 6.2 : Dynamic Programming AUDIO N/A

Lecture 12. Book Sections 6.3, 6.5 : Dynamic Programming AUDIO version (58Mb mp3).

Lecture 13. (Feb 16, 2011) In class MID-TERM EXAM

Follow this link to get MY VERSION of the Course slides.

Lecture 14. Book Sections 7.1, 7.2 : Max Flow and Min Cut AUDIO version (61Mb mp3).

Lecture 15. Book Section 7.3 : Max Flow and Min Cut AUDIO version (55Mb mp3).

Lecture 16. Book Section 7.3,7.5,7.6,7.12 : Max Flow and Min Cut + Applications AUDIO version (56Mb mp3).

Lecture 17. Book Section 7.12,7.7,7.8,7.10 : Max Flow Applications AUDIO version (62Mb mp3).

Lecture 18 (Lecturer SPD). Book Chapter 4.5 : Minimum spanning tree AUDIO version (32Mb mp3).

Lecture 19 (Lecturer SPD). Book Chapter 4.6 : Data Structure for Disjoint Sets AUDIO version (51Mb mp3).

Lecture 20. Book Chapter 13 : Randomized Algorithms AUDIO version (58Mb mp3).

Lecture 21. Book Chapter 13 : Randomized Algorithms + Hashing AUDIO version (53Mb mp3).

Lecture 22. Book Chapter 13 : Hashing + Quantum Computing AUDIO version (55Mb mp3).

Lecture 23. Quantum Computing + CLRS Book Chapter 8 : n log n lower bound on comparison sorting AUDIO version (56Mb mp3).

Lecture 24. CLRS Book Chapter 8 : Sorting in O(n) time !
CLRS Book Chapter 13 : Red-Black Trees AUDIO version (53Mb mp3).

Lecture 25. CLRS Book Chapter 13 : Red-Black Trees AUDIO version (59Mb mp3).

Lecture 26. (Fri Apr 8, 2011) Review of course material AUDIO N/A

Homework 1 ; TA in charge Giulia

solutions Homework 1 AVAILABLE 14 FEB 2011

Homework 2 ; TA in charge Athena

solutions Homework 2 AVAILABLE 13 APR 2011

Homework 3 TA in charge Ladan

solutions Homework 3 AVAILABLE 14 APR 2011

Homework 4 TA in charge Amjad

solutions Homework 4

WARNING : the course has changed quite a bit in 2011

PDF Format

FINAL EXAM 2011 (Apr 18, 2011)
PDF Format

FINAL EXAM 2010 (Apr 30, 2010)
PDF Format

FINAL EXAM 2008 (Mar 31, 2008)
PDF Format

FINAL EXAM 2005 (Mar 17, 2008)
PDF Format

Description: Design and analysis of algorithms. Complexity of algorithms. Data structures. Introduction to graph algorithms and their analysis.
(3 credits; 3 hours)
Prerequisites: either COMP 250 or COMP 203.
Schedule Types: Lecture, Final Exam, Midterm Exam, Optional Tutorial.
Restriction: Not open to students who have taken or are taking COMP 252.
Restrictions: May not be enrolled in one of the following Levels:
Doctorate
Masters & Grad Dips & Certs
May not be enrolled in one of the following Faculties:
Faculty of Medicine
Centre for Continuing Education
Faculty of Dentistry