Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
CSE 101 Fall
Instructions
For each of the following dynamic programming design problems (problem 3):
the following ingredients are needed:
1: Define the sub-problems and corresponding array (this needs to be a description of an arbi-
trary array entry in words.)
2: A description of the base cases
3: the recursion used to fill the array and an explanation of the recursion. (often this requires
a case analysis.)
4: ordering of the subproblems
5: final form of output
6: pseudocode
7: time analysis
If you don’t have the above ingredients, we will not grade your submission.
No justification of correctness is required.
1. (15 points)
Recall the mountain problem from the midterm:
A linear mountain range has n peaks, one peak every mile. Each peak has a height in thousands of
feet given as an array A[0], . . . , A[n− 1]. You wish to put cell towers on a subset of the peaks so that
every peak is covered will cell service. The range of the cell tower is proportional to the height of the
peak. In particular, for every thousand feet of height, the cell tower has a horizontal range of 1 mile
(in each direction.)
Now, suppose to lead an expedition to erect a tower on a mountain, it will cost you 1000 dollars per
thousand feet of height.
Design a Dynamic programming algorithm that returns the minimum cost to cover the entire mountain
range.
For this problem, we will give you the definition of the subproblems and corresponding array:
Let M [i] be the minimum cost to cover all mountains 1, . . . , i by only using mountains
1, . . . , i.
Alternative subproblem:
Let M [i, j] be the minimum cost to cover all mountains 1, . . . , i by only using mountains
1, . . . , j.
2. (15 points)
Recall the Electric car problem from hw4 (question 1.)
You are driving from city X to city Y along a straight road in your electric car. Your car has a battery
capacity of B KWh. This time assume that B is an integer that your car has a fuel economy of e = 1
(meaning that you can travel 1 mile on 1 KWh).
There are a number of charging stations located at distances X < x1 < x2 < . . . < xn < Y (measured
in miles) such that X = x0 = 0 and Y = xn+1. Also, assume that each xi is an integer.
1
Now, suppose that each gas station has a price for charging: (p0, p1, . . . , pn, pn+1) meaning that at
station i, it costs pi dollars to charge 1 KWh (also assume that the charging stations charge in integer
quantities of KWh).
Your goal now is to travel from X to Y using the least amount of money. (The time it takes is not
relevant for this problem.)
Design a Dynamic programming algorithm that returns the minimum cost.
For this problem, we will give you the definition of the subproblems and corresponding array:
Let P [i, k] be the minimum cost to get to station i with k KWh of charge left in your
battery.
3. Farkle is a dice game played with 6 six-sided dice. There are many rules and variations to the game
so let’s stick with the simplest version:
Each die showing a 1 is worth 100 points and each die showing a 5 is 50 points. Any other number
(2,3,4,6) does not score.
This is how the game is played: You first roll all 6 dice. If you do not roll any scoring dice then your
turn is over and you get 0 points (This is called a FARKLE). Otherwise, you will set aside all of your
scoring dice (1’s and 5’s) and then roll the remaining dice.
The play continues in the same way. If on your next roll, you do not roll any scoring die then your
turn is over and you get 0 points (FARKLE). Otherwise, you will set aside all of your scoring dice (1’s
and 5’s) and then roll the remaining dice.
If, eventually all of your dice are scoring dice then your turn is over and you earn that score.
(a) (18 points)
Design a dynamic programming algorithm that computes the probability of playing FARKLE
with n dice and successfully ending with all 1’s and 5’s.
(b) (2 point)
What is the expected score for 6 dice?