Proceedings of the workshop "Intelligent Educational Systems on the World Wide Web",
8th World Conference of the AIED Society, Kobe, Japan, 18-22 August 1997

ADIS - An Animated Data Structure Intelligent Tutoring System or Putting an Interactive Tutor on the WWW

Kai Warendorf, Colin Tan
Intelligent Systems Lab, School of Applied Science
Nanyang Technological University,
Blk N4 Nanyang Avenue #2a-36, Singapore 639798
Tel: (+65) 7996266, Fax: (+65) 7926559, Email:
wdorf@acm.org
Personal Homepage: http://isl.sas.ntu.ac.sg:8080/~wdorf
ADIS Homepage: http://isl.sas.ntu.ac.sg:8080/adis

Abstract: In today's Information Technology (IT) age, the traditional role of teachers and learners is being changed by multimedia courseware. Hypermedia offers much to learners in terms of providing an environment that engages the learner, allowing the construction of knowledge in a meaningful way. However, these packages lack intelligent tutors. Intelligent Multimedia Tutoring Systems (IMTS) can offer some solutions by providing students multimedia interface features with the added ability to monitor the student's performance and to provide guidance towards the correct solution using methods of constraint-based tutoring. The pre-requisites for the topology chosen were low cost, high efficiency, platform independence, and the ability to be used on the World Wide Web (WWW). ADIS was successfully implemented in Java and integrated with a Graphical User Interface (GUI) to interact with students. It contains a communication protocol and expert evaluation, which is based on generality and therefor allows expansion of the system without modifying the expert itself.

Introduction

The Animated Data Structure Intelligent Tutoring System (ADIS) is an intelligent tutoring system developed as a teaching aid for a course on Data Structures to enhance students' understanding of data structures such as linked-lists, stacks, queues, trees and graphs. ADIS has the capability to display data structures graphically on the computer screen as well as allowing graphical manipulation of the data structure created. There is a tutorial mode incorporating exercises, where students can learn basic algorithms (insertion, deletion etc.) of data structures visually.

The traditional role of teachers and learners connotes an active teacher/passive student relationship, usually with the teacher lecturing at the front of the class while students sit at desks in rows and listen, take notes, and occasionally ask questions. The knowledge obtained is then applied to practical exercises in a supervised laboratory session, generally of two hours duration. Students have to complete their project within the session, and may consult qualified tutors concerning the task.

With the maturing of the Information Technology (IT) age, multimedia courseware has increasingly emerged, especially in the last decade. It has been shown that multimedia helps to make education more attractive and hence more effective by providing higher levels of interactivity [Hoogeveen 1995]. In computer science education, the visualization and interactive animation of abstract data structures has a positive effect on learning algorithms and is regarded as attractive by students [Lawrence et al. 1994]. Multimedia user interfaces are also attractive because they allow various modes of interaction, which facilitate learning. High level multimedia courseware packages have become widely available, providing coaching in a wide range of topics, from phonics and drawing to mathematics and chemistry.

Although multimedia courseware greatly enhances interactivity in the learning environment as compared with the classical teacher-student relationship described above, they still lack intelligent features, i.e. they can guide the student through the course (and even provide hints), but they are not able to adapt to the student's ability to understand and learn. No monitoring of the student's progress is possible and no facilities to intervene when the student is on the wrong track exist.

The Intelligent Tutoring System

General Concept

ADIS is completely implemented in Java to allow platform-independent standalone usage or internet delivery, either of proprietary origin (i.e. conventional market Web Browsers such as Netscape Navigator or Microsoft Internet Explorer), or on one designed specifically for the ITS (Hypermedia browser [Verhoeven & Warendorf 1997]). The system consists of several core modules, which are relatively independent of each other to allow easy upgradability and portability to other teaching domains:

  1. Personalized Student Models, each of which will monitor the progress of one student.
  2. An Expert Model, which stores instructions for each exercise as well as the initial state (if any). This model also provides the template by which to compare student actions, to detect constraint violations made by the student.
  3. An Expert Tutor, which operates on the Student and Expert Models. It is responsible for the validation of each move by the student in an exercise (by means of pattern matching the corresponding steps from both models). The tutor uses the constraint based tutoring module as proposed by [Ohlsson 1992] and described in detail in [Warendorf and Tan 1997].
  4. The Graphical User Interface (GUI) Shell which serves as the bridge or HCI interpreter between students and the ITS [Warendorf 1997].

Figure 1: General Schematic Diagram of ADIS (Full-size)

Figure 1 gives a general schematic representation outline to the ITS. Currently every user has his own copy of the Expert and Student model. In the future development of ADIS there will be many student hosts (clients) but only one central expert (server). Each student still has his/her own Student model but all will use the same copy of the Expert model in the Expert's Knowledge Database. The Data Structure Modules available can be easily expanded by adding new microworlds to the system. The prerequisite for this is laid by defining a general communication protocol and implementing the tutor engine without any knowledge about the domain being taught.

Communication between the Expert and the GUI: The AtomicAction Class

Implementing an Intelligent Tutoring System as a Client/Server model encounters a severe problem concerning the response time to the student. Not only does the appropriate response to the student have to be computed, but the request has to be sent forward to the server and an answer awaited. Even though the current version has the client/server support not implemented, e.g. Remote Method Invocation (RMI), due lack of support of conventional browsers, its design is catered for this purpose. In order to achieve this, interaction between the different components, e.g. GUI, tutor and database must be kept to a minimum. The communication is based on single or atomic actions between the two sides. Each step by the user is reported to the expert as an AtomicAction and is evaluated as described below.

The datum of information transfer between the Expert and the GUI is the AtomicAction object. This object contains complete information about the action just performed by a student. The Expert will compare the AtomicAction object with its template, to determine if the student is on-track in the exercise. This object is also the unit of storage in the Expert and Student model databases. It is stored in the Expert model in the form of the initial state for each exercise, and in the Student model as the student's exercise history.

An AtomicAction object consists of two components:

  1. action: This variable conveys the type of action just executed by the student, e.g. adding a node to a linked list.
  2. bubble: This object contains the actual graphical information of the object, like the type (arrow, node, etc.) and its relation with other objects, e.g. in the above example the value of the node and the nodes it is connected to.

Each instance of an AtomicAction object either contains only an action component, or an action plus a corresponding Bubble object describing the action. AtomicAction objects are generated by the GUI whenever a student executes some action through the interface. A clone of this instance will be passed to the Expert for processing and any necessary storage in the Student model database.

Evaluation of the Expert: The EMAtomicAction Class

The Expert receives an AtomicAction object from the GUI as described in the section above. In order to keep the tutor general the AtomicAction received is not evaluated directly. If the AtomicAction were to be evaluated directly, the expert would have to have responses coded for the steps which can be executed by the user in each microworld meaning that adding new domains in the future would be a cumbersome process.

Instead the Expert employs an EMAtomicAction object, which extends from the AtomicAction class. This object inherits all the parent attributes, and introduces an extra variable called checkitem. The Expert Model stores the correct sequences to be executed by the student and uses checkitem to identify which constraint should be tested for each step in each exercise. In other words, this variable will determine which pattern will be matched from the Expert template to the student's action. If there is a match, then the student performed the correct action and the Expert should take no action. Conversely, if there is a mismatch, then that particular constraint has been violated and appropriate remedial action can be taken. Figure 2 shows how an action executed by a student progresses through the ITS system and the various branches and results that can be obtained.

As already mentioned before the expert does not know the detailed implementation of the microworlds. He can only cater to specific actions like changing between microworlds and exercises. Even in this case he just loads another part of the database, which contains the exercises with their corresponding constraints. If the EMAtomicAction finds a constrained violation, it is reported to the expert and an appropriate response is passed to the GUI for display to the student. This includes tutorial help as well as resetting the exercise to the last correct step in case of an unrecoverable error.

Information Passing

Figure 2: Information Passing Mechanism (Full-size).

An Implemented Example

In order to demonstrate the responses from the ITS, an delete exercise from the linked list module will be used. Before going into the practical session, the theoretical solution will be described to provide a reference for the test run. Assume there are 5 nodes in a linked list connected together (singly linked list). If the second node had to be deleted, one of the correct sequence of actions might be as follows:

For this example, consider that a student is tasked to delete the second node (node 2) from the given linked list. The correct sequence of actions would be as follows:

  1. Create a TEMP pointer
  2. Assign the TEMP pointer to the third node of the list
  3. Delete or "free" the second node
  4. Join the segments to form new list by assigning the first node to the element segment currently pointed to by the TEMP pointer, the third node in this case.
  5. Removing the TEMP pointer

This is not a unique solution to the problem. For example, step b. could be assigning a TEMP pointer to the second node, step c. assigning node 1 to node 3 and finally step d. removing node 2. For demonstration, only the first sequence of actions will be considered correct.

Incorrect Sequence

In the exercise discussed above, the student always executed the correct action. This means that the Expert always found a match in its template for each step, and thus the tutor never activated to provide any pedagogical instruction besides displaying encouragement and storing the action information in the Student model. This is ideal, but will not be the norm, especially considering that the students targeted to use ADIS would be relatively new to data structures.

Error 1: Deleting the second node

If the student omits steps b. and c. and deletes node 2 immediately, the tail of the linked list will be lost (Figure 3), as indicated by red nodes moving towards the garbage bin. It is immediately clear at this point what error the student has made and the exercise can be reset with useful hints given, so that the student is allowed to discover that a TEMP pointer is needed to keep the tail.

Figure 3: Response of the tutor when deleting the second node (value -41) directly (Full-size).

When the constraint of removing a node from the middle of a linked list (node 2) without first creating a TEMP pointer to hold the remainder of the list is violated, then the tail of the linked list (node 3) will be irrecoverably lost and the resulting structure will become incorrect. Any further monitoring by the expert would therefore be unnecessary, as further student inputs would not be coherent based on this incomplete linked list. The expert can immediately provide instruction to the student regarding the violated constraint, without any further action or information from the student.

Error 2: Assigning TEMP to the wrong node

Assume the student proceeds to do the correct action of adding a TEMP pointer. Then the student connects the TEMP pointer to the second node (value -85). A constraint is violated as the exercise requires the TEMP pointer to be connected to the third node. Any further monitoring by the expert would therefore be unnecessary, as further student inputs would not be coherent based on this linked list. The expert can immediately provide instruction to the student regarding the violated constraint, without any further action or information from the student. The Expert will respond with the appropriate tutoring message and will also retract the incorrect move made by the student (see Figure 4).

Figure 4: Response of the tutor when assigning the TEMP pointer to the wrong node (Full-size).

The wrong actions by the student will be stored in the Student model. This caters for cases of abnormal aborts by students or server/client system anomalies resulting in shutdown. After system recovery, the student does not need to redo all the actions as they will be recalled from the Student model. If the last action was wrong, then the tutor would also be invoked. Further the Expert will adjust the tutoring level for that particular step in the Student model.

Conclusions

Even though only a representative shell exists currently, the implemented example discussed in the previous chapter clearly demonstrates the potential of ADIS. The constraint-based modeling technique has been successfully implemented in an ITS for a course on Data Structures. With the framework for Linked Lists, Stacks and Queues, addition of other modules is trivial since the communication protocol and the expert evaluation is based on generality. This means whenever a new microworld is added to the system there is no need to rewrite the expert for the new module. Since the comparison of expected and received response is done with the EMAtomicAction class, modifications only need to be done to cater for the special requirements of the new microworld. After implementing a database for exercises, their constraints and pedagogical responses as well as a new GUI, the system can be integrated and used with the constrained based tutor.

Acknowledgments

Special thanks to Tay Yong Seng, Tan Hua Min, and Tan Tai Heng for their support in developing the GUI components that this project utilizes to interact with the external world.

References

Hoogeveen, M. (1995): "Towards a New Multimedia Paradigm: Is Multimedia Assisted Instruction Really Effective ?". Proceedings of Educational Hypertext and Hypermedia, (pp. 348-353). Graz.

Lawrence, A. W., Badre, A., and Stasko, J. (1994): "Empirically Evaluating the Use of Animations to Teach Algorithms". Technical Report of the Graphics Visualization and Usability Centre, 94-07. Atlanta, Georgia: Institute of Technology.

Ohlsson, S. (1992): "Constraint-Based Student Modeling". Journal of Artificial Intelligence in Education 3(4), pp. 429-447.

Verhoeven, A., and Warendorf, K. (1997): "Design Issues for a Hypermedia Lab Support ITS". Proceedings of PACES/SPICS 97, Singapore, pp. 567-574.

Kai Warendorf, Colin Tan: Constrained-Based Student Modeling for an Intelligent Tutoring System on Data Structures, to appear in Proceedings of ICICS 97 (9-12 September 1997), Singapore.

Kai Warendorf: ADIS - An Animated Data Structure Intelligent Tutoring System on the WWW, to appear in Proceedings of ICICS 97 (9-12 September 1997), Singapore.