Home | Bookmarks | Papers | Blog |

Time: Tuesday/Thursday 3:30-4:45. Location: Online.

The purpose of this course is to cover some more advanced algorithms than the ones covered by standard classes. There might be some overlap with CS 473 topics wise, but the main purpose is to cover some fun and interesting algorithms that are not usually covered in CS 473. Also, there would be no overlap with CS 374 (CS 473 has roughly 3 weeks/1 month of overlap in topics with CS 374). The course is intended for strong undergrads or graduate students. Taking CS 473 is not required before taking this class.

Topics may include:

- More interesting examples of divide and conquor
- FFT
- Sorting networks (maybe AKS).

- Some classical data-structures
- Fibonacci heap and alternatives
- Union-find (maybe even full analysis).
- LCA in a tree in constant time.
- Range trees/kd-trees
- How to make data-structures dynamic, some easy cases

- Some machine learning algorithms?
- Planar graphs, spearators, etc
- Some randomized algorithms
- Some streaming algorithms
- Shortest path in undirected graph with negative weights (joins, etc).
- Some distributed algorithms
- Some computational geometry algorithms:
- Closest pair in linear time
- Linear programming
- Clustering (local search)

Last modified: Wed 2020-11-11 17:33:44 UTC 2020 by Sariel Har-Peled