An Animated Tutoring System for Interactive Learning of Nonlinear Data Structures

Abstract

This paper presents an interactive, user-friendly tutoring system, which can be used to enhance students' understanding of the principles behind data structures. The system has the capability to display data structures graphically as well as providing the facility to allow users to perform the basic operations on the data structure generated. An animation-based approach has been developed to provide a step-by-step illustration of how various traversal techniques are performed in the context of binary search and AVL trees data structure. The system has a tutorial mode incorporating exercises, where students can learn basic concepts operations associated with each data structure. The evaluation was carried out by computer science undergraduate students in the School of Computing and Mathematics. It is generally acknowledged that the system was very useful in teaching students about data structures. This system can be used as an effective supplement to traditional teaching methods.

Keywords:

• tutoring system
• animation
• data structures
• Java programming

Introduction

Data structure and associated algorithms are an important part of any computer science curriculum. It is a common observation that teaching data structure to students effectively is a constant challenge. Students struggle to comprehend theoretical models and core concepts. Becker and Beacham (2001) found that it is often difficult to let students understand a working knowledge of the creation and operation of data structures by using traditional communication and delivery methods. They developed a graphical, animated system aiming to provide a step-by-step walkthrough of how operations are performed on B-Trees data structure. Chen and Sobh (2001) highlighted that many students find it difficult to understand various data structures because it requires abstract thinking. They argued that it would be very helpful if there was a visualization tool of data structures such as arrays, queues, stacks, trees and graphs for students to manipulate. An intelligent tutoring system which aims to guide the interactive learning of data structures from the algebraic specification to the real implementation was developed by del Vado Vírseda et al. (2009).

The recognized usefulness of an animated tutoring system has triggered several efforts from the computer science community to develop web-based animated systems. For example, the applet provided by one of the MSc students at the University of Liverpool (http://www.csc.liv.ac.uk/~ullrich/COMP102/applets/bstree/) demonstrates the operations of insertion and deletion on binary search trees. The system available at http://webdiis.unizar.es/asignaturas/EDA/AVLTree/avltree.html has a number of useful features to demonstrate the behaviour of binary search and AVL trees. Interestingly, the system seems to only accept a tree of integers.

The main purpose of this paper is to present a Java-based animated tutoring system. It can be used to provide an interactive exploration environment, in which students can learn and gain a better understanding of the principles behind data structures through experimentation. The following section outlines systems design. A detailed description of the system’s implementation is provided in the following section. The evaluation results are then presented and the paper concludes with discussion of the results, and future development.

System design

Starting with a brief description of requirement analysis, this section details the design of several main components included in the system including database design.

Requirements analysis

Before the start of the system design, a set of requirements were gathered during the regular meetings between the stakeholders. The main purpose of this project is to develop a system that could demonstrate the operation of algorithms on data structures to help students visualize and understand the makeup of each data structure and the difference between traversal algorithms. This general requirement was expanded upon in meetings to derive a set of requirements defined to a level of detail sufficient for systems design. A total of 15 functional requirements and 18 non-functional requirements were defined and documented using the Volere requirement shell (Volere 2011) as illustrated in Figure 1. The implementation of binary search and AVL trees were given the highest priority as they were usually the focus of the Advanced Programming module taught in the School.

Figure 1 An example of requirements documented using the Volere requirement shell.

Use of Unified Modelling Language

Throughout the project, Unified Modelling Language (UML) has been utilized to support systems design with constructing Use Case Diagrams as the starting point to reflect the requirements of the users. The Use Case Diagram shown in Figure 2 provides a high level overview of the application to be built. Although it does not describe the requirement in details, it highlights the relationship between requirements, users, and the major components. When the user starts the application, a connection is made with the database; it is at this point that all the data is fetched and stored. All the use cases are initiated by the user and the functionality of the system and what actions can be performed within the application are clearly depicted.

Figure 2 An illustration of the Use Case Diagrams used in the systems design. A use case is represented as an eclipse with a name inside. The stick man icon with the name below of the icon symbolizes an actor and other external systems, such as a database.

In order to model stepwise activities and interaction between components, activity diagrams have been used. Figure 3(a) illustrates the scenario that occurs when a user responds to a question in the System Quiz section. Rounded rectangles depict the activities within the workflow. The diamond is a decision which checks whether the answer is correct or incorrect and then notifies the user. The black circles within the System Quiz section represent the final state or termination of the activity. The sequence of events that take place when a user tries to delete a node from a data structure is illustrated in the activity diagram in Figure 3(b). When the user presses the delete button, a checking is then performed as to whether the user has entered a value in the textbox. If no value has been entered, the workflow ends; if there is a value, a search is performed to check if the value exists within the data structure. If a value has been entered but does not exist, the flow terminates, otherwise the node is deleted and any reshaping is performed.

Figure 3 An illustration of the use of activity diagrams: (a) activity diagram for System Quiz section; and (b) activity diagram for deleting a nod.

Database design

During the requirement gathering stage, it was decided that it is important to incorporate a quiz section into the system, which helps students test their knowledge about the basic concepts of data structures and their operations. The quiz data should be stored in a database and the design must allow for the possibility that more questions can be added by lecturers whenever necessary.

Figure 4 show the Entity Relationship (ER) diagram of the database used to store quiz data. There are two tables: ‘Questions’ and ‘Answers’. The table Questions is for storing all quiz questions. It contains a column called ‘difficulty_level’, representing the difficulty level associated with each question. All of the questions stored in the database come in a choice of three difficulty levels: 1, 2, and 3 standing for basic, medium, and advanced levels respectively. The table ‘Answers’ stores all the possible answers. It has a column ‘is_right_answer’ which defines what choice is the right answer for particular question. Storing answers in a separate table not only allows for each question to have a different number of choices, but also each question can have any amount of answers (1:N relationship).

Figure 4 ER diagram of the database used to store quiz data; PK: primary key, FK: foreign key.

Implementation

The system is a Java-based application designed to provide an interactive learning environment. It has the capability to display data structures graphically on the computer screen, as well as providing the facility to allow users to perform the basic operations on the data structure generated. The interface for the system is shown in Figure 5. On the top there is a menu bar including a list of menu items used to import trees from a sequence of objects, either Integer or String, stored in external files and edit some system parameters, for example background and node color settings. Right under the menu bar, there is a pane holding all the buttons used to perform some basic tree operations, such as tree traversal and inserting, deleting and searching a node in a tree. The central pane is the core component of the system. All the visualization and animation takes place in this pane. On the right-hand side, there is the quiz section used to test students’ knowledge related to the data structure. The implementation of some main components is detailed below.

Figure 5 A screenshot of the system developed.

Traversing a data structure

Traversing is an important topic in teaching data structure and yet students find it difficult to understand. Providing various means to help students gain a good understanding of different traversal techniques becomes a core part of our tutoring system. Firstly, we provide a visual animation to illustrate the process associated with each traversal algorithm. Specifically, once a user clicks on the corresponding button, the system will activate an animation thread in which the color of each node currently being visited is changed in a speed defined by the user. The order in which the color of nodes is changed depends on the order in which nodes are visited during traversal, as illustrated in Figure 6. In the meantime, the output of the traversal is displayed accordingly at each step. By doing so, the students can clearly visualize each traversal process step by step with a speed they are comfortable with. As can be seen in Figure 6, the yellow node represents the current node to be visited. The order in which the yellow node is displayed reflects the order in which nodes are visited during traversal, i.e., visiting each node’s children (from left to right) before the node itself. The output of the post traversal is 9, 10, 47, 70, 56, 12. By displaying a succession of these images from (a) to (f) along with the corresponding output of the visited nodes, the traversal process is highlighted and easy to be understood. The UML activity diagram is shown in Figure 7.

Figure 6 Visual animation of post-order traversal implemented in the system.

Figure 7 The UML activity diagram for animation.

Parameter settings

During interviewing with students, it was found that ability to adjust various system settings including background color and zooming is one of key factors to make the system user-friendly. To achieve this, two approaches were implemented. For selecting the panel background color scheme, an instance of JColorChooser contained in the javax.swing package (http://docs.oracle.com/javase/1.4.2/docs/api/javax/swing/JColorChooser.html) was created, which provides a pane of controls designed to allow a user to manipulate and select a color as illustrated in Figure 8. In addition, a total of seven instances of JSlider (http://docs.oracle.com/javase/6/docs/api/javax/swing/JSlider.html) were created to adjust various system parameters including animation speed, zoom in/zoom out, the width of the X-axis and the length of Y-axis. The use of JSlider makes the user easily enter a numeric value bounded by a minimum and maximum value.

Figure 8 An instance of JColorChooser used to determine the panel background color.

MySQL database

In order to minimize configuration and installation effort from students, while providing an interactive exploration environment, all the data related to the quiz section are stored in a MySQL database located in the school server. Through JDBC (Java Database Connectivity), students can access the quiz section without installing a local copy of the database, as illustrated in Figure 9. In addition, the lecturer can easily to update and maintain the quiz database using the facility provided by the school server.

Figure 9 The framework used to connect the quiz MySQL database located at the school web server.

Evaluation

At the end of the development of the system, an evaluation session was carried out with Computer Science undergraduate students to assess what they thought of the application. An anonymous user evaluation form was created and distributed to the students. They were informed that not all steps were mandatory and that if they wished they could disregard the steps and test the system without instructions. The feedback form allowed the testers to record any likes, dislikes, defects and suggestions for improvement. An anonymous evaluation form was completed by each participant.

What the users liked about the application

Being easy to use and nicely laid out are among the most favourite features found by the testers. The general consensus was that the system was very useful for teaching data structure related modules and those seeking to learn the concepts involved. The tests showed that users were able to navigate the application with minimum instructions. They liked being able to resize the tree and change the color by using sliders. They liked that you could change the speed of the animation and delete the node by clicking it. Being able to view the traversal pseudo code when an animation was occurring was also found useful.

Areas for improvement

The User Acceptance Tests suggested several areas for the improvement. An issue that was raised during the evaluation was that there was no overall total score when the user completed answering the quiz questions. With most quiz systems, the user expects a total at the end and not simply a ‘correct’ or ‘incorrect’ response with each answer. Another issue found was that the rebalancing operations on the AVL tree are too quick for the human eye. This is because the reshaped tree is repainted as opposed to the X and Y coordinates of a node being gradually changed to show the nodes moving to their new position. This would definitely be considered for future development.

Discussion and conclusions

This paper presents a user-friendly cross-platform tutoring system, which can be used to enhance students' understanding of advanced data structures. It places an emphasis on the implementation of an animated system to support the teaching of binary search trees, AVL trees and graphs, which were the core components of the Advanced Programming module taught in the school. The system has the capability to display data structures graphically on the computer screen, as well as providing the facility to allow users to perform the basic operations on the data structure generated. An animation-based approach has been developed to illustrate the process associated with each traversal algorithm. In addition, the system has a tutorial mode incorporating exercises, where students can learn basic concept operations on data structures. The system was evaluated by Computer Science undergraduate students. Feedback from the User Evaluation forms was very positive. It is generally acknowledged that the system was very useful for teaching students about data structures. The animated approach implemented has demonstrated great potential to help student understand the theoretical aspects associated with each data structure. This system can be used as an effective supplement to the traditional teaching methods related to data structure modules.

The issues raised during the evaluation stage provide directions for future development. These include using animation to demonstrate AVL tree rebalancing and a total score for the quiz section. The current version only provided the limited functionalities to support the graph data structure. Using visual animation to illustrate graph traversal techniques and other related algorithms, such as Prim’s algorithm used to construct minimum spanning trees, and Dijkstra Algorithm used to find shortest path lengths, will be an important part of the future development.