Homework 6: Dynamic Programming

--- tags: Homeworks-Summer21 --- # Homework 6: Dynamic Programming **Due Date: Friday, July 23rd, anywhere on Earth time (Saturday, July 24th, 8 a.m. EDT)** ## The Hunt Continues... (optional) :::spoiler Optional theme material The all-powerful CS18 Team of Theme needs to make a video. Why? Well.. you'll find out soon enough. But the scenery around campus is too boring! It's all the same buildings and greenery, drudgery unspeakable. Before, there was a blue anchor, a light at the end of the storm. But now the blue anchor has vanished. Blueno is gone. The glorious Team of Theme plans to bike from Providence to Boston, but its members also have a healthy appetite. To plan their trip effectively and satisfy their hunger, they need to develop an algorithm! *Deliciously good snacks, the Theme Team must eat,* *On their trip to ol' Beantown, what a delightful retreat!* *Taking videos and snapshots,* *For a mystery well-wrought,* *Soon to be watched, by all who complete!* Check out this wonderfully customized remake of [2048 with the CS18 staff](https://cs18-2048.vercel.app/) (and you might find a clue here as well) ::: ## Learning Objectives * Develop a collection of examples and tests that exercise key behavioral requirements and aspects of a problem * Write programs that behave as expected based on a provided description or collection of test cases ## Assignment Link Here is the [Github classroom link](https://classroom.github.com/a/VtiQgv9u). If you're having trouble with IntelliJ, check out our [IntelliJ Common Problems](https://hackmd.io/webHvA8yTCqGOAKXYgrI_A) handout. Please make sure to read [our gradescope submission guide](https://hackmd.io/jC-SEMn_RpiGqMH_EhsDMw) before handing in your assignment! ## Handing In There are some written questions on this homework. For these questions, create your answers in whatever word processing program you like and upload a PDF with your answer. After completing this assignment, these files sould comprise your `sol` package: * `TravelPlain.scala`: a recursive solution to the Travel Plans problem * `TravelPlans.scala`: a DP solution to the Travel Plans problem * `CodeBreaker.scala`: a DP solution to the Code Breaker problem * `Homework6TestSuite.scala`: tests for `TravelPlain`, `TravelPlans`, and `CodeBreaker` * `written.pdf`, with the answers to the writen questions on this homework. You should submit the above files to the **Homework 6 : Implmentation** submission on Gradescope. You should additionally submit `Homework6TestSuite.scala` to the **Homework 6 : Testing** submission. **Note:** If your code does not work with the autograder, you will be penalized. If there are any complications, follow these steps: * Make sure that your Testing submission passes the wheat test. If it doesn't, you should use the autograder output and the message in the failed autograder test to debug your test suite. * If your test suite passes the wheat, run your implementation against your test suite. If this crashes, you should fix your solution code so that it is compatible with your test suite. * If you are still having issues, please reach out to us at TA Hours or Ed. ## Travel Plans  ### Problem Description You have to plan a multi-day trip to Boston from the CIT. You are able to travel up to a certain distance each day. You also have a food budget, so you have to figure out where to stop each day so that your food budget lasts through the trip. There are a total of $n$ rest stops that you could stop at, conveniently spaced at regular intervals of exactly 1 mile apart. The first rest stop is exactly 1 mile from your starting point (the CIT). You calculate that you can bike up to $d$ miles (inclusive) before you get too tired. Thus, you must visit a rest stop every $d$ miles (inclusive). In addition, **you must stop at the last rest stop before the end** (Boston) to gather supplies. Each rest stop has different qualities of snacks, so some stops are more expensive than others. You fortunately are a snack/rest stop connoisseur so you already know the costs associated with each rest stop to the nearest dollar. For this problem, you need to compute (1) the minimum amount of money you must spend to get from the CIT to the last rest stop before Boston and (2) the path associated with that minimum cost. This path will be a sequence of rest stops, where no pair of consecutive stops are greater than $d$ miles apart. Remember, this sequence should always terminate with the last rest stop. Your solution to this problem will take two inputs: (1) an array of size $n$ containing the cost (U.S. Dollars) associated with each rest stop, and (2) the maximum distance $d$ that can separate consecutive rest stops in the final path. Your solution will choose which rest stops to visit, with the choice constrained by the given distance. We'll approach this problem using the sequence of steps we've been following in lecture: work out a concrete example, write the plain recursive code, then optimize a copy of the recursive code with dynamic programming. **If you go to office hours with a question, the TAs may ask to see your work on the steps, to help figure out where you are actually stuck. The TAs will not help you find errors in your code without your showing them the steps.** * **Task:** Work out a concrete example of costs (U.S. Dollars) and show what the minimum value and path would be for an array of rest stop costs and distance $d$ of your choosing. These answers should be in the PDF that you upload for this assignment. These do not need to be written in code (as a test case would) --- you can write your costs example as a table or sequence of numbers within the doc. If you think working out a second example would help you understand the problem, feel free to write it down as well (though we only require one example for grading). :::info You are welcome to collaborate with other students to develop examples and to confirm the correct answers for each one. You'll still do the coding on your own, but sharing examples and ideas about how the problem works is fine. You just need to document who you worked with on the examples in your PDF file. ::: * **Task:** Write a recursive program (no dynamic programming optimization) that computes the minimum cost to make the trip (under the constraint of no more than $d$ miles per day). Put this in the class called `TravelPlain`. The class should contain the following methods: 1. Constructor: takes two inputs---an integer `distance` (representing what has been referenced as $d$ in this handout) and an array `snackCosts` of doubles. 2. Method: `optimalCost`, which takes no parameters and returns a double representing the minimal snack cost (U.S. Dollars) for you to get from the CIT to the last rest stop (remember, the last rest stop must be included in your solution). 3. You might find it helpful to write a helper method that takes in an index of a rest stop and which computes the minimal snack cost for you to get to that rest stop. **Note:** Remember that the first rest stop (rest stop 0) is 1 mile from the CIT! * **Task:** In `TravelPlans`, make a copy of your unoptimized recursive program and modify it to use dynamic programming. You may use either top-down or bottom-up DP (whichever your prefer). `TravelPlans` should contain the following fields and methods (part of the DP solution): 1. Field: An array named `optCosts` that stores the minimal snack costs you can incur getting to each rest stop. 2. Field: An array of `Lists` called `optPaths` to store the paths corresponding to the minimal snack costs computed in step 1. 3. Method: `initTable`, which takes no parameters and returns void. It puts base case values and default values into `optCosts` and `optPaths` (see `AbsMacaron` from lab 9 for an example). For this problem (and the next one), your default minimal value should be `Double.NegativeInfinity`. 4. Method: `fillTable`, which mimics the recursive solution to fill in the cells of `optCosts`. 5. Constructor: takes two inputs---an integer `distance` and an array `snackCosts` of doubles (**in that order**). The array will be of length $n$, where $n$ is the number of rest stops. The Constructor should: 1. Check that the distance is larger than 0 and the number of rest stops is at least one. If either of these conditions fails, throw an `IllegalArgumentException` with no message. *You do not need to write tests for these exceptions.* 2. Set `optCosts` to an uninitialized table of the dimensions required based on the number of rest stops in the input. 3. Set `optPaths` to an uninitialized table of the same dimensions as *optCosts*. 4. Call `initTable` and `fillTable`, in that order. 6. Method: `optimalCost`, which takes no parameters and returns a double representing the minimal snack cost (U.S. Dollars) for you to get from the CIT to the last rest stop (remember, the last rest stop must be included in your solution). 7. Method: `optimalPath`, which takes no parameters and returns an array of booleans that indicate which rest stops you should stop at to achieve minimal cost (U.S. Dollars). Specifically, if you should stop at rest stop $i$, then the boolean value associated with rest stop $i$ should be assigned the value `true`. **Note:** The last rest stop should always be assigned the value `true` since you must stop there. **Note:** Use `optCosts` and `optPaths` to write these two methods. Particularly for the first method, you should not be doing lots of extra calculations. If your approach seems complicated, rethink it! **Note:** The `optimalCost` method is a function in the mathematical sense: there is always a unique minimum cost of traveling from the CIT to Boston, say $c^*$. However, the optimal path need not be unique. Indeed, there may be multiple selections of rest stops suitably spaced along the route whose total costs sum to $c^*$. Your `optimalPath` function need only return one such selection; all are equally valid solutions to this problem. * **Task:** As always, be sure to write test for your implementation of `TravelPlans` in `Homework6TestSuite`. You should test the `optimalCost` and `optimalPath` methods (testing the others is not required). In particular: * You do not need to write any tests for inputs that would yield exceptions. * Your tests for `optimalPath` do not need to include cases where there is more than one possible solution. It is fine to test only cases that have a single solution. For `optimalCost`, however, you should test cases with multiple paths to the same optimal cost. * You do not need to write tests for any private methods (even if they are methods that we told you to write). * You should write tests for `TravelPlain` as well (you can use the same tests that you wrote for `TravelPlans`) ## Code Breaker ### Problem Description Your goal is to find the "difference" between two words, which we quantify as a number indicating the minimum number of edits required to transform one word into the other. There are three possible operations: inserting a letter, removing a letter, and substituting a letter. For example, consider the words “apple” and “opal”: apple -> opple (substitution) opple -> opale (substitution) opale -> opal (deletion) Here, the difference between the words would be 3, because it takes 3 operations to go from “apple” to “opal”! For the purposes of this problem, you should count uppercase and lowercase letters as the same letter. This means the difference between “opal” and “OPAL” should be 0. The difference between two words can be computed recursively, by looking at the numbers of edits needed to convert substrings to one another. Continuing with "apple" and "opal", imagine that you had a two-dimensional array with one word on each dimension: | | ` — ` | `"a"` | `"p"` | `"p"` | `"l"` | `"e"` | | ------- | --- | --- | --- | --- | --- | --- | | **` - `** | | | | | | | | **`"o"`** | | | | | | | | **`"p"`** | | | | | | | | **`"a"`** | | | | | | | | **`"l"`** | | | | | | | In the cells, you would store the minimum distance between the substrings from the current row/column to the last row/col (you could also interpret substrings as going from the first row/col to the current one). Filling in the table would give you the minimal distance between the entire words. * **Task:** Come up with a concrete example using words with at least 4 letters other than "apple" and "opal" and show the table contents for those two words. Include the completed table in your PDF submission. :::info You are welcome to work with others to understand how to fill in the apple/opal table, but the concrete example you submit for this task should be entirely your own work. ::: * **Task:** Write a class, `CodeBreaker`, whose constructor takes as input the two words. Inside your `CodeBreaker` class, write a method `findScore`, which takes in no arguments and returns an `Int` representing the smallest difference between the two words input into the class. In addition to the `findScore` method, your class should contain the following: * A table (2-dimensional array) named `similarityArray` that stores distances between either the prefixes or suffixes of each word (this choice corresponds to the choice of direction in filling out the table cells). * A method `fillSimilarities` that takes in no parameters and returns void. This should fill in the cells of `similarityArray` using dynamic programming. You should call `fillSimilarities` inside your class in order to fill the `similarityArray`. Your `findScore`method should therefore just return the contents of the cell that contains your final answer (which cell that is will depend on the order in which you chose to fill the table). You do NOT need to write the plain recursive solution for this problem, but you are welcome to if it will help you understand the computation before you try to optimize it. * **Task:** As always, write your tests for this problem in `Homework6TestSuite`. The testing guidelines are the same as they were for the tests for Travel Plans. :::spoiler **Open for hints on CodeBreaker!!** 1. Think about what the base cases for this problem might be. Start there and work backward. 2. Look back at Lab 9, and review the macaroon problem. Review Lecture 26 (Dynamic Programming) as well. 3. Complete (many) more examples! In each example, how did you figure out what goes in each box of the table? Could you explain in English what you considered? Could you translate that process to code? 4. In Travel Plans, "moving" from one cell of the DP table to another has a straightforward meaning. What would it mean to "move" from one cell of your table to another? 5. If you're stuck, please post your worked example(s) and your thoughts on Ed! ::: ## Socially Responsible Computing :::success This assignment is also available as a Google document, which [you can copy here.](https://docs.google.com/document/d/14Y81biyXpYkITZh13RFMbAbC0m3gPQ3taN4haEUBow0/edit?usp=sharing) ::: Read [this](https://www.nature.com/articles/d41586-018-06610-y) article and complete the following tasks: **Task 1:** Imagine that the government of the country you’re in is considering a measure to limit streaming (Netflix, Hulu, etc.) traffic per household to some fixed amount of hours per week (see “Power Play” section). Assume that, if enacted, you can’t get around it with multiple accounts/VPNs/other measures. Would you support the measure? Why or why not? [5-6 sentences] The position you choose doesn’t matter--what matters is that you pick a side and support your point with evidence from the text, potential impacts on relevant stakeholders, and refutation of counter arguments. :::spoiler **Click for hint** For some direction on issues you might consider when answering this question, think about these questions from the [social threats modeling table](https://docs.google.com/document/d/1PDYOcwgQmfSLS7YAAzoUlwoytvRr7_gDwM-BRkPa548/edit?usp=sharing) introduced in lecture 19. * How does the system impact an individual stakeholder’s ability to thrive, exercise their rights, and develop freely? * How does the system impact the relationships between individuals and their community, including trust, communication, and participation? * How much energy does it take to collect, store, and maintain the data? ::: <br/> **Task 2:** Google crawls and indexes millions of webpages and stores this information across its various data centers around the world. You implemented a smaller version of this indexer when you completed Search. 1. Explain one social and one environmental outcome of Google Search’s high space usage. [3 sentences] 1. Explain one social and one environmental outcome of Google Search’s low runtime. [3 sentences] 1. Why is it important to consider the resource usage of our programs? [3-4 sentences] 1. Suggest a more accurate name for the Cloud—one that better represents its environmental impact and the physical data centers it relies upon. Have fun with this! [1 sentence] ### How to Hand In/Grading: Submit your work as a single PDF file on Gradescope to the “Homework 6: SRC” submission portal. Do not include your name or other identifying fields anywhere in your response. This, like all assignments, is subject to the course collaboration policy. ## FAQ  **What is the difference between top down and bottom up dynamic programming? Is one method preferred?** Check out [Lab 9, Slide 7](https://docs.google.com/presentation/d/1YBYKEZmonA4BB7i8XG6M19VQrAPko1et/edit#slide=id.p5), also shown below. Reviewing the exercises in Lab 9 may also be helpful. ![](https://i.imgur.com/wsyaiMJ.png) In summary, Top-Down: starts with the problem, then addresses subproblems Bottom-up: starts with base case(s), then builds up to the problem Neither method is preferred : ) **How do I run code in the constructor to set up stuff?** In Scala, unlike Java, if you put code in the body of the class (outside of a method), it is essentially like putting code in a Java constructor! Like so: ```scala= class Example(cs18: String) { /* this code will run each time a new Example * is created, as it is outside of a method */ if (cs18 == "super cool") { println("wow so cool :0") } } ``` --- *Please let us know if you find any mistakes, inconsistencies, or confusing language in this or any other CS18 document by filling out the (mostly) [anonymous feedback form](https://cs.brown.edu/courses/cs018/feedback)!*