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

Details about the course

List of course topics

Project Information

### News

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