Algorithm Explanation (AE)

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

Last update: January 25, 2006

Short description

Longer description

Current state


Short description:

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.

Longer description:

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.

Current State

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:

Dagstuhl seminar on
Software Visualization
  1. Explaining Algorithms: A New Perspective. T. Müldner, E. Shakshuki International Journal of Distance Education Technologies (JDET). 2006. Accepted
  2. Tomasz Müldner, Elhadi Shakshuki, Andreas Kerren, Zhinan Shen, Xiaoguang Bai. Using Structured Hypermedia to Explain Algorithms. IADIS e-Society 2005.
  3. 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.
  4. 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.
  5. 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.
  6. 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.
  7. T. Müldner, E. Shakshuki and J. Merill. Selecting Media for Explaining Algorithms. AACE Proceedings of EDMEDIA'04; Lugano, Switzerland, pp. 2048-2053.
  8. 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.


CATE 2004