1. Probablistic algorithm | Randomized algorithm
- concentrated inequalities
- graph sparsification
- dimension reduction
- balls-and-bins, hashing
- sublinear algorithm
- algebraic
- parallel matching
- distributed algorithm(network coding)
- probabilistic methods
- local lemma
- random walks
- Markov chain
randomized algorithm is undetermaniztic algorithm, so it is weaker algorithm, but we have more freedom in solving problems.
2. Linear Algabra
- random walks
- graph particioning algorithm
- graph as an electrical network
- electical flow
- multiplicative update method
- max flow
3B CS