**Algorithm Explanation (AE)**

Joint work with Drs. E. Shakshuki (Acadia University) & Andreas Kerren (Kaiserslautern), and several undergraduate students.

Last update: January 25, 2006

An algorithm is one of the most basic concepts in Computer Science, but understanding of algorithms
is often difficult. There has been extensive research on algorithm animations, showing how specific implementations
of algorithms are executed. This project is on algorithm *explanation*
rather than visualization; that is the use of structured descriptions and computer graphics to *explain* essential properties (invariants) of various algorithms.

Because of the importance of algorithms, for more than 15 years researchers have been trying to find the best way to teach algorithms. Visualization is considered as one of the best known approaches to use; especially its understanding as "the power or process of forming a mental image of vision of something not actually present to the sight". Software visualization has grown from early flow-charts to current sophisticated graphics workstations showing 3D visualization of complex software systems. It uses various kinds of multimedia, including graphics to show abstractions of data, animation and video to convey the temporal evolution of a computer algorithm, and voice, also called auralization.

Unlike existing algorithm visualization systems, our model concentrates on algorithm *explanation* and it reflects the structure of an algorithm. We define this structure
as a directed graph of abstractions. Each *abstraction* is designed
to focus on a single operation used directly or indirectly in the algorithm, and it provides an Abstract Data Type,
ADT, which gives a high-level view of generic data structures and operations. *Operations* are provided in a textual form, but there is also a hyperlinked visual description used to help the student
to understand basic properties of the algorithm; for example algorithm invariants. Each ADT operation is either
implemented in an abstraction at the lower level, or it is a *primitive* operation. This approach supports the novel mode of studying not available in any other visualization
system; namely an algorithm may be studied top-down, bottom-up, or using a mix of the two.

A hierarchical Abstract Algorithm Model (AAM) is a DAG, which consists of abstractions representing operations. Each abstraction explains a single operation op(), and consists of a textual representation and a visual representation. The textual representation includes an ADT that provides data types and operations. It also provides a representation of the operation op() using the ADT from this abstraction.

To explain this concept, let's assume that f() is an operation. The abstraction that explains f(), abst(f) is a pair (ADT, representation of f() in the ADT), where ADT consists of data types and primitive operations; see the figure below:

There is an edge from the abstraction abst(f) to an abstraction abst(g) if g is one of the primitive operations from the ADT abst(f). Therefore, a child abstraction provides a partial implementation of the operation from the parent abstraction. Typically, there are only few operations from any abstraction's ADT that are implemented in a child of this abstraction; others are considered primitive operations. An AAM of an algorithm f() is a graph rooted at abst(f). To explain an algorithm, we construct an AAM graph with sufficient number of levels so that the student is able to understand how and why the algorithm works (in particular, the student can form and justify invariants of the algorithm.) For example, to explain Insertion Sort, we would use the explanation graph shown in figure below:

.

A *taxonomy* of all explanations has a tree-like
structure. Non-leaf nodes of the taxonomy represent concepts, such as "Iterative Algorithms" (the root
represents all algorithms). Leaves represent explanations of specific algorithms, created by specific authors,
for example "John Doe: Merge Sort". The author who creates an explanation of a new algorithm specifies
where in the taxonomy hierarchy this explanation will be placed.

**SHALEX **Structured Hypermedia Algorithm Explanation System

The current version of SHALEX is designed based on client-server architecture and provides a web-based algorithm explanation system. The users can play one of the following four roles:

- learners, who study algorithms;
- authors, who are responsible for tasks such as creating algorithm explanations,
- algorithm administrators, who are responsible for tasks such creating lessons, or assigning evaluations;
- administrators, who are responsible for tasks such as maintaining user accounts, groups of users, and their roles.

Dagstuhl seminar on Software Visualization

- Explaining Algorithms: A New Perspective. T. Müldner, E. Shakshuki International Journal of Distance Education Technologies (JDET). 2006. Accepted
- Tomasz Müldner, Elhadi Shakshuki, Andreas Kerren, Zhinan Shen, Xiaoguang Bai. Using Structured Hypermedia to Explain Algorithms. IADIS e-Society 2005.
- T. Müldner and E. Shakshuki. A new Approach to Learning Algorithms. Proceedings of the International Conference on Information Technology (ITCC2004), IEEE Computer Society, pp. 141-145, 2004. Las Vegas, USA.
- T. Müldner, E. Shakshuki and J. Merill. Yet another Way to Explain Algorithms. The 7th IASTED International Conference on Computers and Advanced Technology in Education, CATE 2004, August 2004.
- T. Müldner and E. Shakshuki. On Visualization and Implementation of Algorithms. Proceedings of the 5th International Conference on Information Technology Based Higher Education and Training (ITHET'04), IEEE Computer Society, pp. 138-143, Istanbul, Turkey, 2004.
- E. Shakshuki, T. Müldner and B. Haughn. ATIA: Algorithm Teaching Interface Agent. Proceedings of the 5th International Conference on Information Technology Based Higher Education and Training (ITHET'04), IEEE Computer Society, pp. 138-143.
- T. Müldner, E. Shakshuki and J. Merill. Selecting Media for Explaining Algorithms. AACE Proceedings of EDMEDIA'04; Lugano, Switzerland, pp. 2048-2053.
- R. Wilhelm and T. Müldner Using Compile-time Techniques to Generate and Visualize Invariants for Algorithm Explanation. Proceedings of the Second Program Visualization Workshop: HornstrupCentret, Denmark, June 27-28, 2002. Published by DAIMI PB-567, 2002, M. Ben-Ari (ed.), pp. 23-27.

**Presentations:**

**Links**: