Abstract: A design for an Intelligent Multimedia Tutoring System (IMTS) is proposed in which hypermedia is central. The IMTS will tutor students during their laboratory assignment for CE108 Data Structures and Algorithms. A guided discovery tutoring style within a World Wide Web browser provides a mixed-initiative dialogue tutoring style with variable levels of guidance. Hypermedia provides software visualisation and audio feedback. Navigation support for browsing is included. A tri-layer architecture supports three different learning activities. From a primary layer of adaptive hypermedia students can access a layer of fill-in exercises and a layer of microworlds. Implementation is based on WWW resources.
We propose a design for an Intelligent Multimedia Tutoring System (IMTS) to support students during laboratory sessions for CE108, a course in data structures and algorithms . Typical for the laboratory situation is that the system will be accessed by students with varying information needs. Depending on the lab assignment, the amount of preparation, and their general knowledge level, students may want to study the syntax of a C statement, investigate the dynamics of a sorting algorithm, look for C code examples, or expect guidance to solve a programming problem related to their assignment. The IMTS must be capable of handling these different goals without enforcing one fixed tutoring style upon students with different information needs. Since finishing their assignment has top priority for the students, the system must be easily accessible and support flexible interaction without requiring extensive instruction. The system should also support distance education of students through the internet.
A principal design driver is the application of multimedia. It has been shown that multimedia helps to make education more attractive and hence more effective by providing visualisation and higher levels of interactivity . In computer science education, the visualisation and interactive animation of abstract data structures has a positive effect on learning algorithms and is regarded attractive by students . A multimedia user interface is also attractive because it allows various modes of interaction which facilitates learning.
Current available systems to aid computer science education can be divided in two main categories. The first category consists of Software Visualisation Systems such as Tango, Balsa II, and more recently SWAN  . A significant number of such systems exist , but few of them have been effectively applied in education. Most of them lack facilities for appropriate tutorial feedback to learners and are not integrated within a complete tutoring framework. User interface friendliness is usually limited and, especially for novice users, freely experimenting with algorithms is cumbersome.
The other category consists of classical Intelligent Tutoring Systems (ITS). They are able to interactively tutor a complete curriculum, usually in a textual environment. A number of ITSs have been developed for teaching programming languages. They are able to give students intelligent error feedback and usually have a tutoring style that dictates both the type of exercises as well as their order based on a curriculum sequencing component. An example is Anderson's Lisp Tutor . The user interface is text-based, and students are led through a series of tutoring sessions until the complete curriculum is completed. Multimedia is usually not applied.
We strongly feel that for successful tutoring in a computer science laboratory the system must find a middle ground between the above categories. It should have multimedia capabilities to visualise algorithms and provide an easy-to-use yet sophisticated interface. It also should contain ITS components for student modelling, curriculum sequencing, error feedback, and a flexible, non constraining tutoring style. It should be able to switch from unrestricted exploration of algorithms to more directed tutoring whenever considered more effective for a given topic. Also, information lookup by students as in general information retrieval systems should also be supported in the IMTS.
Similar systems are already emerging in ITS research. The usage of Adaptive hypermedia (adaptive multimedia in a hyperlink format) in ITS research is gaining popularity in to communicate domain knowledge. Adaptive hypermedia can bridge the gap between traditional unrestricted user-driven hypertext environments and machine-driven tutoring systems. Adaptive hypermedia tutoring systems provide navigational guidance to students browsing hypermedia documents. Navigation support is done by suggesting suitable hyperlinks, and marking or hiding non-recommended ones. The support is based on the curriculum and on the student's knowledge. Multiple choice tests and fill-in questions integrated within the hypermedia environment serve both as exercises and provide data for a student model in order to give individualised guidance. Because a large part of student population is familiar with hypermedia through the internet, it is expected that the usage of adaptive hypermedia in educational systems will grow . Recent results from a survey we conducted amongst 106 first and second year student who completed CE108 indicate moderate but significant support for a tutoring system for CE108 based on guided browsing. Familiarity with WWW browsers was high.
This paper proposes an
integration of hypermedia with an ITS into
an IMTS for support of students during computer science laboratory
sessions. Related issues concerning tutoring style, architecture
and implementation of the IMTS are also discussed.
2 Existing intelligent tutoring
2.1 Educational hypermedia based on World Wide Web standards
Recently, a number of educational systems that use adaptive WWW hypermedia have been developed. An example such a system on the WWW is ELM-ART . The user interface of ELM-ART is a standard Web browser, in which the user can select topics from a Lisp curriculum. Guidance in hypertext is provided by the system through sorting and marking hypertext links as 'recommended', 'not recommended', and 'neutral', according to an individual learning path that is selected by the system. Interactivity is provided by presenting to the student interactive exercises consisting of hypermedia fill-in forms. After analysis of the replies, the system gives textual feedback to the student. Individual hypertext pages are generated based on the student's browsing history. All interaction with the system takes place in a standard WWW browser. Accessing the system over the internet allows distance learning.
Another recent approach in using a standard internet browser in an ITS is SAFARI , where the ITS controls a Web browser. Because the browser is encapsulated in Smalltalk, the tutoring module can hide, show and load the browser with a new pages, thus giving stronger guidance to the student's browsing compared to ELM-ART. As in ELM-ART, information about the user's browsing history is used by the ITS in order to diagnose the student's learning progress and to update the student model.
A third example mentioned here is an educational WWW system for tutoring mathematics . It generates fill-in forms and multiple choice questions based on displayed graphs of mathematical functions. Optional are video clips that contain spoken explanations of mathematical procedures. From the three systems mentioned, it applies hypermedia most.
All three systems share the
advantages of mainly relying on standard
tools for implementation, using HTML in standard browsers, and
allowing distance learning over the internet.
2.2 Algorithm animation within hypermedia
Currently no systems are known to us that apply algorithm animation inside an ITS. However, courseware systems which support interactive algorithm animation within a hypermedia environment do exist. Classroom experiments with the courseware system AlgoNet  confirmed the effect of software visualisation in computer science education. Other empirical results support the conclusion that multimedia instruction combined with interactive algorithm animation is more effective than classical 'blackboard' instruction 
Although algorithm animation
valuable results regarding effective application of hypermedia
in education , they lack intelligent tutoring features. Therefore
below the requirements of an IMTS are identified in order to integrate
hypermedia into a conventional ITS design.
3 Selection of tutoring and
methods for an IMTS
3.1 Guided Discovery tutoring with hypermedia
Elsom-Cook has classified a number of ITSs based on the level of constraint their tutoring style imposes on the student. The range of systems runs from constructionist environments such as Papert's Logo environment (fully unconstrained exploration by students) to systems with a directive tutoring style such as the Lisp Tutor. Elsom-Cook's approach to tutoring known as guided discovery tutoring identifies the need for variation in tutoring style which can be defined as the amount of freedom a student has for explorative actions while being tutored . Ideally, the tutor should try to be as invisible as possible for the student. This approach to tutoring resembles cognitive apprenticeship and coaching theories. In apprenticeship tutoring, learner initiative and built-in support from an intelligent user interface are essential. Because this is similar to the presence of navigation guidance in hypermedia , we propose to combine a hypermedia environment with guided discovery tutoring.
Since a laboratory support system will have to rely on mixed-initiative dialogue to handle the diverse information needs of the students, the level of direction in tutoring has to be variable. The student will usually decide what he wants to be taught next. The system will guide him in this selection process, and make suggestions. Hence, the tutoring style of the IMTS will usually be guiding instead of 'classical-style' tutoring. Guidance in hypermedia consists of offering suggestions to the student. The tutoring style should however become more directive when this is more effective for certain topics.
Elsom-Cook proposes bounded
user modelling for student
modelling in guided discovery tutoring. It is based on the assumption
that an estimation of the user's knowledge level is inevitably
inaccurate, because sufficient student performance data is not
always available. Since information about the knowledge state
of students in an hypermedia environment will be often incomplete,
we propose bounded user modelling to model individual students
in the IMTS. User modelling will be less accurate than in a complete
curriculum-sequencing systems where the system controls the order
of tutoring. To provide navigation support, additional overlay
modelling is proposed to record the hypermedia nodes visited by
3.2 Three methods for communicating domain knowledge
A number of design issues for
effective applying adaptive hypermedia,
fill-in exercises and graphical microworlds in an IMTS are mentioned
here. Hypermedia, exercises, and microworlds are identified as
essential for an IMTS to provide a high level of interactivity.
3.2.1 Adaptive Hypermedia
Recent empirical results from studies of educational hypermedia indicate that just presenting domain knowledge in a hypermedia format is not sufficient to guarantee learning. Factors for the effectiveness of hypermedia on learning are the cognitive style of the student, the structure of the hypermedia network, and the level of interactivity the hypermedia provide.
Cognitive style , the preferred learning style of a student, varies among subjects, and influences the navigational style of students . Adaptive hypermedia preferably takes cognitive styles into account to support different cognitive styles. Cognitive styles can be 'field-dependent versus field-independent' , or 'sensing versus intuitive' . One finding from empirical research is that computer science students who usually do not do well in classical computer science education benefit from hypermedia tutoring  because it matches their cognitive style. Related to this is the finding that explicit structured hypertext is not compatible with students who use a field-independent learning style . This implies that no single structure for hypermedia is effective for everyone.
The Concept mapping architecture of hypermedia is another factor for learning. It has been shown that some types of concept maps help to avoid disorientation better than other types . Disorientation is one of the key problems of educational hypermedia. Theories of learning such as Cognitive Flexibility and Situated learning have been applied to guide the structuring of hypermedia . One outcome was that learning improves when hypertext guidance is available in the form of a central theme that acts as a scaffold for learning.
Cognitive media types are types of physical media defined by their function in the learning process . When the system refers to hypermedia types as 'warning', 'process', 'case study' instead of 'sound', 'picture', 'text', the effect on learning improves. A related finding was that students with some background knowledge of the contents take more advantage of cognitively-based hypermedia structures.
Navigation support can be provided by ordering or marking hypermedia links to indicate their suitability for the student, as is done in ELM-ART. Completely hiding links for the user is also an option, but restrictive. Other methods to provide navigational support are the availability of indices, graphical maps of the hypermedia structure, and displays of the navigation history. Navigation support is closely related to cognitive style, concept mapping architecture, and the student model, and has to be an integral part in the design.
Animation of algorithms in hypermedia has been shown to be effective for learning. Animation enhanced with interaction increases the effect for learning . Video clips that provide no interaction are less effective for learning.
and auditory cues are
important to benefit
fully from hypermedia. According to dual modality theory, voice-overs
aids the understanding of text that is being read simultaneously.
Research has shown that users prefer voice output to accompany
written texts , though no effect on learning was found. Students
appreciated voice-overs because it aided reading and kept motivation
high. However, when the voiced text differed from the written
text the voice was considered distracting. Auditory
are helpful to prepare a user
for coming events and give feedback.
However, in empirical tests half of the subjects found them annoying
, and continuous music was rated similarly. The SonicFinder
 was an experiment of auditory feedback in a sound rich user
interface. The author claims sound added to the attraction of
the user interface. In general, voice-over and auditory cues help
to make multimedia more attractive as long as the user can control
3.2.2 Fill-in form Exercises
In systems that teach computer languages within a hypermedia environment, fill-in forms are widely used. ELM-ART  and CASABLANCA , two systems for tutoring a programming language, contain fill-in form exercises for completing computer programs. Research has shown that program completion exercises are more effective for learning a programming language than program generation exercises are . Students learn faster with completion exercises because source code examples are directly available.
An IMTS with programming exercises
select exercises to tutor the curriculum, or it will suggest them
in order to update its student model. As in CASABLANCA, exercises
should preferably be tailored towards a predefined difficulty
level. Thus, for every topic the IMTS preferably makes a choice
from exercises with various difficulty levels. However, at any
moment students should have the opportunity to select exercises
on their own for a self diagnosis.
3.2.3 Direct Manipulation Microworlds
Microworlds can be defined as sets of objects and operators inside a simple environment which the learner can explore in order to reach an understanding of the processes and relationships of the objects and their operators. An example of a direct manipulation microworld is DIBI, a microworld to explore laws of mechanics . DIBI allows students to simulate elastic impacts by manipulating objects in a guided mode or fully unrestricted. DIBI's student model helps to interpret a student's actions to give appropriate feedback.
For an IMTS for data structure education, a set of microworlds for data structures such as stacks and binary trees would be desirable. Students who enter such a microworld in the IMTS can create, move, and link data structures with a mouse. The manipulation of visible objects helps to visualise abstract data structures and to learn their properties, and is considered a valuable method for learning . Exploration of a microworld can either be fully unrestricted or under guidance from the IMTS. Feedback is given whenever incorrect operations are performed on the data structures. Guided discovery tutoring is achieved by setting a goal structure, consisting of an incomplete data structure. The goal structure has to be built from scratch or from given structures by the student. Guided discovery tutoring is natural for microworlds where learning by discovery is encouraged. However, also unguided exploration should be allowed by the IMTS, where the only feedback comes from the implicit restrictions of the microworld.
Direct manipulation of data
education has been demonstrated in SWAN
and in a number
of Java applets. For manipulation tasks, a mouse-based user interface
is usually preferred over keyboard commands . However, about
20% of the subjects repeatedly prefer keyboard input over mouse
input . Support for keyboard input in a microworlds is therefore
important in order to accommodate all types of users.
4 Layered Architecture for a lab
An example of an educational adaptive hypermedia system that contains elements of guided discovery tutoring is A Learning Lab . In ALL, students can choose to navigate through hypermedia with or without guidance. At any time students can ask the system for a diagnosis of their knowledge by answering assessment questions. Based on the results, ALL will suggest relevant topics from the curriculum. The student model, an overlay model, contains a hypothesis of the individual student's learning style. This enables the system to present topics in an individualised order. ALL contains many elements of a hypermedia ITS. Since an IMTS has different requirements, we present here an architecture specific for an IMTS targeted for the support of students in laboratory sessions.
In the architecture we propose, the tutoring activities are divided in three layers. Each layer has its own tutor. The primary layer consists of adaptive hypermedia, primarily intended for free or guided browsing of topics. It contains hyperlinks to a second layer which consists of fill-in and multiple choice exercises. The primary layer also contains hyperlinks to a third layer which consists of graphical microworld for guided or free experimenting with data structures and algorithms. The IMTS is capable of curriculum planning but it will usually not enforce an order. Instead, based on diagnosis, it will suggest relevant fill-in exercises, exploration in a microworld, or suggest related topics by presenting a set of hyperlinks to the student. Our motivation for an architecture based on three layers, as shown in Figure 1, is :
Whenever a student encounters problems with the laboratory assignment, she can browse freely through topics which are implemented as adaptive hypermedia. The system will give navigation support and may suggest relevant fill-in form exercises to test the student and give problem-directed feedback. Another educational activity the IMTS may suggest is free or guided exploration of data structures in a graphical microworld. Each of the three layers has tutoring methods tailored to the specific type of interaction.
Each layer's tutoring module has
specific methods for interaction with an suitable level of student
5 Implementation with WWW resources
The application of standard WWW
hypermedia platforms has three advantages. First, many students
are familiar with the WWW browsers. Second, authoring of WWW hypermedia
is supported by a number of widely available tools. Third, a WWW
based IMTS is accessible from anywhere on the internet, allowing
true distance learning.
Fill-in forms within HTML pages are
for textual interaction with the IMTS. Graphical user interface
linked to the forms to handle the students' responses, network
traffic is reduced and responses will be faster.
5.3 Direct Manipulation Microworlds: Java Applets
For handling direct manipulation of graphical objects, only HTML and scripting languages are too limited. Java, an object oriented, multithreaded complete Internet-oriented programming language , is proposed for the implementation of microworlds. Java allows implementation of highly customised graphical environments inside WWW browsers. Browsers provide a platform independent environment for small Java applications known as applets integrated in HTML hypermedia .
Although Java is still maturing and
, Java is expected to become more important for WWW hypermedia
development. Especially the availability of graphical user interface
class libraries, advanced multimedia players and authoring tools
for Java hypermedia will increase the application of Java in
World Wide Web hypermedia.
Hypermedia has been recognised as an
element of an intelligent tutoring system for support of students
during computer science laboratory assignments. Recent educational
hypermedia systems on the internet illustrate the growing significance
of hypermedia in intelligent tutoring. The architecture we proposed
here identifies three educational activities through which students
receive laboratory support: browsing through hypermedia, completion
of fill-in exercises, and exploration of data structures and algorithms
in microworlds. Guided discovery tutoring is selected as the unifying
tutoring style for all three learning activities. For implementation,
resources are available from the World Wide Web. The choice for
WWW resources minimises the need for customisation.
 K. Warendorf, :Intelligent Multimedia Tutoring System for Laboratory Support in Software Engineering Education, Proceedings of Educational Hypertext and Hypermedia, Boston, 1996, p. 814.
 M. Hoogeveen, :Towards a New Multimedia Paradigm : Is Multimedia Assisted Instruction Really Effective ?:, Proceedings of Educational Hypertext and Hypermedia, Graz, 1995, pp 348-353.
 A. W. Lawrence, A. Badre, J. Stasko, :Empirically Evaluating the Use of Animations to Tecah Algorithms, Technical Report GVU-94-07, Georgia Institute of Technology, 1994.
 C. Shaffer, L.S. Heath, J. Nielsen, :SWAN: A Student-Controllable Data Structure Visualization System, Proceedings of Educational Hypertext and Hypermedia, Boston, 1996, pp 632-637.
 B.A. Price, R.M. Beacker, I.S. Small, :A Principled Taxonomy of Software Visualization, Journal of Visual Languages and Computing, vol 4(3), 1993, pp. 211-266.
 J. R. Anderson , A.T. Corbett, K. Koedinger and R. Pelletier, :Cognitive Tutors: Lessons Learned, Journal of Learning Sciences, vol 4, 1995, pp. 167-207.
 I. Beaumont, P. Brusilovsky, :Adaptive Hypermedia: From ideas to Real Systems, Proceedings of Educational Hypertext and Hypermedia, Graz, 1995, pp. 93-98.
 E. Schwarz, P. Brusilovsky, G. Weber, :World-Wide Intelligent Textbooks, Proceedings of Educational Telecommunications, Boston, 1996, pp. 302-307.
 R. Nkambou, G. Gauthier, :Use of WWW Resources by an Intelligent Tutoring System, Proceedings of Educational Hypertext and Hypermedias, Boston, 1996, pp. 527-532.
 K. Antchev, M. Luhtalahti, J. Multisilta, S. Pohjolainen, K. Suomela, :A WWW Microworld for Mathematics, Proceedings of Educational Telecommunications, Boston, 1996, pp. 5-10.
 M. M. Recker, A. Ram, T. Shikano, G. Li, J. Stasko, :Cognitive Media Types for Multimedia Information Acces, Journal of Educational Multimedia and Hypermedia, vol 4(2/3), 1995, pp. 183-210.
 M. E. Crosby, , Jan Stelovsky, :From Multimedia Instruction to Multimedia Evaluation, Journal of Educational Multimedia and Hypermedia, vol 4(2/3), 1995, pp. 147-162.
 M. Elsom-Cook, :Guided Discovery Tutoring and Bounded User Modelling, in John Self (Ed.) Artificial Intelligence and Human Learning, Chapman and Hall Computing, 1988, pp. 164-178.
 W. E. Hefley, :Apprenticeship Instruction through Adaptive Human-Computer Interaction, Proceedings of IEEE, 1992, pp. 229-239.
 T. Jones, C. Berger, :Studentsí Use of Multimedia Science Instruction: Designing for the MTV Generation, Journal of Educational Multimedia and Hypermedia, vol 4(4), 1995, pp. 305-319.
 R. D. Kortauer, R. Koubek, :An Empirical Evaluation of Knowledge, Cognitive Style, and Structure upon the Performance of a Hypertext Task, International Journal of Human-Computer Interaction, vol 6(4),1994, pp. 373-390
 R. E. Beasly, M. Waugh, :Cognitive Mapping Architectures and Hypermedia Disorientation: An Empirical Study, Journal of Educational Multimedia and Hypermedia, vol 4(2/3), 1995, pp. 239-255.
 M. J. Jacobson, C. Maouri, P. Mishra, and C. Kolar, :Learning with Hypertext Learning Environments: Theory, Design, and Research, Journal of Educational Multimedia and Hypermedia, vol 4(4), 1995, pp. 321-364.
 K. Opwis, M. Stumpf, H. Spada, :Domain Representation and Student Modeling in a Microworld for Elastic Impacts, in M. Tauber and D. Ackerman (Eds.), Mental Models and HCI 2, Elsevier Science Publishers BV, 1991, pp. 361-372.
 Y.-F. Shih, S. Alessi, :Effect of Text vs. Voice on Learning in Multimedia Courseware, Proceedings of the International Conference on Computers in Education, Singapore, 1995, pp. 460-468.
 S. Bradey and L. Henderson, :Voice-Overs and Auditory Cues: Their Impact and Role in Learning Through IMM, Proceedings of Educational Hypertext and Hypermedia, Graz, 1995, pp. 109-114.
 W. W. Gaver, :The SonicFinder: An Interface That Uses Auditory Icons, HCI, vol 4, 1989, pp. 67-94.
 P. Brusilovsky, E. Schwarz, and G. Weber, :ELM-ART: An Intelligent Tutoring System on World Wide Web, Proceedings of the ITSí96, 1996, pp. 261-269
 M. Soga, A. Kashihara, J. Toyoda, :Adaptive Fill-in-blank Program Problems from the View of Cognitive Load and Applications Systems on WWW, Proceedings of the International Conference on Computers in Education, Singapore, 1995, pp. 575-582.
 J. van Merrienboer, M. de Croock, :Strategies for Computer-based Programming Instruction: Program Completion vs. Program Generation, Journal of Educational Computing Research, vol 8(3), 1992, pp. 365-393.
 B. Shneiderman, :Direct Manipulation: A Step Beyond Programming Languages, Computer, Aug. 1983, pp. 57-69.
 E. Ulich, M. Rauterberg, T. Moll, T. Greutmann, O. Strohm, :Task Orientation and User-Oriented Dialog Design, International Journal of Human-Computer Interaction, vol 3(2), 1991, pp. 117-144.
 E. Eberleh, W. Korfmacher, N. Streitz, :Thinking or Acting ? Mental Workload and Subjective Preferences for a Command Code and a Direct Manipulation Style, International Journal of Human-Computer Interaction, vol 4(2),1992, pp. 105-122.
 G. Trentin, V. Midoro, :A Learning-Lab Where AI Meets HyperMedia, Proceedings of Educational Hypertext and Hypermedias, Boston, 1996, pp. 276-282.
 A. Verhoeven, :Investigation of Software Tools for Development of an IMTS, internal document, May 1996.
 Sun Microsystems., :The Java Language Specification, available on http://java.sun.com, May 1995.
 JavaSoft Inc., "Java API overview" (WWW document), http://www.javasoft.com/products/apiOverview.html