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
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.
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
Clustering (local search)
Last modified: Wed 2020-11-11 17:33:44 UTC 2020 by Sariel Har-Peled