---
tags: labs, spr22
---
# Lab 9: Dynamic Programming

## Assignment Link
Use this [GitHub Classroom link](https://classroom.github.com/a/qSlTuM69) to get the stencil code for this assignment.

## Setup

If you're having trouble with VSCode, check out our [First Time Setup Guide](https://hackmd.io/@csci0200/software-setup-s22) and these [folder setup instructions](https://edstem.org/us/courses/16807/discussion/1309739).

## Problem Description


You have to plan a (less than [a thousand-year](https://www.youtube.com/watch?v=rtOvBOTyX00)) bike trip to Boston from the CIT. You already know the route you want to take. You are only able to travel up to a certain distance before you have to stop for snacks (and it's probably less than [a thousand miles](https://www.youtube.com/watch?v=Cwkej79U3ek)). You also have a limited food budget, so you have to figure out the best places to stop while minimizing your budget. [Watch your price tag](https://www.youtube.com/watch?v=qMxX-QOV9tI)! You will eat at CIT before you head out, but you still need to plan the rest of your stops.

Here's a sample map of the route and the (evenly-spaced) stops along the route. Each stop is labeled with the cost of your favorite snack at that stop.


You could choose to get a snack at every store, but that would cost you $$1 + 2 + 5 + 2 + 4 + 3 = 17$$ dollars. If you knew that you could skip over one store after eating, you'd have several possible options, such as:

- CIT, Store2, Store3, Store5 (cost is $1 + 5 + 2 + 3 = 11$)
- CIT, Store2, Store4 (cost is $1 + 5 + 4 = 10$)
- and so on

Note that you don't *have* to skip a store: you could stop at the next store, or skip it and stop at the next. Your goal is to figure out which set of stores to visit in order to minimize your snack costs.

***Note:** this is a different form of route-search problem than we did on graphs. There, we were trying to find some way to get from one place to another. Here, *we already have the route*, but we need to plan how to *use some resource along that route*. It's still a search problem, but of a different flavor.*

In this lab, you are going to develop two programs to find the sequence of stops with the lowest total cost, as well as the corresponding list of stores to stop at. We will do this as we did in lecture, first by understanding the tree of all options, then by writing a recursive version of the program, then by optimizing that recursive version to avoid repeating computation.

### The Tree of Options

To understand the problem, let's draw out all the possible collections of stops to get from CIT to Boston. We will organize this as a tree where we start from CIT. At each tree node, we have multiple possible "next stops", depending on the distance rule. If our allowed distance is 2, then there are two options from each node (visit the next stop or skip the next stop and visit the one after that).

Here is the start of a tree drawing out the possible stop sequences that respect our rule or skipping at most one stop after each stop along the way. The red numbers are the costs of snacks at each stop. Store4 is boxed off because it is a leaf (being within one skip from Boston):


**Task:** Complete the diagram.

**Task:** Inspect your diagram. What is the cheapest total cost? Which collection of stops (including CIT, where we have agreed we will eat before leaving) yields that cost?

Now we want to **compute that minimum cost algorithmically**. We will do this by working from the bottom of the tree upward, labeling each node with the lowest-total-cost incurred from that point to the destination (bottom of the tree).

**Task:** The lowest cost incurred at each leaf is just the cost of snacks at the corresponding store. Now, consider a node one level up from the leaves: what is the cheapest cost and how can we compute it? *Hint: use min and consider the costs at the leaves that are one level down.*

**Task:** Pick a node one more level up (two from the bottom). What is the cheapest cost from that node? How did you compute it? Do you spot the pattern?

**Task:** Complete the following statement:

*The optimal cost at a node is ___________ + the minimum of __________*

:::spoiler Here's the final labeled diagram that you should have come up with

In this version, the red numbers are the snack costs per stop. The circled blue numbers are the optimal costs at each node. The yellow highlight shows the best path if we are allowed to skip at most one stop along the way.

:::

### Turning our Algorithmic Ideas into Code

The tree gives you the idea of how we could do this computation. Now, we have to turn that into code.

We could build the tree as an explicit data structure and traverse it from leaves to root as we just did by hand. That isn't necessary, however. Instead, we can effectively generate and label this tree by writing a recursive function. Each call to the function generates a node. The "edges" arise when one call is made within another.

Here is a code fragment that corresponds to generating the nodes and computing the minimal costs at each one:

def compute_optimal_cost(fromStoreNum):
   best_cost_next_store = compute_optimal_cost(fromStoreNum + 1)
   best_cost_skip_store = compute_optimal_cost(fromStoreNum + 2)
   return price_this_store + min(cost_next_store, cost_skip_store)

This corresponds to being at a store and computing the better option between the two stores we could visit next. Each call to `compute_optimal_cost` matches one node in the hand-drawn tree.

**Task:** Discuss and make sure you understand this recursive structure and how it aligns with the tree. If you have questions, call over a TA.

### Dissecting the Full Recursive Version

Open `TravelPlansRec.py` in the stencil code. This is the complete version of a recursive program to compute the optimal total cost, building on the recursive idea of the previous code fragment. To give you practice with classes, we have put the code within a class. There are two parameters to the `_init_` constructor:
- `distance` is the max number of segments you can travel without stopping (`distance` 2 means you can skip at most 1 stop).
- `snack_cost` is an array holding the costs of snacks per stop. CIT is in index 0, while index `N` holds the cost of `StoreN`.

**Task:** Inspect the code, and figure out how it performs the minimal cost computation that you worked out by hand. Specifically:

- Where in the code are the costs at the leaves determined?
- Where in the code are the costs at the intermediate nodes determined?
- Why is there a `for` loop in the `else` case of `optimal_cost_helper`?
- What about the code enforces the rule on the number of stops that one can skip before buying a snack?

Discuss any questions that you have about how this code works.

:::info
**Checkpoint!** Call over a TA to check over your work. Ask them any questions you have about how this works.
:::

**Task:** Run the code. Add tests to experiment with different distances (you can use the same example). Are you getting the minimal cost that you expected?

### Writing the Optimized Version (Dynamic Programming)

Look back at the tree that you drew earlier. Notice how some subtrees are repeated. For example, the subtree starting at `Store3` occurs three times. Each node for the same store has the same "optimal cost" label. Rather than compute the same stop's cost multiple times, what if we computed each one exactly once and saved the result? Better still, since we labeled the optimal costs on our tree from the leaves up, we can build up an array of optimal costs from each store, working backwards from the stops closest to Boston.

Let's make an array to hold the optimal costs at each stop.

**Task:** We have started the following table showing the array and how each cell is computed. Finish the table.

| Stop Name | Array Index | Optimal Cost |
| -------- | -------- | -------- |
| CIT | 0 | |
| Store1 | 1 | |
| Store2 | 2 | |
| Store3 | 3 | 5 (from snack_cost[3] + min-from-4-and-5) |
| Store4 | 4 | 4 (from snack_cost[4]) |
| Store5 | 5 | 3 (from snack_cost[5]) |

Now, we just need to write code to do this. Roughly, our code needs to:

- Create an array with as many slots as there are stops (the optimal cost for each stop is in the array index with the same number)
- Start at the end (largest index) of the array. For any slot within the allowed distance of the destination city, record that the optimal cost is the cost of snacks at that stop.
- Work backwards through the rest of the array slots, computing their values using the formula that you worked out on the diagram (which should look very similar to the store-cost-plus-min formula in the recursive version)

**Task:** Open the `TravelPlansDP` file in the stencil code. Fill in the body of the `fill_table` method according to the above steps.

**Task:** Now, fill in the body of the `optimal_cost` method. This is the method that will return the optimal cost from the entire trip (setting aside the set of stops).

**Task:** Use these methods to compute optimal costs on a couple of different distances. Print out the contents of the array in an interactive window and make sure the array has the values that you expect.
<!-- (remember, to print out an array in Python, we use `str`, as in `print(str(the-array))`) -->

### Computing the Optimal Set of Stops

So far, we have computed the optimal cost, but not the specific sequence of stops used to obtain that cost. Fortunately, doing this just requires us to save a little additional information, similar in spirit to how we have stored information to track the paths we came from in breadth-first search and Dikjstra's.

**Task:** The following array maps each store to the optimal cost path from that store to Boston. We store the route as a list of store numbers. Finish filling in the array (by hand)

| Stop Name | Array Index | Optimal Path |
| -------- | -------- | -------- |
| CIT | 0 | |
| Store1 | 1 | |
| Store2 | 2 | |
| Store3 | 3 | [3,5] |
| Store4 | 4 | [4] |
| Store5 | 5 | [5] |

**Task:** What's the relationship between the `opt_cost` and `opt_path` arrays? Discuss with your partner and finish this statement:

*The value in `opt_cost` is ________________________ the list of store numbers in `opt_path`*

**Task:** Expand your `fill_table` code to also fill in the `opt_path` array.

**Task:** Now, fill in the body of the `optimal_path` method. This is the method that will return the optimal cost from the entire trip (setting aside the set of stops).

**Task:** Use these methods to compute optimal costs on a couple of different distances. Print out the contents of the array in an interactive window and make sure the array has the values that you expect.
<!-- (remember, to print out an array in Python, we use `str`, as in `print(str(the-array))`) -->

:::info
**Checkpoint!** Call over a TA to check over your work.
:::

### Testing

**Task:** Make a testing plan. What are good examples to test here and why?

**Task:** Now that you have written this code two ways, you can check that both versions return the same results. This is a handy technique if you have an existing algorithm that you trust (either because you tested it extensively or because someone gave it to you). Write a series of tests that check the optimal costs computed by your DP version against the optimal costs computed by the recursive version.

**Task:** Discuss how you might use our earlier observation about the relationship between the arrays to help test whether the route computation is correct.

:::info
**Checkpoint!** Call over a TA to check over your testing and you're done!
:::

______________________________

*Please let us know if you find any mistakes, inconsistencies, or confusing language in this or any other CSCI0200 document by filling out the [anonymous feedback form](https://docs.google.com/forms/d/e/1FAIpQLSdFzM6mpDD_1tj-vS0SMYAohPAtBZ-oZZH0-TbMKv-_Bw5HeA/viewform?usp=sf_link).*