FRI-2G.303-1-CCT1-03
DYNAMIC PROGRAMMING VISUALIZER
Abstract
Dynamic Programming (DP) is a complex and challenging algorithm design technique. This report presents a specialized educational tool designed to help students understand the DP paradigm. A visual tutor has been developed that interactively demonstrates the two fundamental dynamic programming approaches - Bottom-up Approach and Top-Down with Memoization Approach, specifically for 0/1 Knapsack Problem. Students can follow the DP technique step by step, visualizing the DP table as it is populated and observing the transitions between cells. Hovering over each cell provides an explanation of how its value was derived. Additionally, the tool allows users to track the execution of an algorithm by displaying its source code. The visualization system also includes a testing mode, which highlights incorrectly filled cells and offers hints for the correct values and their calculations. By providing visualization and guidance, this educational tutor aids students in effectively learning DP strategies and enables lecturers to focus more on explaining the underlying concepts rather than generating tables in class.
Keywords
Dynamic Programming, 0/1 Knapsack Problem, educational tool
REFERENCES
- Algorithm Visualizer (2024). Available at: https://algorithm-visualizer.org/dynamic-programming/knapsack-problem.
- Alsuwaiyel, M. (2010) Algorithms: Design Techniques and Analisys. World Scientific Publishing.
- Cormen, T. H. et al. (2012) Introduction to Algorithms. Third, Computer. Third. Edited by PHI Learning. The MIT Press. doi: 10.2307/2583667.
- Dasgupta S., C. Papadimitriou and U. Vazirani (2007) Algorithms. McGraw-Hill Higher Education.
- Dynamic Programming Visualization (2024). Available at: https://dynamic-programming.debkbanerji.com/problem/knapsack-without-repetition.
- Interactive algorithms. Solving big problems by combining small decisions Dynamic programming. Knapsack 01. (2024). Available at: https://hope.simons-rock.edu/~mbarsky/utor/explorables/OWL/issue1_30112015/knapsackexplore.html. Knapsack Algorithm Visualization (2024a). Available at: https://monicagranbois.com/knapsack-algorithm-visualization/.
- Knapsack Algorithm Visualization (2024b). Available at: https://rose-paul.github.io/DP_vizualization/.
- Knapsack Visualizer (2024). Available at: https://knapsack.masao.io/.
- Levitin, A. (2012) Introduction to Design and Analysis of Algorithms. Third. Pearson.
- Price, B., Baecker, R. and Small, I. (1998) ‘An introduction to software visualization’, Software Visualization, pp. 3-27.
- Ramani, K. V. and Rama Rao, T. P. (1994) ‘A graphics based computer-aided learning package for integer programming: The branch and bound algorithm’, Computers & Education, 23(4), pp. 261-268.
- Shaffer, C. A., Cooper, M. and Edwards, S. H. (2007) ‘Algorithm visualization: a report on the state of the field’, in SIGCSE ’07: Proceedings of the 38th SIGCSE technical symposium on Computer science education, pp. 150-154. doi: 10.1145/1227504.1227366.
- Velázquez-Iturbide, J. A. Debdi, O., Esteban-Sánchez, N. and Pizarro, C. (2013) ‘GreedEx: A visualization tool for experimentation and discovery learning of greedy algorithms.’, IEEE Transactions on Learning Technologies, 6(2), pp. 130-143.
- Velázquez-Iturbide, J. Á., Pérez-Carrasco, A. and Urquiza-Fuentes, J. (2009) ‘A design of automatic visualizations for divide-and conquer algorithms’, Electronic Notes in Theoretical Computer Science 224, pp. 159-167.
- Yi, J. S. et al. (2008) ‘Understanding and characterizing insights: how do people gain insights using information visualization?’, in 2008 Workshop on BEyond time and errors: novel evaLuation methods for Information Visualization, pp. 1-6. doi: 10.1145/1377966.1377971.