Homework 5: Dynamic Programming - HedgeDoc

<style> h3 { border-bottom: 1px solid #ccc; } section { margin-bottom: 2rem; padding: 0em 1em; padding-bottom: 1em; border-radius: 4px; background-color: #f7f7f7; border: 1px solid #ccc; } summary { font-weight: bolder; } summary:hover { text-decoration: underline; } </style> # Homework 5: Dynamic Programming **Due:** Friday, November 17 at 11:59PM ET In this homework, you will gain some practice with dynamic programming and debugging. Concretely, you will work with two dynamic programming problems: - **Edit distance**: computing the "distance", required to transform one string into another, which is used in applications like spell checking - **Seamcarve**: an algorithm to find "seams" in images, which can aid in resizing images without losing important data For the first program, we have given you a *real* ChatGPT generated solution to this problem, but it's broken. In this assignment, build up your dynamic programming skills by learning about how edit distance works and then debugging and fixing this program. Afterward, you will build your own implementation for the core of the seamcarve algorithm. As you do both of these, you will build up good sets of test cases to help test your understanding and give you practice with testing against a well-defined specification. :::info **Note: Dynamic programming can seem challenging at first, but we are here to help!** This assignment has lots of resources, examples, and notes for how to get started and how reason about both programs before you get to the code. Take the time to read and work through these examples--we have spent a lot of time building them to help you! :::  # Learning Objectives - Use dynamic programming to produce efficient solutions to optimization problems. - Work with code produced by a large language model (ChatGPT), identify the approach it to solve problems, and fix its mistakes. - Use concrete examples, invariants, hand tracing, and debugging to explore or explain how a program works. - Comment code effectively. - Write programs that behave as expected based on a provided description or collection of test cases. # Setup You can download the stencil code using this **[Github Classroom](https://classroom.github.com/a/JDZpjXMm)** link. :::warning :warning: **Warning**: **Be sure to read the [**Python Stencil Setup Guide**](https://docs.cs200.io/s/python-stencil-setup-guide)** for important instructions on how to set up VSCode to use the stencil. In particular, **make sure you [set up your environment](https://docs.cs200.io/#Setting-up-your-environment)**--if you don't this, you won't be able to run any tests! ::: **Various other resources: you may find helpful** - **[Our Python Stencil setup guide](https://docs.cs200.io/s/python-stencil-setup-guide)**: for how to load the stencil - **[Our guide for going to Python from Java](https://docs.google.com/document/d/1wwOL1PsgdfeAzv77m6iBNzwX0m9HV5i_nJoKKZad_tY/edit?usp=sharing)** which includes links to the Python documentation that you should refer to - **[Our Python Testing Guide](https://docs.cs200.io/s/python-testing-guide)**: how to run and debug tests, as well as this [annotated VSCode debugging guide](https://brown-csci0200.github.io/assets/lectures/23python1/Lec25_whiteboard_f22.pdf) from lecture - **[Our Python Style Guide](https://docs.google.com/document/d/1yadShv9w5oe_NWIt4fDk-DG_neBIy0AdX4mer2S0O3A/edit?usp=sharing)**: how to format your Python code    # Grading 1. **Implementation** (50%): Your implementation is autograded. 2. **Testing** (50%): We are **not** grading your assignment using wheat and chaff grading this time! This is because there is only one substantial method that you write for each part of the assignment, without much room for edge cases that are not already taken care of by the structure of the problem and starter code. Instead of automated grading, we will ask you to document your example-writing process and manually grade you on your tests as well as your written justifications for the tests. # **Edit Distance** Applications, such as spell checkers and disease modeling, often need to know the differences between two strings. One way to describe the difference between two strings is how many edits are needed to transform one string into another. For the purposes of this exercise, an edit consists of the **substitution** of one single letter for another, the **removal** of a single letter, or the **insertion** of a single letter. We can transform "apple" to "opal" in three edits. 1. The **substitution** of `a` for `o`: **a**pple -> **o**pple 1. The **substitution** of a `p` for an `a`: op**p**le -> op**a**le 1. The **deletion** of the `e`: opal**e** -> opal Since we can't do any better than this, the **edit distance** between "apple" and "opal" is three. :::warning We treat uppercase and lowercase letters as the same, so the difference between “opal” and “OPAL” is 0. ::: From this description alone, ChatGPT has no problem generating (sometimes buggy) solutions. The stencil code has a file `edits.py`, with two of its solutions. We edited only the comments and the function names. ```python # compute the edit distance working from left to right def edit_distance_fwd(word1, word2): ... # compute the edit distance working from right to left def edit_distance_bwd(word1, word2): ... ``` <section> ### Task 1-A Develop a good set of test cases for this problem and put them in the `test_hw5.py` file in the stencil. Include a comment explaining why you think you have a good set of tests (did you come up with them systematically, do you have some other criterion for thinking this is a good set, etc). Use your tests to check the correctness of both Python programs. In a comment in your file, indicate which version(s) are working based on these tests. </section> ## How is Edit Distance Actually Computed? Let's investigate how edit distance is computed. Consider what it would take to find the edit distance between "apple" and "opal". To do this, we will decompose the problem `edit_distance["apple", "opal"]` into smaller subproblems. :::info :warning: **Note on notation**: In this document, `edit_distance[word1, word2]` is just the name we've given to the problem of finding the edit distance between `word1` and `word2`. It doesn't refer to a function call and it's not Python syntax. In fact, it is your responsibility in later tasks to identify how each part of the Python code in `edit_distance_fwd` and `edit_distance_bwd` solve subproblems of `edit_distance[word1, word2]`. ::: To find `edit_distance["apple", "opal"]`, we will break the strings up at the first letter `"a" + "pple", "o" + "pal"`. There are three possible edits involving the first letter of each word that we need to consider. ![](https://lh6.googleusercontent.com/iFl_HHEMkT_jU15d6EsPbQLahQfi__CEY1MOi0QoXkHnnSQ6BOyzSb0ZIiIGedc98UaqYhEmW9YUAK2SVjQz_Dn964lnjbhNjRZH4LL0AF3-oU_CfYDitwRRPga0GgScJDiOKX6sQsHTawVq27kbKwA) Since we are interested in the fewest number of edits between "apple" and "opal", we will select the minimum of the three possibilities: ```python edit_distance["apple", "opal"] == 1 + min( edit_distance["pple", "pal"], # substitue the first a for an o edit_distance["pple", "opal"], # remove the first a edit_distance["apple", "pal"], # insert an o at the start ) ``` There is one other case to consider. As an example, let's look at the subproblem `edit_distance["pple", "pal"]`. Like before, we'll break the strings at the first letter `"p" + "ple", "p" + "al"`. The first letters match (`"p" == "p"`), so no edits are needed to the first letter. ``` edit_distance["pple", "pal"] == 0 + edit_distance["ple", "al"] ``` <section> ### Stop and Think Identify edge cases for `edit_distance[word1, word2]`. What should we do? <details><summary>Check your work</summary> We haven't considered what happens when either word is empty. If `word1` is empty, `len(word2)` insertions are needed to build up the word. Another edge case occurs when `word2` is empty. In this case, `len(word1)` deletions are needed to transform `word1` into the empty string. In any case, if one word is empty, the edit distance is the length of the other word. </details> </section> Naively evaluating `edit_distance` in the recursive manner described in this section would be expensive, because the same subproblem will be considered by multiple branches.  Instead, let's solve the subproblems of `edit_distance` in a more structured manner. ## The Tabular Approach to Solving Edit Distance Once we find the edit distance for one of the subproblems, we will store the result in a table so that it doesn't have to be recomputed later. How big of a table do we need to store everything? For each subproblem `edit_distance[word1, word2]`, notice that we have broken the first letter off of the original `word1` some number (`i`) of times, and we have broken the first letter off of the original `word2` some number (`j`) of times. We can break off `0`, `1`, `2`, ..., or `len(word1)` letters from `word1`. Similarly for `word2`. Therefore the number of distinct subproblems is `(1 + len(word1)) * (1 + len(word2))`, and our table is a `1 + len(word1)` by `1 + len(word2)` 2D array. In dynamic programming, we store the result of each subproblem after it's computed in a structured way, allowing us to avoid doing the unnecessary work of evaluating identical subproblems multiple times. Our job is to fill every cell in the table`dp` with the solution to a distinct subproblem. When we're done, there will be a cell in `dp` that contains the solution of the overall problem. When we tackle a problem with dynamic programming, we must carefully choose the order to solve the subproblems. For edit distance, this manifests in the iteration order for the nested `for` loops. There is often some flexibility in this choice, which is why there are two variants for the solution: `edit_distance_fwd` and `edit_distance_bwd`. :::success ### :sparkles: Super helpful resources for this part :sparkles: <b>You should reference the following resources for assistance.</b> * This **[worked-out example](https://docs.google.com/document/d/1ho1QLYRFjn6_ToV7sJxcUrq5MfBej4SAUBSpRE1_rDI) developed by HTA Paul** shows how the cells in the table build on each other. * The lecture recording and notes provide an overview on strategies for dynamic programming.  * Try out **[this spreadsheet](https://docs.google.com/spreadsheets/d/1ojMRMESK1Oz5J12fLiHWstBLzLGFLvR35y4tfklE10w)** as a demo of how to run the **backward** variant. (To use it, go to File > Make a Copy to duplicate the spreadsheet, then edit your copy). You should only have to edit the light red cells for this task. You will know you’ve gotten the correct values if **all** of the cells (except for A2 and A4) are _white_. If a cell is unfilled, it will be light red, and if it is wrong, it will be dark red.  ::: <section> ### Task 1-B Improve your understanding by working through the concrete example `edit_distance["cods", "code"]`. You will do the **backward** variant. We’ve set up the table with the letters of each word around the edges to help you keep track of what the indices mean relative to the words. The `-` represents the end of the string (or the empty string). We’ve filled in the cell for converting `"s"` to `"e"`. Fill in the rest of the bottom row (so converting `"s"` to `"de"`, `"s"` to `"ode"`, etc), then move up and fill in the row above. As an example, for the cell with the **`W`**, you’ll use the three cells `x`, `y`, and `z`. What edits (**substitution**, **removal**, or **insertion**) do each of `x`, `y`, and `z` correspond to? | | **C** | **O** | **D** | **E** | - | | ----- | ----- | ----- | ----- | ----- | - | | **C** | | | | | | | **O** | | | **`W`** | `x` | | | **D** | | | `y` | `z` | | | **S** | | | | 1 | | | - | | | | | | There’s nothing for you to turn in here, but working through this is a key part of your understanding how this works. </section> <section> ### Task 1-C Now, return to the `edit_distance_bwd` code in `edits.py`. **Fill in the comments** as marked in the code file, explaining what each part of the marked parts of the code is doing. </section> <section> ### Task 1-D Using your confirmed `edit_distance["cods", "code"]` table, **write tests** in `test_hw5.py` to make sure `edit_distance_bwd` behaves as you expect. :::success **Hint**: *Use the table you just worked out to aid in debugging*!! ::: As you find issues, correct any problems in the ChatGPT solutions. Your final `edits.py` file should have correctly-working versions of both functions. In a comment, describe what sort of errors you found in the ChatGPT code. </section> # **Seamcarve** ## Problem Description The Seamcarve algorithm is used to resize (shrink) an image horizontally by removing “unimportant” pixels from the image. We can do this by finding vertical “seams” in the image representing the pixels that have the lowest difference in color from their neighbors and, thus, can be removed without significantly altering the image. More information on seamcarve can be found on the [Wikipedia page](https://en.wikipedia.org/wiki/Seam_carving) and in [this video](https://www.youtube.com/watch?v=c-SSu3tJ3ns). ![](https://lh3.googleusercontent.com/TkxHXOtp0x9bcF33vuQg1Dqkz5N7bnscDIR6HqUXs-W6Kldng-xFVknBKFCtjg3g9uLr09iW-rSb-ocWlHcdPyeOE7BynafPfn29VFtYlay4gjSYuSkiMEhEsMOIzMfdDMbvozYinm9xEtDhLsW66e4) ![](https://lh4.googleusercontent.com/mQ8c57rqsZu24odCMXLsniPunw3vmZEsiHlHmpdFBMY42z1ylbastAM5yu7iUC47YJnacIZ04jSaYIlio0W-sWTaKBiD3Nv1kdgY7WJy1J1ygcgisoWA2JESrnNrxk0VfpY2f3n45AGuJzOw5pdNU28) To resize an image, the Seamcarve algorithm completes two main steps: 1. **Finding the <u>importance value</u> of each pixel in the image.** This is determined by how much each pixel varies from its neighbors. It can be calculated as the average of the differences between its value and the value of each of its horizontal and vertical neighbors. These values are stored in a 2D list called an *importance array*. **We have already give you the code for this part** in the `ImportanceCalculator` class, which is used in the stencil by the `calculate_importance_values` method. 2. **Finding the <u>seam of least importance</u> in the image to be removed.** The _seam of least importance_ is defined by these constraints: there is exactly one pixel from each row in the seam, the seam is “connected” (for any row, the seam pixel of that row must border, diagonally or vertically adjacently, the seam pixel above and below it), and the sum total of pixel importances for this seam is the lowest out of all of the possible seams. This computation can be done using the data structures explained further below. These steps are repeated multiple times until the remaining image has decreased by the desired amount of width. :::warning **Note**: For this assignment, you will only be instructed to find vertical seams. ::: :::success ### Super helpful resource We have made an :sparkles: **[interactive spreadsheet](https://docs.google.com/spreadsheets/d/1m2EPDIkgNIzVJYUu9stEANX_7lDHlAruMP5O8Dj6_dU)** :sparkles: that shows these concepts in action. It may help to look at this interactive spreadsheet as you read through the next section for a bigger example than is provided in this handout. ::: ## `vals`, `costs`, and `dirs`: Data Structures to Find a Seam To aid us with our task, it will be helpful to define three 2D arrays: `vals`, `costs`, and `dirs`. ### **vals** Each cell in `vals` is a number representing the relative importance value of the corresponding pixel in the input image. The stencil code provides `vals` to you as a parameter of `find_least_important_seam`. We will work with the following `vals` array over the next section. | **vals** | | | | ---- | ----- | ----- | | 3 | 6 | 8 | | 5 | 7 | 2 | | 4 | 9 | 3 | <section> ### Task 2-A Make your own small (3x3, 3x4, 4x3, or 4x4) vals table. As you work through the `costs` and `dirs` computations by hand, also work through the computations on your own table. Put the computations for your own table in your `hw5_examples.pdf` file. </section> ### **costs** The costs array represents the minimum *cost*--or difference in pixel values--of a seam going through that cell in the image. Each cell of the costs array can be calculated using the following expression: ```python cost_below_left = costs[row + 1][col - 1] cost_below_mid = costs[row + 1][col] cost_below_right = costs[row + 1][col + 1] min_cost_below = min(cost_below_left, cost_below_mid, cost_below_right) costs[row][col] = vals[row][col] + min_cost_below ``` Intuitively, this looks at the minimum cost of the three pixels _below_ the pixel in question, and adds that to the importance value of the pixel in question. If we do this computation starting with the bottom row going upwards, that means that, in the top row, we will find the pixel that starts the seam with the least _total_ importance by finding the minimum value of `costs` in the top row. This is very similar to the trick-or-treating example done in class, except using a minimum instead of a maximum! :::warning As written, this code will result in an `IndexError` when run on the bottom row, the left column, and the right column. The bottom row represents the base case. The left and right columns are edge cases that you will need to handle carefully! :::  <section> ### Stop and Think Using the example `vals` array provided above, fill in its corresponding `costs` array. Remember to also do the same for the `vals` array you came up with! <table> <tr><td width="100px"><b>costs</b></td><td width="100px"></td><td width="100px"></td></tr> <tr><td style="padding-bottom: 20px;"></td><td></td><td style="padding-bottom: 20px;"></td></tr> <tr><td style="padding-bottom: 20px;"></td><td></td><td></td></tr> <tr><td style="padding-bottom: 20px;"></td><td></td><td></td></tr> </table> :::success <details><summary>Check your work</summary> | costs | | | | ----------- | ---- | ---- | | 12 | 11 | 13 | | 9 | 10 | 5 | | 4 | 9 | 3 | </details> ::: </section> <section> ### Stop and Think At which pixel (0, 1, or 2) of the top row will our seam start? :::success <details><summary>Check your work</summary> It will start at pixel 1, because that has the minimum costs value in the top row (11). Figuring out which pixel to start with is called an “argmin” problem. `argmin` looks through an array and returns the index of the minimum element of the array. </details> ::: </section> <section> ### Task 2-B Your implementation relies on a helper function called `argmin`. **Read** the docstring for `argmin` in `seamcarve.py`. In `hw5_test.py`, **write some test cases** for `argmin`. Then, **implement** the `argmin` function in the starter code, test, and debug it. </section> <section> ### Task 2-C Based on the above, begin to write `find_least_important_seam`, first by filling in `costs`. <details><summary>Expand for details</summary> Your method must: - Initialize the `costs` array to be of the correct size. Do not use array multiplication (`[...] * self.image_height`) to create the `costs` array, as it will result in the inner arrays referencing the same values on the heap. - Fill in the values for the base case(s) of the `costs` array. - Fill in the rest of the `costs` array based on the formula above, from bottom to top. You have a `check_bounds` helper function, should you need it! :::info Notice that, in the starter code, the `SeamCarve` class has a constructor that defines the following fields: ```python self.image_array self.image_height self.image_width self.costs self.dirs ``` <details><summary>What's in <code>self.image_data?</code></summary> `self.image_data` is a 3D array! That means `self.image_data` has length `self.image_height`. `self.image_data[row]` has length `self.image_width` and contains the image data for a row. `self.image[row][col]` is a 3-element array representing a specific pixel. `self.image_data[row][col][subpixel]` represents the intensity of the red (`subpixel == 0`), green (`subpixel == 1`), and blue (`subpixel == 2`) channel for a pixel in the original image! It's referred to as a 3D array, since each number in the array is indexed by 3 values (`[row][col][subpixel]`). You won't have to worry about processing `self.image_data`, since the importance values are calculated by `ImportanceCalculator` and provided to you as `vals` in `find_least_important_seam`. </details> ::: </details> </section> ### **dirs** The dirs array represents the direction of the pixel below the current cell that the seam should continue in (either left, right, or straight). ```python cost_below_left = costs[row + 1][col - 1] cost_below_mid = costs[row + 1][col] cost_below_right = costs[row + 1][col + 1] min_cost_below = min(cost_below_left, cost_below_mid, cost_below_right) dirs[row][col] = -1 if min_cost_below is cost_below_left 0 if min_cost_below is cost_below_mid +1 if min_cost_below is cost_below_right ``` Intuitively, this tells us if the seam is going to the left (-1), straight down (0), or to the right (1), based on which pixel contributed the minimum value when we were computing the `costs` table. If we start at the lowest importance seam’s topmost pixel (which we determined using costs), we can use `dirs` to trace down the seam. <section> ### Stop and Think What is the reasonable thing to do at the edges? Why don’t we need to fill out the bottom row? Think back to the goal of keeping the `dirs` array. :::success <details><summary>Check your work</summary> The dirs array represents the direction that the seam continues down. To prevent the seam from going out of bounds, the leftmost column of dirs must not have -1 and the rightmost column must not have +1. The bottom row should be left blank since the seam stops. Be mindful of `IndexError`s when computing `cost_below_*`, like you did when doing `costs`! </details> ::: </section> <section> ### Stop and Think With your `costs` array complete, fill in its corresponding `dirs` array. | **dirs** | | | | :----------: | ---- | ---- | | fill | fill | fill | | fill | fill | fill | :::success <details><summary>Check your work</summary> | **dirs** | | | | :----------: | ---- | ---- | | 0 | +1 | 0 | | 0 | +1 | 0 | </details> ::: </section> <section> ### Stop and Think Which pixels will our example seam traverse, row-by-row? You should also answer this for your own example (and put your answer in `hw5_examples.pdf`, along with your work for costs and dirs for that example). :::success <details><summary>Check your work</summary> We said in the previous example that our seam will start at pixel 1 of the top row. Because the value of `dirs` at row 0, pixel 1 is +1, we move one pixel down and _right_, meaning that our seam will continue with pixel 2 of the next row. Because the value of `dirs` at row 1, pixel 2 is 0, we move one pixel down and _straight,_ meaning that our seam will end with pixel 2 of the last row. We can represent this seam as the list `[1, 2, 2]`. This means that the pixels that should be removed are: the second pixel in the first row, the third pixel in the second row, and the third pixel in the last row. </details> ::: </section> <section> ### Task 2-D Based on this, continue to fill in `find_least_important_seam` with code that: - Initializes the `dirs` array to be of the correct size. Do not use array multiplication (`[...] * self.image_height`) to create the `dirs` array, as it will result in the inner arrays referencing the same values on the heap. - Fills in the values for the `dirs` array :::warning <details><summary>Hint: Think about where this computation belongs</summary> Instead of running the entire computation to compute the `costs` table and then running the entire computation to compute the `dirs` table, might you be able to use some logic that they share to populate both at once? </details> ::: </section> <section> ### Task 2-E Complete the `find_least_important_seam` function by using your `costs` and `dirs` arrays to create a 1D list holding the indices for the seam of least importance. _This is the `[1, 2, 2]` array in the example we've been working through._ </section> <section> ### Running the Code Let's make pretty pictures by running `seamcarve.py` from the terminal in VSCode! We can do this by running Python from a terminal as follows (see [here](https://docs.cs200.io/s/python-stencil-setup-guide#When-you-need-it-Running-Python-from-a-terminal) for general instructions): ```shell python seamcarve.py --path seamcarve_images/example01.png --seamcount 1 ``` Ensure your code is working by comparing the visual representation of the seam that it generates to this one. ![](https://lh3.googleusercontent.com/OFtZY9fhGvr3XYuGyauqKf_HU8oHLwwInyMw1_FBpOBHRmu_gcSZ8n9Y0cbhQrVHH-_HbtT6wwy5zm0ahtIYXCTpvBeU96TlJ9upvFl6Jioy8uyL-Sna3upMzHN4AlYwt3Pd-rg9K3wQDQC6Ea5UmhU) Play around with your own image instead of `seamcarve_images/example01.png` and pick a greater seam count than `1`! `seamcarve.py` will produce two images: the first will be a modification of your original image that has the seams removed, the second is the original image with the seams highlighted. :::warning <details><summary><b>If you encounter errors</b></summary> * If the command **python** isn't found, try **py** or **python3**. * You must run the above commands from your hw05 stencil directory. You will get a “No such file or directory” error if you try to run it from another location! * If you have errors regarding modules, check the [Python setup guide](https://docs.cs200.io/vscode-python-setup-guide) to make sure you're in the right virtual environment. </details> ::: </section> <section> ### Task 2-F Use the [**interactive spreadsheet**](https://docs.google.com/spreadsheets/d/1m2EPDIkgNIzVJYUu9stEANX_7lDHlAruMP5O8Dj6_dU) to come up with at least three more input images. These images should be interesting - in other words, they should test some edge case you might encounter with seamcarve. <details><summary>Details</summary> For the 5x5 version, you can edit cells A2:E6 to contain any number between 0 and 255, and the spreadsheet will automatically calculate vals, costs, dirs, and the seam, and display the resulting image. *Check the tab at the bottom of the document if you would like to create an 8x8 test image instead of a 5x5 test image!* Take a screenshot of the images in the spreadsheet (cells A2:E6) and include these images in `hw5_examples.pdf`, along with a short explanation of why these images are interesting cases to test for in SeamCarve. </details> </section> <section> ### Task 2-G Test your `find_least_important_seam` method with the interesting input images you just made! <details><summary>Details</summary> Your image data should come from the test images you just created in the spreadsheet. If you copy the value of the light blue cells (E1 and Z1), you will get Python-friendly arrays that you can use in your tests! Since the constructor for SeamCarve accepts an image array, you can copy the image data directly into `test_hw5.py`: ```python import pytest from seamcarve import SeamCarve # cell E1 from 5x5 spreadsheet test_image = [[[255, 255, 255], [0, 0, 0], [125, 125, 125], [0, 0, 0],\ [255, 255, 255]], [[0, 0, 0], [125, 125, 125], [0, 0, 0], [255, 255, 255], [0, 0, 0]], [[255, 255, 255], [125, 125, 125], [255, 255, 255], [0, 0, 0], [255, 255, 255]], [[0, 0, 0], [255, 255, 255], [125, 125, 125], [255, 255, 255], [0, 0, 0]], [[255, 255, 255], [0, 0, 0], [255, 255, 255], [125, 125, 125], [255, 255, 255]]] # cell Z1 from 5x5 spreadsheet expected_seam = [2, 1, 1, 2, 3] my_sc = SeamCarve(image_matrix = test_image) importance_vals = my_sc.calculate_importance_values() calculated_seam = my_sc.find_least_important_seam(importance_vals) assert expected_seam == calculated_seam ``` :::warning <details><summary>If your spreadsheet tests are failing</summary> * You do not need to test edge cases of small images. The constructor we give you raises an exception if the input image is less than 2x2 pixels. You also do not need to test for invalid filepaths. * You can use the debugger to examine the costs and dirs arrays and compare them to the spreadsheet. We do not recommend printing out costs and dirs, since it is hard to read that output – the debugger allows you to look at it row-by-row, which is much more manageable. * Our spreadsheet breaks ties (such as in the calculation that is analogous to `argmin`) by selecting the smallest index. For example, if the cells in costs below the cell in question for computing `dirs` are `[24, 45, 24]`, we would put -1 in `dirs`, not +1. If your spreadsheet tests are failing, make sure you don’t have ties, or that you are handling them in the same way we do (by implementing `argmin` according to the docstring and calling it when necessary). </details> ::: </details> </section> :::warning ### Submission Requirement You must use dynamic programming to find the lowest cost seam. In other words, your code should not have a running time greater than O(w∗h) where w is the picture width and h is the height in pixels. If you choose to find the lowest cost seam using brute force, your seam carver will be unreasonably slow and you’ll lose points. ::: # **Handing in** You should submit the following files to Gradescope using the **Homework 5: Implementation** assignment: - `edits.py` - `seamcarve.py` - `test_hw5.py` - `hw5_examples.pdf` There is no separate testing submission for this assignment. We will grade your tests manually, based on the descriptions of what we have asked you to test throughout this assignment. Once you have handed in your homework, you should receive an email, more or less immediately, confirming that fact. If you don’t receive this email, try handing in again, or ask the TAs what went wrong. # Changes * November 12, 1pm: swapped the "Word 1" "Word 2" labels in the codebreaker worksheet Google Sheet. * --- Please let us know if you find any mistakes, inconsistencies, or confusing language in this or any other CS200 document by filling out our [_anonymous feedback form_](https://docs.google.com/forms/d/1KqjKrDqaHAdjpmeXuQkOkeFKjuurzWHfc3HyJbXVxIs/edit)!