Randomized Network Algorithms
ENG SE 741
Probabilistic techniques and paradigms in the design and evaluation of network algorithms. Review of basic concepts in probability, graph theory, and algorithms. Tail inequalities and Chernoff bounds. Ball and bins and random graph models. Markov chains and random walks. The probabilistic method. Monte Carlo methods. Introduction to martingales, networking applications: distributed content storage and look-up in P2P networks, IP traceback, fountain codes, universal hash functions, packet routing. Same as EC 741. Students may not receive credit for both.