Instructor: Prof. Claude Crépeau
Office Hours: Mondays 12:00-15:30 McConnell Eng. Bldg. room 110N
FOR ALL CLASS MATTERS CONTACT crepeau@cs.mcgill.ca

L E C T U R E S

Lecture 1. (5 Jan 2017) Course Outline. Grade School Algorithms Lecture 2. (10 Jan 2017) Book Sections 1.2 : five Representative Problems Book Sections 2.1 : Analysis of Algorithms Homework 1 OUT ; to be submitted via MyCourse Lecture 3. (12 Jan 2017) Book Sections 2.2, 2.4 : Analysis of Algorithms Lecture 4-5. (17-19 Jan 2017) Book Sections 5.1, 5.2 : Recurrence Relations Book Section 5.5-5.4: Divide-and-Conquer algorithms Book Section CLRS 4.3: Master Theorem Lecture 6. (26 Jan 2017) Book Section BB 7.5: Median & Selection Book EXTRACT Section BB 7.5: Median & Selection Homework 1 IN; Homework 2 OUT ; to be submitted via MyCourse Lecture 7-8. (31 Jan-2 Feb 2017) Book Sections 3.1, 3.2, 3.4, 3.5, 3.6 : Introduction to graphs Lecture 9-10. (7-9 Feb 2017) Book Sections 4.1, 4.4 : Greedy Algorithms - Shortest Distances Lecture 11. (10 Feb 2017) Book Sections 4.5 : Greedy - MST Lectures 12-13. (14-16 Feb 2017) Dynamic Programming Book Section 6.1, 6.8, 6.10, 6.3, 6.5, 6.6, 6.7 Homework 2 IN; Lectures 14-15. (21-23 Feb 2017) Max Flow and Min Cut Book Sections 7.1, 7.2, 7.3

Homework 3 OUT ; to be submitted via MyCourse Lectures 16-17. (07-09 Mar 2017) Max Flow and Min Cut Applications Book Section 7.5,7.6,7.12 Book Section 7.7,7.8,7.10 Homework 3 IN; to be submitted via MyCourse Homework 4 OUT ; to be submitted via MyCourse by 28 Mar 2017 23:59 Lectures 18-19. (14-16 Mar 2017) CLRS Book Chapter 12-13 : Red-Black Trees Lecture 20. (21 Mar 2017) CLRS Book Chapter 8 : n log n lower bound on comparison sorting CLRS Book Chapter 8 : Sorting in O(n) time ! Lecture 21. (23 Mar, 2017) Book Sections 4.6 : Union-Find data structure Homework 4 IN; to be submitted via MyCourse Homework 5 OUT ; to be submitted via MyCourse by 11 Apr 2017 23:59 Lectures 22-23-24.(March 28th-30th, April 4th, 2017) Randomized Algorithms + Hashing Book Sections 13.1, 13.2 : Book Sections 13.3, 13.5 : Book Sections 13.6, 13.99 + crypto : Lecture 25. (April 7th, 2017) CLRS Book Chapter 19 : Fibonacci Heaps. Lecture 26. (April 12th, 2017) COURSE REVIEW 2017 Homework 5 IN; to be submitted via MyCourse by 13 Mar 2017 23:59 BELOW THIS LINE : UPDATE REQUIRED WINTER 2017

---

---

Description: Study of elementary data structures: lists, stacks, queues, trees, hash tables, binary search trees, red-black trees, heaps. Augmenting data structures. Sorting and selection, Recursive algorithms. Advanced data structures including binomial heaps, Fibonacci heaps, disjoint set structures, and splay trees. Amortizing. String algorithms. Huffman trees and suffix trees. Graph algorithms. Design and analysis of algorithms. Complexity of algorithms. Data structures. Introduction to graph algorithms and their analysis.
(4 credits; 3 hours)
Schedule Types: Lecture, Final Exam.


---

Required Textbook:


Jon Kleinberg and Éva Tardos, Cornell University,

Algorithm Design
Addison-Wesley, 2006.
FREE ACCESS TO BOOK CHAPTER 1
FREE ACCESS TO BOOK CHAPTER 6
FREE ACCESS TO BOOK CHAPTER 13


---

Other Useful Books:



• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest,and Clifford Stein,
  
  Introduction to Algorithms, 3/e
  MIT Press, 2009.
  ONLINE ACCESS TO THE 3/e OF THE BOOK (from within McGill)
  

  ---

• Dasgupta, Papadimitriou and Vazirani
  
  Algorithms
  McGraw-Hill,2008, ISBN:9780073523408
  Preliminary version of the book
  Solutions to exercices...
  

  ---

• Michael T. Goodrich, Roberto Tamassia
  
  Data Structures and Algorithms in Java (6th Edition)
  John Wiley and Sons; ISBN: 9781118771334

  ---

• Gilles Brassard et Paul Bratley,
  
  Fundamentals of Algorithmics
  Prentice-Hall, 1996. ISBN: 9780133350685

  ---

Send comments/questions to crepeau@cs.mcgill.ca

05/12/2016