Question

There are n trading posts numbered 1 to n as you travel downstream. At any trading post i you can rent a canoe to be returned at any of the downstream trading posts j, where j >= i. You are given an array R[i, j] defining the costs of a canoe which is picked up at post i and dropped off at post j, for 1 ≤ i ≤ j ≤ n. Assume that R[i,i] = 0 and that you can’t take a canoe upriver. Your problem is to determine a sequence of rentals which start at post 1 and end at post n, and that has the minimum total cost.

a) Describe verbally and give pseudo code for a DP algorithm called CanoeCost to compute the cost of the cheapest sequence of canoe rentals from trading post 1 to n. Give the recursive formula you used to fill in the table or array.

b) Using your results from part a) how can you determine the sequence of trading posts from which canoes were rented? Give a verbal description and pseudo code for an algorithm called PrintSequence to retrieve the sequence.

c) What is the running time of your algorithms?

Answer 1

We have to reach from 1 to n and we have to rent a canoe to reach there. Consider the following statement:

Minimum cost for reaching from 1 to n will be the sum of the minimum cost of reaching from 1 to i and minimum cost of reaching from i to n.

the above statement holds the answer to the question.

What we have to do is find the value of i that minimizes this sum.

Here we define our solution recursively:

Now, we can store the results in the matrix C of size nxn, where C[i,j] represents minimum canoe cost from i to j, initially initialised to 0. Here is the pseudocode:

CanoeCost(x, y)

A = zeroes(n,n);

for i from 1 to n

for j from 1 to n-i

A[j, j+i] = min_j<k<j+i{A[j,k] + A[k,j+i]}

end

end

return A[1,n]

b) to get the canoe used, we just need to store the value of k for which we obtained minimum expression in algorithm and then sorting them in ascending order.

Here is the pseudocode:

PrintSequence(x, y)

A = zeroes(n,n);

list = {}

for i from 1 to n

for j from 1 to n-i

A[j, j+i] = min_j<k<j+i{A[j,k] + A[k,j+i]}

add k to list

end

end

Sort(list)

print(list)

c) Running time is same for both the algorithms. Both have two loops and in the innermost loop, we calculate minimum which takes O(n)time, so, overall complexity is O(n³)