COMP362B Winter 2014 Lecture List

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.