Randomized Network Algorithms
ENG EC 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 SE 741. Students may not receive credit for both. 4 cr.