Dynamic Programming in OR

Topic outline

• Dynamic Programming Open Course
  

  Dynamic Programming Open Course

  Contributors : Nadia Brauner (Université Grenoble Alpes), Hadrien Cambazard (Grenoble INP), Nicolas Catusse (Grenoble INP)
  

  Contact : Hadrien Cambazard
  

  • One idea, one story: why is dynamic programming dynamic ? Page
  • Vous devez être inscrit dans le cours pour avoir accès à l'éditeur des exercices de programmation (une fois connecté, si vous voyez encore ce message, utilisez la roue dentée en haut à droite).

  • ---

    Course supports

  • Slides on Dynamic Programming File
  • Chapter 6, Dynamic programming URL

    In the book Algorithms by Dasgupta, Papadimitriou and Vazirani

• Exercices and activities
  

  Exercices and activities

     

  • Be able to write a recurrence formula and the basis cases in dynamic programming

    Know the algorithm for the knapsack and its extensions (larger subset of coins, integer knapsack)

  • Dynamic Programming exercices (with correction) Quiz
  • Self training (the stars indicate the level), le forgeron

  • Giving change Virtual programming lab
  • Kukulkan Virtual programming lab
  • The lab Knapsack is a complete example so students can get familiar with the framework for implementing dynamic programs. It matches the notations and example of the Dasgupta, Papadimitriou, Vazirani book. A simple object model is introduced for the representation of the data (usually two classes) as well as a class PdynSolver.java representing the dynamic program by its states (i.e the DP tables are stored as attributes). The purpose is to get the students familiar with object models that are required for more complex subjects where a model for the data becomes necessary. This framework is also used in the labs Kukulkan and Load Balancing.
  • Knapsack Virtual programming lab
  • Load Balancing Virtual programming lab
  • Hotels* Virtual programming lab
  • Keeping Water**** Virtual programming lab
  • Cutting Cloth** Virtual programming lab
  • Christmas Dynamic Challenge *** Quiz