What is the purpose of functional invariants

Lecture Notes in Informatics

Three forms of interactive visual learning of algorithms are covered: viewing an animation, interactively practicing the steps, and experimenting with a simulation. For them, desirable features from a didactic and software ergonomic point of view are given and examples from web-based learning programs are shown. This system is intended to make it easier for the teacher to choose from the plethora of visualizations available on the Internet the ones that are most suitable for his lessons. Introduction Algorithms and data structures are an important part of computer science. Graphic aids have always been used to convey them. For example, in textbooks, the data structure and the sequence of an algorithm are shown in several individual images. It makes sense to rely on visual representations even when learning with the computer medium. Compared to the book, the computer as a learning medium adds moving images, sounds and interaction as a means of expression. The computer can be used by the teacher to show the students the data structure and how the algorithm works. The students can also work with interactive visualizations of an algorithm themselves. As schools are increasingly being equipped with modern multimedia computer systems, this form of communication is becoming possible in more and more schools. The necessary software is now also easier to obtain. The school's Internet connection provides access to hundreds of interactive learning media on algorithms that are available on the Internet. These are mostly algorithm animations. These are short film sequences that show how the algorithm works by changing the data in the data structure. They are mostly available as Java applets that can be executed directly in the web browser. Typically, the teacher has the task of finding, evaluating and selecting algorithm visualizations for an algorithm to be taught. The following sources can provide an initial overview of the available algorithm visualizations: 1. Resource database of the German Education Server e query in January 2001 with (resource category = learning materials AND subject area = algorithms) yielded 24 hits. 87 2. Database-supported directory of algorithm animations. Recorded animations in German and English. An inquiry in May 2001 resulted in 147 hits. 3. \ "Inventory of algorithm animations" Directory with 200 entries. This article should help to evaluate the interactive visualizations found during the research according to didactic and software-ergonomic criteria, so that the teacher can make a selection depending on the goals and framework conditions. A distinction is made between three types of interactive algorithm visualizations: 1. Algorithm animations are viewed and analyzed by the student. 2. Algorithm exercises ask the student to carry out previously seen steps of an algorithm himself. 3. Algorithm simulations allow the student to experiment with how an algorithm works. Algorithm animations In animations, the algorithm sequence is fixed. The student is essentially expected to look at the steps of the algorithm in a visualization. He is not expected to predict steps or develop parts of the algorithm himself. Of the three types of interactive visualization, animation is by far the most common. The work by Stasko et al [St89] gives a good overview of research work on algorithm animation. Desirable features From a didactic and software-ergonomic point of view, I would now like to state some desirable features for animations that were developed for the "viewing" form of learning. Peter Gloor has developed a similar list with an emphasis on software ergonomic criteria [Gl98]. The animation should meet as many of the criteria as possible. Functional structure. The algorithm is divided into functions. Each non-trivial function is explained in its own animation. Functions that have already been learned can be used as building blocks (function calls) in an animation and are only displayed as one step. Teaching text. A teaching text is connected to the animation, which explains the algorithm in the manner of a textbook with text and pictures. Alternatively, this can also be conveyed through a previous lecture. Display of the pseudocode. In addition to the data structures, the pseudocode of the algorithm is displayed. The current command line is highlighted. In this way, the 88 learner can relate the pseudocode and the actions on the data structures to one another. Explanation of the steps. The steps of the algorithm are commented on in text form or by voice output so that the learner understands what the algorithm is currently doing. Interesting input data. Many algorithms show a special behavior with certain input data. The sorting algorithm Quicksort shows z. B. with presorted input data a different runtime behavior than with randomly mixed input data. The learner is given the various sets of input data to choose from. Small amount of data. The animation works on a small number of data objects. The number is just chosen so that the essentials can still be seen in the algorithm. Large amounts of data make it difficult to perceive and understand. Normally, they do not provide any additional information. Cognitive psychologists have found in tests that humans can typically hold 7-9 units (\? Chunks) in working memory. Therefore, no more than 7 objects should be actively involved in an algorithm step. Just a few steps. Analogously, only as many repetitions of loop runs are shown as are necessary for perception and understanding. Otherwise the learner will quickly become bored and his capacity for attention will be unnecessarily used up. Flexible process control. The animation of the algorithm can be controlled in a similar way to a video recorder: single steps forwards and backwards, play, pause, stop, jump to the beginning and end. From a didactic point of view, it is particularly important to be able to switch back and forth in individual steps. Beginners in particular who are learning the algorithm from scratch are usually overwhelmed with a continuous film. Since normal programs cannot run "backwards", this places special demands on the software architecture of the interactive visualization. Interesting events. One step includes an "interesting event" of the algorithm. This can be B. be an action of the algorithm or the achievement of important intermediate results. In contrast to this principle, some software visualization systems turn graphic operations into steps. The concept of \? Interesting events “was developed by Marc Brown [Br87]. Focus attention. The learner's gaze is drawn to the parts of the representation that will change next. For this purpose, the author can e.g. have these objects blink or change their size. This prevents the observer from perceiving important steps only as a diffuse movement. Soft transitions. Changes to the data structures are shown with soft, flowing movements as far as possible. If, for example, two elements of an array are swapped, they can each move on a semicircular arc and thus "swap places". This makes the process easier to perceive. So that the learner does not get the impression that the data is "moving" in a computer, the accompanying text should indicate how the change in the data is implemented. Swap is z. B. realized via "sudden" copying processes in triangular exchange. One of the main goals in the development of the Tango software visualization system was to enable animations with smooth transitions [St98b]. Example Fig. 1 Learning by looking: Bubble sort animation I am not aware of any algorithm animation that implements all of the principles mentioned. The authors of the animation of the bubble sort algorithm (Fig. 1) wanted to develop an aesthetic animation that takes up the metaphor "air bubbles" (Bubbles) [Ba98]. You have implemented the following principles: $ \ bullet $ Soft transitions $ \ bullet $ Flexible sequence control $ \ bullet $ Display of the pseudocode $ \ bullet $ Small amount of data $ \ bullet $ Teaching text Algorithm exercises After an algorithm has been learned by watching an animation knowledge should be checked and deepened through practice. During an exercise, the student has to predict the next step of the algorithm several times. There is only one "correct" next step, and that is the one that the standard algorithm would perform next. To do this, the student interacts with a visualization of the data structure via a graphical user interface. There seem to be only a few projects that have developed such interactive visualizations ([SSN99], [Bl99], [Fa00]). 90 Desirable features The desirable features for animations that I have given for learning by "viewing" also apply to learning with algorithm exercises, except for the point \ "Display of the pseudocode". The following characteristics should also be present. No pseudocode. Since the student is supposed to predict the next step independently, no pseudocode is displayed. In particular, the character of the examination of knowledge would otherwise be undermined. Use GUI. The possibilities of a graphical user interface (GUI) are used as far as possible and sensible for interaction. In particular, the student can directly select data objects in the graphic of the visualization (e.g. click with the mouse). One step of an algorithm often consists of calling a function. The functions can e.g. be represented by buttons. The student calls a function by first clicking the objects (current parameters) in the graphic and then the button of the function. Simplify operation. The task is designed to be as simple as possible. It is easy to see which functions are offered and which objects can be selected. The student only has to select objects and functions. Operating errors should be reported as such. The operation should be described (e.g. as online help or in the accompanying text). Make solution difficult. There are z. B. more functions are offered than are actually required. If possible, all objects of the visualization can also be selected. This makes it difficult to guess the next step. Error messages and multi-level help. If the student chooses a wrong function or wrong parameters, it can be useful to justify why this function call does not make sense now. In most cases, however, it will be sufficient to report that the algorithm would perform another step. However, it should be possible to call up multi-level help that provides information on what to do and, as the next level, indicates the step directly. 91 Example Fig. 2 Learning by practicing: Merge function An example of learning by practicing is the applet from the learning software for the binomial heap algorithm (Fig. 2) [Bl99]. In it, two lists of binomial trees are to be merged into one result list. This is done in a similar way to written adding. The student must follow the steps of the standard algorithm exactly, but can call up one-step help using the "Tip" button. The above criteria are largely met. Algorithm simulations Algorithm simulations allow free experimentation with functions and data objects. This should enable the student to "rediscover" the algorithm. The algorithm is not conveyed to the student as a finished work, but is intended to repeat part of the work of development and discovery. This puts him in the role of an algorithm developer. The "experiment" form of learning, like other forms of learning, must be embedded in a larger didactic context. For the design of learning software for algorithms, I have developed the didactic concept "Structured active learning of algorithms (SALA)" [Fa99]. As I understand it, an algorithm consists of the following structures: 1. Static and dynamic structure of the data (e.g. lists, references, records / structs) 92 2. Mathematical and logical conditions between data objects, the so-called invariants 3. Functional structure 4. Pseudocode of the individual functions The functional structure of an algorithm indicates which functions the algorithm is divided into and which functions call each other. The following must be specified for each function: $ \ bullet $ Purpose of the function $ \ bullet $ formal parameters (type and role) $ \ bullet $ Start invariants that must apply when the function is called so that the function can work. $ \ bullet $ Work invariants that must be taken into account while the function is working. This partly expresses the "strategy" according to which the function works. $ \ bullet $ Target invariants that must apply at the end of the function. These are derived from the purpose of the function and from the prerequisites (chronologically) of subsequent functions. One cannot expect a student to develop (rediscover) the algorithm himself if he has not been taught essential parts beforehand. I suggest teaching points 1 to 3 (structure of the data, invariants and functional structure) and letting the student develop the pseudocode himself. The pseudocode determines which steps the algorithm performs on a specific set of data. Conversely, by trying out steps, the student can feel his way forward to data on the generally functioning pseudocode. It can be assumed that aimless trial and error does not help much, but that he has to come up with a strategy that he can try out and refine through experimentation. Compared to learning through "practicing", the student works with "experimenting" with a real simulation, in which alternative steps are usually possible based on a situation. There can be several ways to get there. The progress of the processing should be shown in the visualization, so that the student can see where "the work is done" and how close he has come to the goal. The simulation enables the student to experiment. For this purpose, it provides several functions that can be used on the data objects. However, it only executes a function call if the work and start invariants allow this. Desirable features The user interface of the algorithm simulation is similar to that of the algorithm exercise. In addition to the criteria mentioned there, the following characteristics should be met: Content-related error messages. If the student tries to call up a function whose start invariants are not fulfilled or if this would violate a working invariant 93, the interactive visualization must reject this with an error message. The error message should state the reason for the invariants. Progress indicator. The student can see how close he has come to the goal. For example, the visualization can show which part of the data already fulfills the target invariant. Undo. It may well be that the student takes steps that do not violate the invariants, but do not lead to the goal. The student can take back individual steps using an undo mechanism. Example Fig. 3 Learning through experimentation: "Build-Heap" function Fig. 3 shows a screenshot of a simulation of the "Build-Heap" function from the Heapsort algorithm [Fa00]. The student should select a node in the tree and then start one of the functions from the button bar. For the correct solution, the unordered nodes must be ordered bottom-up with Heapify. This simulation offers error messages, progress indicators and undo. The applet can also be switched to the "practice" and "animation" modes.


Full Text: PDF