[theory-seminar] CS 369Z Fall 2021

[Monika Henzinger]

Hi all,
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.

Best regards,
Monika

CS 369Z: Dynamic data structures for graphs and point sets

Instructor: Monika Henzinger

Fall 2021

Date: Tue/Th 9:45 – 11:15am

Location: Hewlett Teaching Center Rm. 103

Grading: Pass/Fail

Description:

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.

Syllabus:

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...
URL: <http://mailman.stanford.edu/pipermail/theory-seminar/attachments/20210830/ad867bda/attachment-0001.html>