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 2016). References and further details will be added as the term progresses.
January 12 Lecture: Course Overview and an Introduction to (Integer) Linear Programming. I asked you to think about the following Exercises for Thursday.
January 14 Lecture: Modelling Problems using (Integer) Linear Programs.
January 19 Lecture: Reductions between 2-SAT and Finding Strongly Connected Components
January 21 Lecture: Solving Linear Programs via the Simplex Method I.. For those of you who have time and interest here is an article by a mathematician who thinks that mathematics is an art, and that the way it is being taught now is terribly wrong
January 26 Lecture: Solving Linear Programs via the Simplex Method II.. I asked you to think about the following Practice, Practice, Practice
January 28 Lecture: Exercises.
February 2 Lecture: We spent more time discussing exercises and showed how to reduce 3-SAT to 3-colourability modulo the creation of a special subgraph J. We will return to this topic.
February 4 Lecture: Duality
February 9 Lecture: P,NP, and NP-Completeness
February 11 Lecture: The proof of the Cook-Levin Theorem, details can be found in MyCourses.
February 16 Lecture: NP-Completeness II: Some NP-Complete Problems.. Note that we did not actually prove that Hamilton Cycle is NP-complete. We will do so if we have time later. For the moment we simply accept it is NP-complete.
February 18 Lecture: Strong NP-completenes,Pseudo-Polynomial time Algorithms, and An Introduction to Approximation Algorithms and Restricted Inputs.
February 23 Lecture: Cutting Stock I
February 25 Lecturer,: Cutting Stock II: We discussed the branch and cut algorithm for Multi-Knapsack presented in Chvatal. I mentioned a few other results on branch and cut. We had time to see the reduction from Vertex Cover to Hamilton Cycle from Cormen et al.
March 8: Midterm in Class(14:30-16), closed book, no electronic aids permitted.
March 10 Lecture: Some Probability Basics.
March 15: Lecture: A Polynomial Expected Time Algorithm For Graph Isomorphism. Sections 2 and 4 of this paper. may also be helpful.
March 17th Lecture: Graph Isomorphism on Trees.
March 22 and 24th Lecture: Isomorphism and Embedding of Planar Graphs
March 29: We introduced geometric algorithms and saw how to use the equation of the signed area of a triangle to determine whether a sequence of three points in the plane make a right-turn or a left-turn, or whether a point lies to the right or to the left of a directed line. We then introduced convex hulls, and saw two algorithms for computing the convex hull of a set of point in the plane. The first algorithm is called gift wrapping (or Jarvis's march), and can compute the convex hull in O(hn) time (where h is the number of points on the convex hull). We then saw the Graham scan algorithm for computing convex hulls in O(n log n) worst-case running time. Both these algorithms can be found in the textbook (Section 33.3 in CLRS 3rd ed.) We saw how to compute the tangent lines to a convex polygon from a given point in O(log n) time, and how to use this same idea to determine in O(log n) time whether a point lies inside or outside a convex polygon. Finally, we started discussing Chan's algorithm for computing convex hulls.
March 31 Lecture:We started the class by going over Chan's algorithm and then analyzing its running time of O(n log h). We then saw how to reduce sorting to the convex hull problem, as well as reducing the problem of element uniqueness to finding the closest pair of points in the plane. We introduced the problem of finding the closest pair of points in 2D in O(n log n) time (Section 33.4). Chan's paper on convex hulls can be found here: https://www.cs.ucsb.edu/~suri/cs235/ChanCH.pdf
April 5 Lecture: We completed the discussion on finding the closest pair of points using divide-and-conquer. We showed why merging two subproblems takes only linear time by relying on a result about packing points in a rectangle. We then moved to discussing greedy algorithms and saw Kruskal's algorithm: a greedy algorithm to find a minimum spanning tree of a weighted graph. We proved the correctness of Kruskal's algorithm. We introduced the disjoint-set (or union-find) data structure, showed that each of the union and find operations run in O(log n) time, and saw how union-find can be used to improve the running time of Kruskal's MST algorithm. Kruskal's algorithm is described in Sections 23.1 - 23.2 of CLRS, while Union-find is in Sections 21.1-21.3.
April 7 Lecture: We discussed an expected linear time algorithm for finding the closest pair of points using a randomized hashing technique. We also discussed a randomized approach to load-balancing. This is from the textbook of Kleinberg and Tardos, the relevant section will be loaded into MyCourses on Wed. April 13.
April 12th Lecture: We discussed fixed parameter tractability, specifically iterative compression. and its application to Cluster Vertex Deletion and Graph Bipartization. These are the first two examples which are discussd in the survey chapter which can be downloaded here: http://link.springer.com/chapter/10.1007%2F978-3-642-02094-0_4 Further details of the Graph Bipartization algorithm can be found here: www.math.mcgill.ca/vetta/Research.dir/foct.ps
April 14th Lecture: We will finish off load-balancing, I will give a brief review of the course and will leave some time for questions.