This is a list of lecture summaries for lectures which have already occurred and a list of provisional topics for future lectures in COMP362B (Winter 2014). References and further details will be added as the term progresses.
January 6 Lecture: Course Overview and an Introduction to (Integer) Linear Programming. I asked you to think about the following Exercises for Thursday.
January 8 Lecture: Modelling Problems using (Integer) Linear Programs.
January 13 Lecture: Solving Linear Programs via The Simplex Method I
January 15 Lecture: Solving Linear Programs via The Simplex Method II
January 20 Lecture: Solving Linear Programs via The Simplex Method III
January 22 Lecture: Linear Programming Duality and an Introduction to 2-Trees
January 27 Lecture: More on Duality and 2-Trees.
January 29 Lecture: Dynamic Programming on Trees and 2-Trees.
February 3 Lecture: P,NP
February 5 Lecture: NP-completeness, Polynomial Reductions and Cook's Theorem
February 10 Lecture: NP-Completeness II: Some NP-Complete Problems.. Here are February 5 Lecture:some questions for next class
February 12 Lecture: Some More NP-Complete Problems:
February 17 Lecture: Strong NP-completenes,Pseudo-Polynomial time Algorithms, and An Introduction to Approximation Algorithms and Restricted Inputs.
February 19 Lecture: k-DRP on trees and 2-trees
February 24 Lecture: Introducing Tree Decompositions and Tree Width.See also these examples
February 26 Lecture: Building Bounded Width Decompositons
March 10: Midterm in Class(8:30-10), closed book, no electronic aids permitted.
March 12 Lecture: Dynamic Programming Using Bounded Width Decompositons. I also mentioned thzt some of you might want to attend a lecture at 16:00 next Monday the 17th. See the announcement, here
March 17,19,24,26 Lectures: k-DRP
March 31 and April 2 Lectures: Probabilistic Analysis of Algorithms
April 9 Lecture: Review and Perspectives.