COMP610B Winter 2018 Lecture List

This is a list of lecture summaries for lectures which have already occurred and a list of provisional topics for future lectures. References and further details will be added as the term progreses. Lectures on April 4 and 16 are cancelled. To make up for this, the lectures on Mar 14,19,21,26, and 28 will begin at 8:00 AM.

Jan. 8: Course Overview, Reducing SAT to 3-SAT, Reducing 2-SAT to finding good orderings. Lecture Notes, Powerpoint.

Jan. 10: Solving 2-SAT using DFS(Related Material covered in Sections 22-3-22.5 of CLSR, Powerpoint).

Jan. 15: Probabilistic Analysis of Quicksort, Randomized Algorithms for Selection.(Sections 7.4.2, 9.1, and 9.2 of CLSR are relevant. The analysis is Section 9.2 is unneccesarily complicated, see the notes). Lecture Notes, Powerpoint.

Jan. 17: Upper and Lower Bounds for Selection Algorithms(The upper bound is treated in Section 9.3 of CLSR) Lecture Notes, Powerpoint.

Jan. 22 Max Flows and Min Cuts with Applications to Matchings in Bipartite Graphs and edge disjoint paths in directed graphs. (Lecture Notes, Chapter 7 of KT can be found in file called NetworkFlows in a folder call KT Chapter 7 on mycourses)

Jan 24: Formulating Maximum Flow Problems (Lecture Notes,Powerpoint)

Jan. 29 and 31: Heaps and Heapsort(Notes will be provided after the lectures. Chapter 6 of CLRS deals with the topic).

Feb. 5 and 7: Red-Black Trees(These lectures are based on Chapters 12 and 13 of CLSR)

Feb. 12 and 14: Solving Maximum Flow Problems(The February 12 lecture will be moved to a mutually sgreed time later in the week. Based on Section 7 of KT.)

Feb. 19: Finding 2-connected components using DFS(Notes will be provided after the lecture)

Feb. 21: Midterm Exam

Feb. 26 and 28: Planar Graphs and 2-DRP(Notes will be provided after the lecture).

March 12 and 14: The Travelling Salesman Problem. (These lectures are based on parts of Bill Cook's book on the topic. Further precision as to the specficic sections will be given after the lectures. Professor Cook will give the March 12th lecture. The March 14 lectures starts at 8:00AM)

March 19 and 21: Compression Algorithms (lectures start at 8:00 AM; References to be determined))

March 26 and 28: The Stable Set Problem(lectures start at 8:00 AM, References to be determined)

April 4: Lecture Cancelled

April 9 and 11: Tree Width(Notes will be given aftder the lecture)

April 16: Lecture Cancelled