Lectureof Nov 26, 2013 Following is the outline for tomorrow's talk by Aanchal Malhotra and Ugur Kaynar: Randomized Routing talk outline: Aanchal: - 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. Ugur: - 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.) Aanchal: - 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.