498 Topics in Algorithms

Spring 2021

Time: Tuesday/Thursday 3:30-4:45. Location: Online.
Zoom link: here (email me if you can not access).
HW: 1, 2 .
Campus wire
Lectures : Class transcribe : Mediaspace
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:

  1. More interesting examples of divide and conquor
    1. FFT
    2. Sorting networks (maybe AKS).
  2. Some classical data-structures
    1. Fibonacci heap and alternatives
    2. Union-find (maybe even full analysis).
    3. LCA in a tree in constant time.
    4. Range trees/kd-trees
    5. How to make data-structures dynamic, some easy cases
  3. Some machine learning algorithms?
  4. Planar graphs, spearators, etc
  5. Some randomized algorithms
  6. Some streaming algorithms
  7. Shortest path in undirected graph with negative weights (joins, etc).
  8. Some distributed algorithms
  9. Some computational geometry algorithms:

Topics for making presentation

  1. [Taken] van Emde Boas Trees (Chapter 20 in CLRS 3rd edition).
  2. [Taken] Making data-structures presistent (based on this article
  3. [Taken] Locality sensitive hashing (start here).
  4. Fine grained complexity (start here).
  5. Parameterized algorithms (chapter 1 and 2 from this book.
Last modified: Tue 2021-03-30 21:48:14 UTC 2021 by Sariel Har-Peled