COMP 150: Topics on Algorithms, Graphs and Data Structures
Details about the course
List of course topics
- Thursday, Dec. 7: Convex hull of point set in 2D, using O(nlogh) time: Kirkpatrick-Seidel Ultimate algorithm, and Chan's algorithm. See my comp163 page, section 5, in particular 5.7.
- Tuesday, Dec. 5: Huffman codes. See section 26.
- Thursday, Nov. 30: Geometry of BSTs. See section 5.
- Tuesday, Nov. 28: Splay trees. See section 4
- October / November: online portion of course
- Thursday, Sep. 28: Spanners: Theta graphs and Chew's algorithm. (high level description). See sections 18, 19.
- Tuesday, Sep. 26: All-Pairs Shortest Paths. See section 10.
- Thursday, Sep. 21: weight-balanced trees and Scapegoat trees. See section 25.
- Tuesday, Sep. 19: Quake heaps (see section 1). After class it looked like the problem with N increasing in the Link step of Delete could be dealt with by having 2T in the potential function. This in turn would require 4B. To be revisited.
- Thursday, Sep. 14: binomial heaps (see section 1), and fractional cascading (somewhat rushed after all, the video in section 8 is probably more clear).
- Tuesday, Sep. 12: examples of the probabilistic method (coins, Ramsey lower bound, hypergraph coloring, independent set). See section 21.
- Thursday, Sep. 7: Ramsey numbers (section 20)