Four non-deterministic programming exercises

G.J. Woeginger

Research output: Contribution to journalArticleProfessional

Abstract

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.
Original languageEnglish
Pages (from-to)207-211
JournalBulletin of the European Association for Theoretical Computer Science, EATCS
Volume94
Publication statusPublished - 2008

Fingerprint

Dive into the research topics of 'Four non-deterministic programming exercises'. Together they form a unique fingerprint.

Cite this