ADIS - An Animated Data Structure
Intelligent Tutoring System on the WWW
Kai Warendorf
Intelligent Systems Lab, School of Applied Science
Nanyang Technological University, Blk N4 Nanyang Avenue #2a-36
Singapore 639798


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 inquiry teaching.

Current ITS suffer from expensive Artificial Intelligence (AI) inference engines, the inability for the expert to learn and handle radical strategy variability, and large empirical search spaces. Although a myriad of ITS exists, no one single topology provides a perfect solution.

The main objective of this project was to provide an optimal solution to implementing an ITS component for the Hypermedia IMTS, to coach in the domain of Data structures. 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 and integrated with a Graphical User Interface (GUI) to interact with students. The current framework contains the Linked list, Stack, and Queue microworlds.

1 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. This system will eventually be used 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 where students can learn basic algorithms (insertion, deletion etc.) of data structures visually. There are exercises for these basic algorithms and the performance of the students is analyzed online.

ADIS is designed to reside over a parent canvas, either of proprietary origin (i.e. conventional market Web Browsers such as Netscape Navigator® or Communicator®, Microsoft Internet Explorer®, or Sun Microsystems HotJava®), or on a Hypermedia browser designed specifically for the ITS [1]. The system can be configured either as a standalone application or a client/server application with the parent canvas residing on the central server, and students accessing the Intelligent Tutoring System (ITS) as hosts (or clients). Figure 1 gives a general schematic representation of ADIS.

Figure 1 Schematic Layout of ADIS

The parent canvas consists of several core modules:

There can be many student hosts (clients) but there is only one central expert (server). Each student will have his/her own Student model but all will use the same copy of the Expert model in the Expertís Knowledge Base Database. The ADIS Modules can contain many more components than are shown in the diagram.

2 The Graphical User Interface
The Graphical User Interface (GUI) consists of an activator and separate applets (microworlds) for each module available in the ITS. The activator is a login screen (shown in Figure 2). Students must enter their login identification before they can select from the buttons below. Each button corresponds to a particular microworld module in the CE108 data structure curricula. Only one microworld application can be activated at any one time.

Figure 2 ADIS Login Screen

Once one of the buttons are depressed, the corresponding module applet will be activated and will appear in a child window. A sample child window is shown in Figure 3.

Figure 3 ADIS User Interface

The functions of the various buttons and choice lists are outlined below:

  1. DocText Area Text area for pedagogic instruction and error messages. Also shows a welcome message on start-up.
  2. Exit Button Quits the current module and returns to the logon screen.
  3. Mode ChoiceList Allows students to choose between 3 modes:
  4. (i) DS Tutorial - to go through exercises on various aspects of the module.

    (ii) C Program Tutorial - to go through coding examples on various aspects of the module.

    (iii) Free Play (default) - Allows student to operate in "Paint Brush" mode, i.e. no guidance or control.

  5. Operation ChoiceList Provides students with necessary tools to operate on the data structure during all modes of operation.
  6. Exercise ChoiceList Only available when student selects either DS Tutorial or C Program Tutorial modes. Allows student to choose which module-specific aspect to practice on, for example, in Linked List the student will be able to choose from INSERT and DELETE exercises.
  7. ButtonOptions Set of module-specific buttons containing functions unique to that module.
  8. Main Canvas Main scrollable drawing area where manipulation of data structures takes place during all modes of operation.
  9. Status Bar Provides help hints for every function, button, or operation activated by students.
3 Graphical Representation of Data Structures

Figure 4 shows the graphical representation of the stack and queue data structures in linked list implementation. These representations were chosen because they are similar to those shown in text books, and thus the user will be able to associate with what he/she has learnt for the textbooks with the display on the tutoring system.

Figure 4 Graphical representation of stack and queue nodes

There are no restrictions placed on the drawing of the data structure and nodes and arrows can be drawn or removed at will. This is because the GUI is meant to be a graphical display tool and would only respond to request made by the student. The restrictions for the system are applied during the course of the exercises and it is the expert system that monitors the studentís action and restrict him/her from taking a particular course of action. These restrictions will enable the expert system to guide the student through the exercise by taking the right course of action, thus helping him/her to learn.

4 Communication Model

In this section the way of communication between the expert module and the individual microworlds (referring to the stacks, queues and trees handling modules). In order to minimize passing of data, a mechanism was developed where only one object is passed between the components as shown in Figure 5.

The datum of information transfer between the Expert and the GUI is the AtomicAction object. This object contains the complete graphical information about the action just performed by a student, and will be used by the Expert to compare against its template, to determine if the student is on-track in the exercise.

Figure 5 Communication Model

This object also represents 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 represents the unit of work of the IMTS, and is responsible to convey the type of action just executed by the student. The value of this variable will uniquely distinguish which operation the IMTS is currently executing.
  2. Bubble This object contains the actual graphical information of the object, like the type (arrow, node), its coordinates and color within the GUI, and an adjacency list describing any connectivity with other objects. The adjacency list is particularly important to the Expert and is used extensively for providing connectivity information of each student action during constraint pattern matching.
Each instance of an AtomicAction object either contains only an action component, or an action plus a corresponding Bubble object describing the action.

5 Expert Model

The Expert model contains the correct step sequence (templates) for each exercise of every module available in ADIS. These templates are used to compare actions executed by students with acceptable actions, to determine their correctness. In addition, the instructions and starting state sequences for each exercise are also stored in here. During run-time, only read transactions are allowed, so that the Expert can retrieve exercise records for display and comparison with student actions. Write or update access privileges are available only to system administrators.

As the Expert model is for exclusive use by the Expert, it is invisible to students (i.e. students have no access to data in the Expert model). However, each student logging on to the Intelligent Tutoring System (ITS) will have a Local copy of this Expert model, on top of his/her own Student model. Due to security restrictions imposed by standard browsers, this cannot be further developed to having only a single copy of the Expert model residing on the main Server and all studentís holding sessions with the Expert sharing the Serverís copy.

6 Student Model

The Student model is similar in structure to the Expert model, but differs in content. The Student model is primarily concerned with storing the history of a student, i.e. the sequence of steps executed by the student for each exercise within each module of the ITS attempted to date. In addition, to supplement the Expert in modeling the student more effectively, a record of every past error committed by the student in each exercise is also stored.

The Student model is created initially when a student first logs on to the ITS. The database is named after the studentís loginID which makes maintenance and performance evaluation more convenient. Thus the Student model is continually updated as the student makes use of the ITS. An exercise record within the Student model will only contain information if the student has previously attempted it. The information stored is the exact sequence of steps taken by the student regardless of the correctness.

7 Multiple-Level Coaching

In ADIS, multiple-level coaching has been implemented. There are three (plus one) levels of coaching. Multiple-level coaching aims to provide a varied and refreshing response each time a student makes an error.

Level 0 activates when the system times out. This will happen if the student does nothing for a pre-determined amount of time. The system will prompt the student to either continue with the session and execute an action or end the exercise and proceed to another module. There is no pedagogical value at this level and this is why it is known as the "plus one" level rather than the fourth help level.

When a student makes an error, the Expert will check to see if the student has any history regarding the erroneous step. If not, then the student is a first-time offender for this constraint violation. Level 1 will be activated when a student makes an error for the first time. The pedagogical instruction available at this level is in terms of useful hints and prompts. The Expert tries to describe what the problem or error is. The aim of the Expert here is to try and prompt the student to make the correct move by himself/herself. The first person has been used in all dialogue displayed to students; this is in the hope of more closely emulating a human tutor.

Violating a constraint more than once does not automatically cause the help-level to be upgraded to level 2. If the Expert determines that the constraint violated is not critical, then the help-level will remain at level 1, another prompt message will be displayed, and the student will be allowed to re-execute the step. This maximizes the opportunity of the student to discover the correct answer for himself/herself, which has the highest benefit in pedagogy.

Level 2 provides more detailed help to the students. The student will get more specific hints and instructions how to pursue with the problem.

Level 3 will activate when a student violates a fundamental constraint, or repeatedly makes mistakes at level 2. The Expert will tell the student explicitly what to do in order to get the correct answer. The Expert can then explain the concept that was violated, with an example, or by completing the exercise for the student. The student then chooses one of several options:

  1. Go back to the exercise being attempted, and re-do the complete exercise.
  2. Go through a new exercise, which isolates the concept in doubt. This aims to confirm the studentís grasp of that concept. Continue with option a.
If not already in the module which teaches the concept, save the current module context, exit the module and call up the module containing the concept in question (cross-link to external modules). The Expert will then start that moduleís tutorial with the student to clarify doubts. After that, proceed with exercises from that module. Once confirmation of the studentís understanding is obtained, return to previous module and proceed with option a.

The development of ADIS is advantageous to the students taking a course in Data Structures. With the help of this ITS the students could take a shorter time in learning to use and manipulate data structures. The exercises that are available on the system will help them to understand the correct way to insert or delete a node in the data structure. Certainly it would improve their skills in using data structures in the programs that they will have to develop later.

8 Conclusion

ADIS is advantageous to the students taking a course on Data Structures. With the help of this tool the students would take a shorter time in learning to use and manipulate data structures. The exercises that are available on the system will help them to understand the correct way to insert or delete a node in the data structure. Certainly it would improve their skills in using data structures in the programs that they will have to develop later.


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