Description

Think back of the courses on Basic Models in Computer Science (BaMI), Algoithms, Data Structures and Complexity (ADC) or Concurrent and Distributed Programming (CDP). Almost all algorithms presented in any of these courses are at some point or another explained by drawing pictures of data structures as graphs and visualising the steps of the algorithm as changes in the graphs. This can provide a very valuable perspective, in addition to textual, mathematical or pseudo-code descriptions of the algorithm.

Graph transformation is a technique in which this kind of visualisation can be completely formalised and brought to life. You can specify rules that operate on graphs and correspond precisely to the steps of the algorithms, and you can execute those rules on concrete instance graphs, thus exploring all steps of the algorithm in detail.

In this assignment, you will create a library of such visualisations, for a set of the algorithms taught in the aforementioned courses, You will do this using the graph transformation tool GROOVE, developed at the FMT group. The precise set of algorithms is yet to be determined, and will depend on your own progress. The intention is that this library can be used in the courses themselves, as an aid to students to understand the material.

References

1. The graph transformation tool GROOVE (Digital version available here)

Additional Resources

1. The paper