COMP 150: Topics on Algorithms, Graphs and Data Structures
Details about the course
List of course topics
- 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)