Abstract
Algorithms are a fundamental part of computer science education, with expressing and tracing forming key aspects of their study. Both pseudocode and code are used to express algorithms. Pseudocode helps abstract away specifics of the programming language when specifying an algorithm, but it can introduce ambiguities due to its informal nature and does not support a structured way to trace an algorithm. On the other hand, tracing a program provides a precise description but can conflate algorithmic logic with language-specific details, obscuring the inherent structure of an algorithm.
In this experience report, we propose employing the Mapcode framework for expressing and tracing algorithms. Mapcode represents an algorithm as a set of transformations between well-defined spaces, naturally producing execution traces that are independent of programming constructs. Unlike traditional notional machines, which model the execution of programs, Mapcode machines model the high-level execution of algorithms. Mapcode traces reflect underlying logic and are independent of programming-language-specific data and control structures like while loops.
We report preliminary findings from two classroom activities which explored the application of Mapcode to express and trace algorithms. In the first activity, third-year undergraduate students drew Mapcode Execution Diagrams to trace simple algorithms already specified in the Mapcode framework. We found that a majority of students were successful in constructing the diagrams. In the second activity, students in a Principles of Programming Languages course successfully defined algorithms from various paradigms (greedy, dynamic programming, sorting, etc.) as Mapcode machines and implemented them in Python and Racket.