Resumen de Using the SRec visualization system to construct dynamic programming algorithms

Jesús Angel Velázquez Iturbide , José Antonio Pérez Carrasco

• Dynamic programming is a demanding algorithm design technique. In this article, we introduce an extension of therecursion visualization system SRec, intended to support dynamic programming. The contributions of the chapter arethreefold. Firstly, we present SRec support to several phases of the systematic development of dynamic programmingalgorithms: generation of recursion trees, checking recursion redundancy in a recursion tree, generation of the dependencygraph associated to a recursion tree, and matching the graph to a table. These facilities require high degree of interactivityto be effective. The article illustrates these facilities with the construction of a dynamic programming algorithm for the 0/1knapsack problem. Secondly, we address several pragmatic issues: usage in educational scenarios, our experience withdynamic programming algorithms, and limitations. Thirdly, the article reports on the results of an evaluation of the systemusability. The results were very positive, providing evidence on the adequateness of extensions. Furthermore, they allowedidentifying minor opportunities for improvements.