Homework 6: Dynamic Programming

--- tags: Homeworks --- # Homework 6: Dynamic Programming **Due Date: Sunday, April 4nd, anywhere on Earth time (Monday, April 5rd, 8AM EDT)** ## The Hunt Continues... (optional) 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 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/qADHsLAH). 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 when we ask you to develop examples for each problem. Create your answers in whatever word processing program you like and upload PDF with your answer to those questions. After completing this assignment, these files sould comprise be in 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 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 Piazza. ### Grading/SNC You can earn a passing grade just from completing the `TravelPlans` problem (assuming your work is mostly correct). Students aiming for As or Bs in the course also need to submit `CodeBreaker`. The difference between A and B grades will depend on the quality of your work, including the set of examples that you chose to use in testing. ## Travel Plans  ### Problem Description You have to plan a multi-day trip. 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 one 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 a class called `TravelPlain`. The class should contain the following methods: 1. Constructor: takes two inputs---an integer `distance` 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. * **Task:** Create a class called `TravelPlans` to hold your dynamic programming solution for this problem. **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`. 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`. *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. Minimal edit distance 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 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. ## Socially Responsible Computing **Task 1.1**: List 10 words that come to mind when you hear phrases like “the cloud”, “the internet" and "algorithm".(e.g. accessible, online, logical…). :::spoiler **Click to reveal all remaining tasks** **Task 1.2**: Read [this](https://www.nature.com/articles/d41586-018-06610-y) Nature article [approximately 15 minutes of reading] **Task 1.3**: Consider the words you listed for Task 1.1. What were some of your own expectations and perceptions of “Internet,” and the “Cloud”, and did the reading change any of them? List 3 new words that you would add to your original list. [3-5 sentences] **Task 1.4**: With reference to anything you learned from the text, why is it important to consider the space and resources taken up by the programs you write? [3-5 sentences] **Task 1.5**: Google crawls and indexes millions of webpages and stores this information across its various data centers around the world. Describe 2 advantages and 2 drawbacks of pre-processing (indexing) before querying for large-scale algorithms like a Google search. [3-5 sentences] **Task 2**: As programmers, we need to consider different axes along which to optimize our programs like space and time complexity. Often, how long a program takes to run and how much space it takes are at odds. Explain your impression of the trade-off between space and time in dynamic programming and why you came to this conclusion. [2-4 sentences] --- Please let us know if you find any mistakes, inconsistencies, or confusing language in this or any other CS 18 document by filling out the anonymous feedback form: https://cs.brown.edu/courses/cs018/feedback.