Introducing nondeterminism.(computational models)

Nondeterminism is an essential concept in mathematics and one of the important concepts in computer science. It is also among the most abstract ones. Thus, many students find it difficult to cope with. In this article, we describe some didactic considerations, which guided the development of a "Computational Models" course for high school students, a course in which the concept of nondeterminism is introduced. Some of these considerations are relevant to college and university students as well. We also discuss students' perceptions of nondeterminism and their achievements in this area. Our findings show that many students prefer to avoid nondeterminism, even when it can significantly simplify the solution's design process. We analyze and categorize the students' solutions, thus shedding light on their perceptions of the abstract concept of nondeterminism.

**********

Nondeterminism is an essential concept in computer science as well as in mathematics. In a typical bachelor CS program, the concept is introduced in the computational models course, and is often discussed again later in an artificial intelligence course. Sometimes it is also discussed in the context of operating systems and distributed algorithms. In a traditional high school program, the concept is rarely included. A high school student may, in a sense, be exposed to the concept when studying probability theory. In that context, nondeterminism is forced by the random nature of events.

In the CS high school curriculum described by Gal-Ezer, Beeri, Harel and Yehudai (1995; Gal-Ezer & Harel, 1999) the concept of nondeterminism is introduced in the Computational Models (CM) unit. The CM unit motivates the need for nondeterministic computational models, and encourages students to choose them, even when deterministic models are sufficient, by demonstrating their advantages.

This unit is unique, compared to other units in this curriculum, and to the best of our knowledge is also unique compared to other high school curricula in other countries. For example, the ACM high school computer science curriculum (Merritt, 1994) includes very few references to few of the topics of the CM unit, only as optional topics, and the more recent ACM K-12 computer science curriculum (Tucker, Deek, Jones, McCowan, Sthepenson, & Verno, 2003) mentions only limits of computability, in one of its five units, as one topic among 10.

In this article we describe the introduction of nondeterminism in the CM unit, and the didactic considerations that guided it, some of which can be applied on college and university levels as well. We also describe the results of a study we conducted on the perception of nondeterminism (partial information on this study was given in Armoni & Gal-Ezer, 2003). This study was part of a wider study, which examined various aspects of the teaching and learning process of the CM unit, such as students' achievements (Armoni & Gal-Ezer, 2004), teaching reductive thinking (Armoni & Gal-Ezer, 2005), and the tendency of students to choose reductive solutions (Armoni, Gal-Ezer, & Tirosh, 2005). The aspect of nondeterminism studied here focuses on the level of use of nondeterminism by students when they have freedom of choice, from which we can deduce their perceptions of this concept.

This article is organized as follows: in the second section " Computational Models in a High School CS Curriculum" we give a brief description of the CM unit; the third section "The Introduction of Nondeterminism" describes the way nondeterminism is introduced; the fourth section "The Study" describes the findings of our study regarding the perception of nondeterminism. Our conclusions and suggestions for further research are discussed in the fifth and last section.