Theory Lunch This Week (12:00, 10/31, SAL 322) (DISREGARD PREVIOUS EMAIL)
Grayson York
This week I will introduce dpvis, an open-source library for
generating interactive visualizations for arbitrary 1D and 2D
dynamic programs (in Python). The talk will be structured as
follows: (1) I will give an overview of the design principles that
enables easy adoption of our library, (2) I will report the
user-study we performed on USC's undergraduate algorithm class
CSCI-270, and (3) I will give a demo of the important
functionalities of the dpvis. Although this is a bit of a
divergence from traditional topics at theory lunch, those who are
interested in learning about *how to teach dynamic programming
better* may find this talk instructive.
Paper Title:
David H. Lee, Aditya Prasad, Ramiro Deo-Campo Vuong, Tianyu Wang, Eric Han, David Kempe
Technical Symposium on Computer Science Education (SIGCSE TS), Feburary 2025.
Paper Abstract:
Dynamic programming (DP) is a fundamental and powerful algorithmic paradigm taught in most undergraduate (and many graduate) algorithms classes. DP problems are challenging for many computer science students because they require identifying unique problem structures and a refined understanding of recursion — another difficult topic in computer science. In this paper, we present dpvis, a Python library that assists students in understanding DP via a frame-by-frame animation of dynamic programs. dpvis can easily generate animations of dynamic programs with as little as two lines of modifications compared to a standard Python implementation. For each frame of the animation, dpvis highlights the cells that have been read from and written to during an iteration. Moreover, dpvis allows users to test their understanding of an algorithm by prompting them with questions about the next operation performed by the algorithm. We deployed dpvis as a learning tool in an undergraduate algorithms class, and report on the results of a survey. The survey results suggest that dpvis is especially helpful for visualizing the recursive structure of DP. While some students struggled with the installation of the tool (which has been simplified since the reported deployment), essentially all other students found the tool to be useful for understanding dynamic programs. dpvis is available at https://github.com/itsdawei/dpvis.