DescriptionThe last couple of decades has witnessed a rapid growth of the role of randomization and probabilistic techniques in theoretical and practical computer science, with applications ranging from combinatorial optimization and machine learning to communication networks and secure protocols. In fact, the most efficient searching and indexing software are based on Markov chains, and every time your computer "talks" to the network your Ethernet card uses a randomized algorithm to decide on the time of the next connection attempt.A randomized or probabilistic algorithm is an algorithm that makes random choices during its execution. As opposed to deterministic algorithms (ie., algorithms with fixed order of execution), randomized algorithms are especially useful when faced with a malicious "adversary" or attacker who deliberately tries to feed a bad input to the algorithm. For example, consider the problem of locating a one in an array containing m ones and m zeroes. In the worst-case scenario, every deterministic algorithm needs m+1 operations, and for large m it would take a very long time. On the other hand, checking the elements of the array in a random order takes a random number of operations with small, uniformly bounded mean and variance, irrespective of the input string (can you do the maths?). It is a common feature of many randomized algorithms, that they are significantly more efficient than the best known deterministic algorithms. Quite often, the former are also simpler and easier to program (and analyze). The aim of the project is to explore some of the known randomized algorithms and show their efficiency. Prerequisites2H Probability is essential; 1H Discrete Maths and/or 3H Probability could be helpful.ResourcesThe book by M. Mitzenmacher and E. Upfal, Probability and Computing: Randomized Algorithms and Probabilistic Analysis discusses essentials of probability theory, motivated by applications to computer science.An introductory survey or a more advanced book by R.Motwani and P.Raghavan on Randomized Algorithms concentrate more on algorithmic applications. Further references might be suggested once the project is underway. |
email: Ostap Hryniv