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.
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:
Publications:
Dagstuhl seminar on Software
Visualization
Presentations:
Links:
