dpvis

The topic of dynamic programming (DP) is particularly challenging for learners newly introduced to algorithm design. The library will serve as a learning aid for studying DP. To this end, we design a widely accessible library that can be used by students to visualize and interact with DP algorithms.

The ultimate goal of this library is not to implement visualization for any finite collection of DP problems. Instead, the library will have the capacity to visualize any DP algorithm, provided that the algorithm is implemented correctly.

Our visualization library works with native Python implementations of DP.

The library has three major features:

• Capability to illustrate step-by-step executions of the DP as it fills out the dynamic programming array. This includes visualization of pre-computations and the backtracking process.
• Interactive self-testing feature in which the user will be quizzed on which cells will be used to compute the result, which cell will the result be stored, and what is the value of the result.

Installation

NOTE: This instruction should be updated after we release to PyPI.

1. Clone the fork locally and change directory:

   # With SSH:
   git clone git@github.com:itsdawei/dpvis.git
   
   # Without SSH:
   git clone https://github.com/itsdawei/dpvis.git
   
   cd dpvis

2. There are a few options to managing virtual environment:

   • (Recommended) Install Conda and install the library locally via pip:

     conda create -n dpvis python=3.11
     conda activate dpvis
     pip install -e . # Do not omit the '.' at the end

   • Alternatively, install Poetry and run:

     poetry install

   • Although highly recommended, a virtual environment is not necessary as long as you have Python 3.8+ and a Python package manager such as pip. In this case, you can install the library directly with:

     pip install -e . # Do not omit the '.' at the end

3. You can verify the installation by running one of our many demos.

   python demos/knapsack.py
   
   # With Poetry
   poetry run python demos/knapsack.py

4. Open http://127.0.0.1:8050/ with your favorite browser. (Make sure that it is "http" and not "https")

Documentation

The documentation is compiled with mkdocs-material and mkdocstrings

To serve the documentation locally, run

poetry install --with docs
poetry run make servedocs

Contributors

dpvis is developed and maintained by

• Ramiro Deo-Campo Vuong
• Eric Han
• David H. Lee
• Aditya Prasad
• Tianyu Wang

License

dpvis is released under the MIT License.