Four non-deterministic programming exercises

In this article, we present four simple exercises that use non-determinism in the context of standard PASCAL-type programs. All four exercises are easy to grasp, and they all have short and nice solutions. Hence they might be appropriate for homework assignments and classroom exercises, and they might help students to digest the definition of a non-deterministic algorithm. Throughout, we will use an exclusive-or command (denoted OR): If in a piece of code we write stmnt-1 OR stmnt-2 then the non-deterministic program will execute exactly one of the two statements stmnt-1 and stmnt-2. Furthermore, we use a command MAYBE(stmnt) which allows the non-deterministic program to either execute statement stmnt or not. Obviously, MAYBE(stmnt) is equivalent to stmnt OR do_nothing.