Tracing Algorithms

Dr. Michael Goldwasser walks through the logistics and benefits for instructors and students in upgrading from static images to interactive animations and question sets. Increase student success in this rigorous series of Data Structures & Algorithms, now with interactive zyVersion.

Limitations of the Traditional Static Image

Tracing and simulating steps of an algorithm is an important student learning outcome of data structures and algorithms courses.  In this piece, we demonstrate how the zyBooks platform allows us to use techniques that actively engage students in the learning process.

Consider, for example, the partition step of an in-place quicksort. A lesson begins with a high-level description of the process, perhaps with code or pseudocode to be more tangible. In our print book, the code is followed by this multipart image.

We hope students can review the figure, understand how the process unfolds, and even make connections between the figure and the implementation of the process, such as the role of the indices r and l in this figure.

Animation with Side-by-Side Code Trace

This traditional static image has been replaced by a more polished animation of the steps that the student can progress through or replay, and we can directly embed a side-by-side trace of the code.  Here is the animation for this lesson in the zyVersion of our Data Structures and Algorithms in Python title.

Question Set Confirms or Recalibrates Understanding

We follow our animation with a question set that is designed to lead the student through yet another trace of the algorithm. That series begins with a rather traditional-looking multiple-choice question asking about the first step of the algorithm:

These questions are meant as part of the learning, more so than for evaluation.  Students can reason about the correct answer, but even if they get an incorrect answer, we can provide a customized response that nudges them in the proper direction.  Since we know that students can click through to switch their answers, they will eventually get to the correct answer (whether or not they understood why).  Fortunately, we can explain that answer and include further diagrams that help students recalibrate their understanding.  In this case, the explanation of the correct answer includes a diagram, that matches the style of our earlier animation, to reinforce the process and prepare the student for success on the next question.

By the end of this series of questions, the student has been led through another trace of an entire run of the algorithm.

We use a similar approach of embedding figures to trace other processes, such as the linear-time bottom-up construction of a binary heap.  Another approach to further engage students in the process of tracing algorithms relies on the use of Parsons problems, where students are presented blocks that show a variety of intermediate states and must order the blocks to reflect the progression.

To see these and further examples, see our Data Structures & Algorithms titles, in Java, C++, and Python.