CSCI570 Homework 6 Solution

1. Given a non-empty string s and a dictionary containing a list of unique words, design a dynamic programming algorithm to determine if s can be segmented into a space-separated sequence of one or more dictionary words. If s = “algorithmdesign” and your dictionary contains “algorithm” and “design”. Your algorithm should answer Yes as s can be segmented as “algorithm design”.

Your objective is to travel from the starting point at the city's entrance, located at block (0,0), to a specific destination block (n,n). The city is laid out in a grid, and at each intersection or block (i, j), you might either incur a cost (pay an entrance fee) or receive a reward (get a payback) for passing through. These transactions are captured in a grid, with positive values representing fees and negative values representing paybacks.
You would like to get to your destination with the least possible cost. Formulate the solution to this problem using dynamic programming.
a) Define (in plain English) subproblems to be solved.
b) Write the recurrence relation for subproblems.
5. You have two rooms to rent out. There are n customers interested in renting the rooms. The ith customer wishes to rent one room (either room you have) for d[i] days and is willing to pay bid[i] for the entire stay. Customer requests are non-negotiable in that they would not be willing to rent for a shorter or longer duration. Devise a dynamic programming algorithm to determine the maximum profit that you can make from the customers over a period of D days. a) Define (in plain English) subproblems to be solved.
b) Write the recurrence relation for subproblems.
6. You are given a sequence of n numbers (positive or negative): 𝑥1, 𝑥2,. . . , 𝑥𝑛 .Your job is to select
a) subset of these numbers of maximum total sum, subject to the constraint that you can’t select two elements that are adjacent (that is, if you pick 𝑥𝑖 then you cannot pick either 𝑥𝑖−1 or 𝑥𝑖 ). On the boundaries, if 𝑥1is chosen, 𝑥2 cannot be chosen; if 𝑥𝑛 is chosen, then 𝑥𝑛−1 cannot be chosen.
Give a dynamic programming solution to find, in time polynomial in n, the subset of maximum total sum.
7. Suppose you have a rod of length N, and you want to cut up the rod and sell the pieces in a way that maximizes the total amount of money you get. A piece of length i is worth pi dollars. Devise a Dynamic Programming algorithm to determine the maximum amount of money you can get by cutting the rod strategically and selling the cut pieces.