This is a list of lecture summaries for lectures which have already occurred and a list of provisional topics for future lectures in COMP610B (Winter 2016). References and further details will be added as the term progresses.
January 12 Lecture: Checking Out Student background
January 14 Lecture: Selection and Priority Queues: Algorithms This is Chapters 6 and 9 of the text, although we did not include the increase key function in our definition of a Priority Queue. I asked you to think about lower bounds on the number of comparisions needed to find the median or build a heap in the comparision tree model. I also asked you to think about how to speed up the algorithms for building heaps on average and in the worst case.
January 19 Lecture: Selection and Priority Queues: Lower Bounds (Includes McGill Student Work IMSW). Paper by Gonnet and Munro with Algorithm For Building Heaps Using Binomial Trees, Paper by McDiarmid and Reed giving fasted expected time algorithm for building heaps Paper given better lower bound on finding the median
January 21 Lecture: Solving Recurrence Relations
January 26 Lecture: More on Selection and Heap Building. Paper given better lower bound on finding the median
January 28 Lecture: 2-SAT and Finding Strongly Connected Components
February 2 Lecture: Finding 2-Connected Components
February 4 Lecture: Builidng 2-cut trees.
February 9 Lecture: Finding Isomorphisms for Trees and 3-connected Planar Graphs
February 11 Lecture:Work Group
February 16 Lecture: Isomorphisms and Embedding of Planar Graphs
February 18 Lectures: Max-Flow Min Cut Algorithms. We discussed the Algorithm for Max Cut on pages 374-380 of Chvatal. We saw it could be used to find the maximum number of vertex disjoint paths
February 23,25 Lectures: k-DRP. We discussed the k-DRP and an algorithm for 2-DRP. I emailed you notes for this.
March 8 Lecture: Midterm in Class(8:30-10), closed book, no electronic aids permitted.
March 10 Lecture: was cancelled.
March 15 and 17 Lecture: Finding and Using Bounded Width Tree Decompositions. We followed the approach taken in the Chapter: Algorithmic Aspects of Tree Widthby Reed in the Book Recent Advances in Algorithmic Combinatorics edited by Linhares-Sales and Reed. We covered pages 85-98 pf the book except for Section 4.2.2.You can access an electronic version of this book via the McGill Library.
March 22 and 24 Lectures: We discussed algorithms for k-DRP for Capacity 2 k-DRP. This material will not be examined.
March 29 Lecture was cancelled
March 31st Lecture: We introduced greedy algorithms and discussed the problems of activity selection. We also saw how the greedy strategy sometimes fails to produce an optimum solution through the discussion of the 0-1 knapsack problem (CLRS Sections 16.1 - 16.2). We then saw how Prim's algorithm aplies the greedy strategy to find a minimum spanning tree of a given graph (CLRS Section 23.2).
April 5 Lectures: We reintroduced greedy algorithms and revisited some examples showing why greedy often does not work (i.e. does not produce the optimum solution). We then defined the minimum spanning tree problem, and described Kruskal's greedy algorithm for finding minimum spanning trees of graphs. 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 started the class by discussing balanced search trees. We introduced the red-black tree and its properties, and showed that a red-black tree having n keys has height at most 2log(n+1). We discussed the tree modification operations -- "insert" and "delete", and saw in detail how insertion in a red-black tree works (CLRS Chapter 13).
April 12 Lecture: We discussd 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 14 Lecture: TBA.