Teaching the Power of Randomization Using a Simple Game

摘要

Any deterministic algorithm can be viewed as a game between the algorithm player and the input player. A randomized algorithm can be viewed as a mixed strategy for the first player, used to minimize the disadvantage of being the first to reveal its move. We suggest a simple and accessible guessing game that can serve as both a way to explain notions in algorithms (like worst case input) to students and also to illustrate the power of randomization, presented in an intuitive way.