Dynamic Programming

Explore an Innovative Algorithmic Paradigm
Published

March 18, 2024

Exploration

  • Read chapters 9 and 10 in A First Course on Data Structures in Python
  • Explore algorithms that use recursion and dynamic programming in the ds2 package of donsheehy/datastructures. Can you add debugging statements to trace how these algorithms work?
  • Read chapter 9 for a review of recursion and how it works in the Python language
  • Design, implement, and test your own efficient implementation of the lcs function!

Activities

  • Monday and Wednesday: Dynamic Programming
    • Explore how to implement recursive functions in Python
    • Investigate a new algorithmic paradigm called dynamic programming
    • Learn more about the longest common sub-sequence problem
    • Examine Python source code segments to illustrate key points
  • Thursday: Start new algorithm engineering project
  • Friday: Present results from an algorithm all-hands project

Project

Goal

To build and use a Python program, called listconcatenator, that runs benchmarks to study the performance of combining data into different types of lists

Steps

  • Use listconcatenator as your template repository
  • Install the project’s dependencies using devenv
  • Follow the instructions to complete the project:
    • Week 1: Implement all of the modules in listconcatenator
    • Week 2: Design and conduct experiments and document experimental results
  • Schedule office hours if you have questions

Slides

Full Screen: Week Ten: Recursion and Dynamic Programming

Back to top