# 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:

- 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)

## Topics for making presentation

- [Taken] van Emde Boas Trees (Chapter 20 in CLRS 3rd edition).
- [Taken] Making data-structures presistent (based on this
article
- [Taken] Locality sensitive hashing (start
here).
- Fine grained complexity (start here).
- Parameterized algorithms (chapter 1 and 2 from this
book.

Last modified: Tue 2021-03-30 21:48:14 UTC 2021 by Sariel Har-Peled