The goal of an Intelligent Tutoring Systems (ITS) is for itself to be aware of the knowledge it contains, as well as what the student knows. Such systems should be "... capable of automatically inducing and using a structural model of the student's reasoning strategies" . An ITS should also be "self-adaptive" - able to adapt tutoring sessions based on self-contained knowledge. Several systems are evaluated below. These represent the current range of approaches for the ITS playing field in Student Modeling. Most systems to date either employ one of the following techniques, a variant of one, or a hybrid of two or more.
A sophisticated Intelligent Multimedia Tutoring System (IMTS) for an university course on Data Structures in C gives students a possibility to get answers to their questions outside of labs . The students could also prepare better for their labs using the IMTS or review part of the lecture material during lab sessions when they need help. The IMTS is completely developed in Java and resides on a parent canvas, either of proprietary origin (Web Browser or Standalone Application) or on one designed specifically for the IMTS. In the first phase it supports the students on algorithms on linked lists, queues, stacks and binary search trees. The user interface is completely interactive, meaning that the student will interactively manipulate the data structures on the screen. In tutorial mode, the student will be given exercises, which s/he has to solve interactively by manipulating the nodes of the data structures. Feedback and tutoring will be given to the student upon errors. In this paper we describe the usage and implementation of constrained-based student modeling as introduced by Ohlsson .
Constraint-Based Student Modeling
No perfect solution has been found and perhaps none should be expected. The extent of false knowledge is so overwhelming that the problem of inferring what the student "knows that is not so" is computationally intractable in its general form and perhaps even conceptually incoherent. Instead of a single general solution, there has been a slowly growing library of imperfect but useful techniques. Each technique has a unique combination of advantages and disadvantages. What is required is to match a suitable technique for each pedagogical purpose. The approaches to student modeling can be divided into three broad but distinct groups of thought:
The Constraint-Based approach to student modeling [Ohlsson, 1992] suggests representing subject matter knowledge in sets of constraints. A student violating one of these constraints indicates incomplete or incorrect knowledge. These violations can be used to guide an ITS in its response. This approach suggests that runnable models of either the expert or the student may no longer be needed. It also proposes that the computations required for student modeling can be reduced to just simple pattern matching.
Constraint-based student modeling is based on the notion that students can be described in terms of entities more abstract than particular solution paths or strategies. Abstraction can be achieved in two ways:
Applying this to teaching of data structures, it was discovered that this modeling technique is the best suited. Imagine that the students' task is to learn how to delete an element out of a linked list, e.g. element 2 as shown in Figure 1 (a) - (e). The steps the student has to perform are the following:
If the student leaves out step 1 and 2, then upon deleting element 2 the tail of the linked list will be lost (Figure X (f)), as indicated by the dashed element 3. Detecting this situation it is immediately clear what kind of error the student made and the tutoring module can act upon it. It can reset the exercise and give the student useful hints, so that s/he discovers her/himself that a help pointer is needed in order to keep the tail.
With many of the documented strengths of the technique in line with the data structure ITS domain, the project will concentrate on applying this technique while implementing the ITS component. However, the potential disadvantages of the constraint-based model cannot be ignored. The expert model designed should attempt to provide a sufficiently exhaustive semantic net such that disadvantage 2 can be avoided. This will also affect the kind of pattern to be used in defining constraints.
To our knowledge the constraint-based student modeling technique was never before implemented in an ITS. Therefore there is no evidence that the technique can produce psychologically realistic or pedagogically useful student models capable of guiding instruction. However, the off-line diagnosis done by Ohlsson (1992) has demonstrated its feasibility. Based on the diagnosis, this technique is well suited with respect to the goals of the data structure tutoring system.
Constrained-based student modeling was proven to be successful for an Intelligent Tutoring System on data structures. The computational overhead that was previously needed by other ITSs was greatly reduced this way. Instead of providing an extensive bug list or diagnosis model, a more simple constrained-based error list is needed. In combi
nation with a sophisticated tutoring method such as socratic dialogue the system will serve as an intelligent interactive tutoring system during laboratory sessions.
 Brown, J. S., R. Burton, M. Miller, J. DeKleer, S. Purcell, C. Hauseman and R. Bobrow (1975): Steps towards a Theoretical Foundation for Complex, Knowledge-Based CAI. Technical Report 3135, Bolt, Beranek and Newman.
 Warendorf, K. (1996): Combining interactive multimedia and inquiry teaching to build an intelligent multimedia tutoring system, Proceedings of ED-MEDIA 96, Boston, Pg. 814.
 Ohlsson, S. (1992): "Constraint-Based Student Modeling". Journal of Artificial Intelligence in Education 3(4), (pp. 429-447).
 Burton, R. (1982): "Diagnosing bugs in a simple procedural skill" in D. H. Sleeman and J. S. Brown (eds.): Intelligent Tutoring Systems (pp.17-183). New York: Academic Press.
 Ohlsson, S., Langley, P. (1988): "Psychological evaluation of path hypotheses in cognitive diagnosis" in Mandl H., Lesgold A. (eds.): Learning issues for intelligent tutoring systems. (pp. 42-62). Springer-Vlg.
 Anderson, J. R., Boyle, C. F., Corbett, A. T., and Lewis, M. W. (1990): "Cognitive modeling and intelligent tutoring". Artificial Intelligence 42, (pp. 7-49).