Teaching Nondeterminism as a Special Case of Randomization
Ingo Wegener · 2007
Nondeterminism is a central concept in computer science. Every student of computer science is faced with this concept, since it is the basis of the NP-completeness theory and is applied in automata theory, formal languages, and many more areas. Students tend to have difficulties with the abstract concept of nondeterminism. Here a different approach to nondeterminism is proposed. Students should first learn the fundamental concept of randomization and randomized algorithms, since randomization has nowadays applications in all areas of computer science. Afterwards, nondeterminism can be easily introduced as a special case of randomization.