Teaching Students to Think Nondeterministically

This paper focuses on the concept of nondeterminism in computer science (CS). Nondeterminism is already acknowledged in the literature as a CS fundamental idea. It is relevant to many CS areas such as operating systems, concurrent and distributed computation, and computational models.

In a previous work [1] we examined the concept of nondeterminism from an historical perspective, based on a multidimensional taxonomy we defined. We showed a strong connection between nondeterminism and abstraction, an important CS idea. We also argued that despite the abstract nature of nondeterminism, which makes it a challenging concept for students, and even because of this abstract nature, nondeterminism should be taught on a high level of abstraction, encouraging students to think of nondeterministic entities as truly nondeterministic, that is, as unpredictable and inconsistent. Such a level of introduction and discussion can help to develop students’ abstraction skills on the one hand, and to help them appreciate an important CS idea in a complete manner, on the other.

The study described in this paper focuses on the manner CS college students think of nondeterminism. In the first phase of the study we used qualitative methods, interviewing CS college students that had studied a course on automata and formal languages. We saw that these students thought of a nondeterministic automaton as a consistent entity that always gives the same answer for the same input, an answer which is based on an examination of all possible computation paths.

The findings of the first phase were not consistent with the actual teaching process, which presented to these students nondeterministic automata as theoretical, inconsistent entities.

We explained these findings within the framework of constructivism. We hypothesized that a teaching process that does not offer students opportunities to interpret nondeterminism within familiar contexts may result in different images of nondeterminism.

We designed an intervention and examined its effect. The research setting included a treatment group and a control group of CS students from two colleges, taking a course on automata and formal languages. The two groups shared similar characteristics and similar prior exposure to the concept of nondeterminism, as supported by the findings of a questionnaire given to both groups at the beginning of the semester. Both groups filled in another questionnaire at the end of the semester, aimed at establishing students’ image of nondeterministic entities. Interviews were conducted with students from the treatment group at the end of the semester.

The findings indicate a change in students’ perception. None of the interviewed treatment group students thought of nondeterministic automata as machines that run through all possible paths, and most of these students thought of nondeterministic automata as inconsistent entities. In an analysis of the second questionnaire, we saw that the control group demonstrated an image of nondeterministic automata as consistent, predictable machines. In the treatment group we saw a shift towards the image of nondeterministic automata as unpredictable, inconsistent machines. However, this shift resulted also in students who had a mixed, inconsistent image (thinking of nondeterministic automata as both consistent and inconsistent). 

Since the intervention was minimal, we view our findings as encouraging and we believe they are indicating that using appropriate teaching strategies, nondeterministic automata can be taught and perceived on a high level of abstraction. Future studies can examine variations of our strategy, such as confronting students explicitly with the unpredictability and inconsistency of nondeterministic automata.

[1] Armoni. M. and Ben-Ari, M. (2008). The concept of nondeterminism: Its development and implications for teaching. Science and Education. Available online on springerlink at http://www.springerlink.com/content/90584930180756l1/.

Author 1: Michal Armoni; Michal.Armoni@weizmann.ac.il
Author 2: Noa Lewenstein; Noa@netanya.ac.il
Author 3: Mordechai Ben-Ari; Moti.Ben-Ari@weizmann.ac.il

: Back to 2009 Winter Issue, Vol. 4, No. 2

: Back to List of Issues

: Back to Table of Contents

Created on 03 Apr 2015, Last modified on 03 Apr 2015