Students' Use of Animations for Algorithm Understanding

Introduction

We present an exploratory investigation of how students understand algorithms while using different types of algorithm animations. While animations may have intuitive appeal, they are often added to interfaces without a clear understanding of how the animation will benefit the user. Studies have compared the effects of animated and static graphic displays on computer-based learning, but results are inconsistent [2]. Our goal in the current work is to explore the roles played by two types of algorithm animations in student learning. Through micro-analyses of student performance, we seek to establish clear, causal links between characteristics of alternative animation displays and the progress of student learning.

Search Algorithms

In this pilot study, we focused on students' understanding of two AI search algorithms: Best-first (BF) and A*. When provided with a start and goal city, each algorithm attempts to find the shortest path from start to goal. Both search algorithms maintain a list of cities yet to be inspected (the "open" list) and a list of already inspected cities (the "closed" list). The algorithms differ in how they decide which city to inspect and the role played by the closed list. BF chooses the city closest to the current city. The closed list avoids loops in the search. A* chooses the city on the open list that lies on the shortest estimated path computed by summing its distance from the start city and its (estimated) distance to the goal city. If A* encounters a city in the closed list that is reached by a shorter path from the start city, this city is re-inserted in the open list.

Alternative Animation Displays

State information for a search task can be represented at different levels. On one level, the state of the algorithm can be represented by displaying the value of key variables. The animation would show the variables changing over time. On a different level, the state of the algorithm can be represented in terms of the algorithm's purpos - the meanings of key variables.

We investigated two algorithm animation displays, which work at different levels of detail. Both displays are part of the FLAIR system, a repository of pedagogical materials that support instruction in introductory undergraduate Artificial Intelligence courses [1]. One display animates the behavior of the search algorithms on a geographical map. The student specifies a start city and a goal city and selects a search algorithm. During a search, the display shows the current partial path on the map, marking the cities that have been examined. Thus, the animation shows the algorithm's exploration of a map, effectively displaying the partial path currently considered "best." A second display animates the contents of algorithms' list structures during the search [3]. During a search, the display shows the current city and the changing contents of the list data structures. Each list is a separate row in the display, and each city is represented by a labeled block. The student can also examine current estimates of the cost of including a city on the open list as the next step in the search path.

METHOD

Our goal in this pilot study is to explore students' behavior as they learn about the two search algorithms and to observe the role of the animation displays in this understanding. Through observing the microstructure of student problem solving, we seek evidence for and against the usefulness of the different animation displays for student learning.

Participants & Task

Two undergraduate CS majors were recruited for the evaluation. Both students had taken a data structures course but neither had knowledge of AI search algorithms. The students were asked to explain differences between the BF and A* algorithms. The task was to specify example search problems (i.e., start and goal cities) that demonstrate the relative performance of BF versus A*. For example, students were asked to find (if possible) a problem where A* finds a shorter path than BF and one where A* examines more nodes than BF. In addition to specifying example search problems, students were asked to describe the differences between the two algorithms.

Procedure

Before the evaluation session began, the students were given a brief explanation of heuristic search and a hands-on demonstration of the animation displays. Students were supplied with the task description, an overview of search concepts, pseudocode for the BF and A* algorithms, and blank sheets of paper for note taking. The students had two hours to complete the tasks and were instructed to work collaboratively. A video recording was taken of the computer screen during the session. Students were encouraged to verbalize as they problem solved.

OBSERVATIONS

The primary data used in the evaluation was the videotape of the problem-solving session.

• * During the first 30 min, the students engage in trial-and-error exploration using the map display. In time, they begin to predict the algorithms' behavior at each step. At the end of this period, the students find example problems that satisfy the criteria of those tasks for which there are answers.

• * In the next 30 min, the students decide to examine the pseudocode to discover how to find the remaining example problems. They form the initial hypothesis that BF examines fewer cities because it "examines on the fly."

• * The students resume testing the algorithms using the map and list displays, and suggest a refinement to the initial hypothesis: "BF uses only the estimated distance to the goal. A* [also uses the partial path from the start city] ...". They begin to keep track of the open and closed list contents on paper. At the end of the first hour, they conclude that "BF just calculates which [city] is closest to the goal."

• * At approximately 75 min into the evaluation, the students design new tests for A* based on how they think the algorithm will behave. During a test, they notice with surprise that A* "jumps around." That is, in contrast to BF, which always explores from the current city, the map display shows that A* sometimes considers alternative paths from the start city to the current city. The students set as their goal to explain this phenomenon.

• * During the last 15 min of the allotted time, the students attempt to explain the differences between the two algorithms. Based on several more tests of the algorithms, the students modify their previous tentative hypotheses into a final explanation. The key difference between the algorithms, they conclude, is the fact that A* keeps track of previous promising paths whereas BF does not. The students note that this feature of A* explains why, during search, A* appears to "jump around" on the map display.

DISCUSSION

The most striking event occurred midway into the second hour when the students noticed that the A* algorithm "jumped" to explore alternative paths (shown in the map display). This visual discovery, which facilitated the students' discovery of the critical difference between the algorithms, can most clearly be attributed to the map display. In contrast, the list animation display did not appear to be as useful to the students. They chose instead to keep track of the changing list contents on paper.

CONCLUSIONS

An animation of an algorithm shows successive states in the algorithm's execution. Depending on how the states are represented, the animation allows easy determination of certain forms of state information and, more importantly, facilitates comparison of successive algorithm states. The map display shows overall behavior. This display provides information on the current path being considered. Because a primary difference between BF and A* is in how paths are searched, the key difference in the algorithms' behavior can be readily observed in the map animation. At certain points, the A* algorithm switches the entire path from start to current city; a behavior never exhibited by BF.

The list display animation shows the nodes added to and removed from the two main algorithm variables, the open and closed lists. However, the display does not readily show why a particular node is added or removed. That is, for understanding the differences between the algorithms, changes in the lists are not as important as the reasons for those changes, in terms of the heuristic criteria the algorithms use for search (i.e., the various "cost" functions).

Alternative animations of the same algorithm may provide different information and facilitate different types of reasoning. Students found the list animation unnecessary, but the map display led them to discover the key difference between the algorithms. Had the list animation also shown the reasons behind the changing list content - the heuristic cost function - it might have aided students' understanding. As with static displays, one must consider the information displayed by the animatio - what information is readily extracted by viewing the animatio - in light of the information needed by users (learners) for their tasks.

Acknowledgments

This research was supported in part through the Educational Infrastructure Program of the National Science Foundation (Grant #CDA-9115254) and by Educational Testing Service.