## COMP 150: Topics on Algorithms, Graphs and Data Structures

Details about the course

List of course topics

Project Information

### News

- 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)