Credits |
6 |

Lecturer |
Michael Kapralov |

Schedule |
Lectures: Mondays 14-16 in SG1 and Fridays 13-15 in CO1. Exercises: Mondays 16-18 with quiz in GRA330 (A to Ce), GCA331 (Ch to Gi), GRB330 (Go to Ma), GCB330 (Me to Sa), GCB331(Sc to Z). On Mondays without a quiz we only use GCA331, GCB330, and GCB331 assuming there is enough room. |

In this course you will get familiar with the theory and practice of basic concepts and techniques in algorithms. The course covers mathematical induction, techniques for analyzing algorithms, elementary data structures, the design of algorithms by induction, Sorting and searching, Merge sort, quicksort, heapsort, binary search, graph algorithms and data structures, graph traversals, shortest paths, spanning trees, matching, network flows, and elements of the theory of NP-completeness.

This is a course for second year students of both the systèmes de communication and informatique sections. The lectures will be in English, but you are free to choose the final exam in either of English or French. The exercises will be mainly in English but some may be in French.

For more details see the official couse book here.

- Mid-term exam: Monday 4 November
- Quizzes: The following Mondays: 30 September, 14 October, 28 October, 18 November, 2 December
- Final Exam: TBD

- September 20, September 23: Basic concepts and analysis + Insertion Sort. Sections 2.1, 2.2 + Review of Chapter 1,3 and Appendix A
- September 27, September 30: Divide-and-Conquer, Merge-sort, solving recurrences, maximum-sub-array problem. Sections 2.3, 4.1, 4.3-4.5
- October 4, 7: Strassen's algorithm for matrix multiplication, solving recurrences. Sections 4.2, 4.4, 4.5 + Review of Section 4.3
- October 11, 14: Heaps and Heapsort. Chapter 6
- October 18, 21: Datastructures: queues, linked lists, binary search trees. Sections 10.1, 10.2, 12.1, 12.2, 12.3
- October 25, 28: Dynamic programming: rod cutting matrix chain multiplication. Sections 15.1, 15.2
- November 1, November 4: More Dynamic Programming: formalization, longest common subsequence, optimal binary search trees. Sections 15.3, 15.4, 15.5
- November 8, November 11: Elementary graph algorithms: BFS, DFS, Sections 22.1, 22.2, 22.3 + Review of Appendix B
- November 18, November 22: Topological sort, flows. Sections 22.4, 26.1, beginning of 26.2
- November 25, November 29: Flows continued and bipartite matching. Sections 26.2 continued, 26.3
- December 2, December 6: Datastructure disjoint sets + minimum spanning trees. Sections 21.1, 21.2, 21.3, Chapter 23
- December 9, December 13: Bellman-Ford, probabilistic analysis. Sections 24.1, 5.1, 5.2
- December 16, December 20: Hash tables, Sections 11.1, 11.2, 8.1, 8.2 + Discussion of Quicksort

- Thomas Cormen, Charles Leiserson, Ronald Rivest, Clifford Stein: Introduction to algorithms, Third Edition, MIT Press, 2009.

A to Ce: GRA330

Ch to Gi: GCA331

Go to Ma: GRB330

Me to Sa: GCB330

Sc to Z: GCB331

On Mondays without a quiz, we only use GCA331, GCB330, and GCB331 assuming that there is sufficient room.

2012-2013, 2011-2012, 2010-2011, 2009-2010, 2007-2008, 2006-2007