ON THE IRREDUNDANT GENERATION OF KNOWLEDGE SPACES

Algorithms for the computer aided assessment of students' knowledge frequently operate on a structure called a knowledge space. The generation of a knowledge space often requires computing the closure of a family of subsets of a given set under union; unfortunately, however, the number of unions thus generated may grow exponentially with the number of subsets. It follows that algorithmic efficiency is of paramount importance. In this paper we present an algorithm based on specific members of a family of subsets of a finite set that eliminates redundant computation. thereby obtaining optimal efficiency. This algorithm is called the irredundant algorithm. The irredundant algorithm was applied to generating knowledge spaces from two different branches of knowledge, and to determining the size of these spaces. It is shown that the size of a knowledge space is an important characteristic of the structure of knowledge in a given area. For the same field of knowledge, in practice, we may obtain different knowledge spaces. It is shown that the irredundant algorithm can be used to intergrate different knowledge spaces into a common knowledge space. This procedure is illustrated with the example of two knowledge spaces on elementary reading and writing abilities. © 1993 Academic Press. All rights reserved.