Search Mailing List Archives
[theory-seminar] CS 369Z Fall 2021
monika.henzinger at univie.ac.at
Mon Aug 30 13:25:05 PDT 2021
I am a visiting professor at Stanford and will teach CS 369Z this fall
semester. Here is the announcement, please come if you are interested
in dynamic data structures.
CS 369Z: Dynamic data structures for graphs and point sets
Instructor: Monika Henzinger
Date: Tue/Th 9:45 – 11:15am
Location: Hewlett Teaching Center Rm. 103
With the increase of huge, dynamically changing data sets there is a
raisingneed for dynamic data structures to represent and process them.
This course will present the algorithmic techniques that have been
developed for dynamic data structures for graphs and for point sets.
1. Computational models:
* Adversarial models, average-case model, cell probe model, pointer
machine model, oracle model, conditional lower bounds
2. Fundamental data structures:
* Euler-Tour trees and Top Trees
* Epsilon-nets, cover trees, range-search data structures
3. Hierarchy-based dynamic graph algorithms:
* Connectivity and minimum spanning trees, approximate cardinality
matching, vertex coloring, shortest paths
4. Random-rank based dynamic graph algorithms:
* Maximal independent set, maximal matching, vertex coloring
5. Point Sets 1: Dynamic proximity search
* Different variants of approximate nearest neighbor
6. Point Sets 2: Dynamic clustering algorithms:
* Core sets, k-center, k-means, k-median, hierarchical clustering
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the theory-seminar