Systematic Development of Dynamic Programming Algorithms Assisted by Interactive Visualization
J. Ángel Velázquez‐Iturbide, Antonio Pérez-Carrasco · 2016
Dynamic programming is an algorithm design technique that is very difficult to learn. In this paper, we introduce an extension of the recursion visualization system SRec, intended to support some phases of the systematic development of dynamic programming algorithms: generation of recursion trees, checking redundancy in an adequate recursion tree, generation of the dependency graph associated to that recursion tree, and matching the graph to a table. These facilities require high degree of interactivity to be effective. We have successfully applied the new version of SRec to a number of dynamic programming algorithms in an algorithm course. We have also evaluated the performance of two groups of students in a recursion removal task: an experimental group using SRec and a control group using traditional means. Many of the results were similar for both groups. However, the experimental group did the task with higher confidence and was more efficient in some issues, while the control group was more persistent in one task.