Lectureof Nov 26, 2013

Following is the outline for tomorrow's talk by Aanchal Malhotra and Ugur Kaynar:

Randomized Routing talk outline:
- Background: Basic definitions of computer networks, its topologies, routing in
a network, routing algorithm, etc.
-  Problem Definition: Permutation routing in hypercube
-  Deterministic Bit-Fixing routing algorithm with an example.
-  Worst case-analysis of the algorithm.

-  What is random routing algorithm?
- What is moment generating function?
- Chernoff bounds. Apply Chernoff bounds for Poisson trials.
- Compare chernoff bounds with other bounds that we learn (example question will
be solved.)

- Analysis of the randomized routing algorithm using Chernoff bounds.

Students are expected to go through the pages 60-67 for Chernoff bounds. And
pages 72-78 for routing in hypercube.