Recall the electric car problem but this time, each battery also has a price p$[$i$]$ to replace:

Suppose you are driving along a road in an electric car. The battery of the electric car

can bring you x$[0]$ miles. There are battery stations along the way at positive positions

D$[1],.....,$ D$[$n$]($in sorted order.$)$ Each battery station can replace your battery and give you a new battery that can bring you a certain number of miles. The distances of the batteries are given in the array x$[0],$ x$[1],.....,$ x$[$n $-1]$ and the price of each battery to replace is p$[1],........,$ p$[$n $-1].$

You wish to start at position $0$ with a full battery and end at position D$[$n$]$ by replacing

batteries with the minimum total cost.

$($a$)(4$ points$)$

Recall the following greedy algorithm that worked in homework $4$:

Candidate Greedy Strategy III:

Travel to the battery station with the largest D$[$i$]+$x$[$i$]$ value $($in other words, the battery

that can take you the farthest down the road.$)$ Replace the battery at that station and

repeat the process starting from that station until you can reach position D$[$n$]$ and then

go directly there.

Give a counterexample as to why this does not always give you the optimal solution.

$($b$)(7$ points$)$

Design a reduction algorithm that uses Dijkstra's algorithm. Compute the time analysis in terms

of the number of battery stations n$.$

$4$ points for correct high level algorithm.

$3$ points for runtime analysis.

$($No proof of correctness$)$

$($Your algorithm should run in O$($n$^2)$ time.$)$

$($c$)(10$ points$)$

Design a DP tabulation algorithm by ordering the subproblems from n to $0$: $($step $1$ and $4$ have

been done for you$)$

$1$: Dene the subproblems:

Let G$[$k$]$ be defined to be the minimum price it takes to get to battery station n

assuming you start at battery station k with the battery from battery station k$.$

$2$: Dene and evaluate the base cases

$3$: Establish the recurrence for the tabulation.

$4$: Determine the order of subproblems:

Order the subproblems from n to $0.$

$5$: Final form of output.

$6$: Put it all together as pseudocode

$7$: Runtime analysis