You are traveling by a canoe (boat) down a river and there are n trading posts a

Question

You are traveling by a canoe (boat) down a river and there are n trading posts along the way. Before

starting your journey, you are given for each 1 %u2264 i < j %u2264 n, the fee fi,j for renting a canoe from post i to post

j. These fees are arbitrary (random). For example, it is possible that f1,3 = 10 and f1,4 = 5. You begin at

trading post 1 and must end at trading post n (using rented canoes). Your goal is to minimize the rental

cost.

%u2022 Give the most efficient Dynamic Programming algorithm (in pseudocode form) you can to find

out the optimal cost.

%u2022 Write an efficient algorithm (in pseudocode form) to find out the optimal path.

%u2022 Perform time and storage complexity analyses of your algorithms.

%u2022 Show trace of your algorithms by choosing an appropriate example.

Explanation / Answer

Let m[i] be the rental cost for the best solution to go from post i to post n for 1 %u2264 i %u2264 n.

The %uFB01nal answer is in m[1]. We can recursively, de%uFB01ne m[i] as follows:

m[i] =

%uF8F1

%uF8F2

%uF8F3

0 if i = n

min

i<j%u2264n

(fi,j + m[j]) otherwise

We now prove this is correct. The canoe must be rented starting at post i (the starting

location) and then returned next at a station among i + 1, . . . , n. In the recurrence

we try all possibilities (with j being the station where the canoe is next returned).

Furthermore, since fi,j is independent from how the subproblem of going from post

j, . . . , n is solved, we have the optimal substructure property.

For the time complexity there are n subproblems to be solved each of which takes

O(n) time. These subproblems can be computed in the order m[n], m[n %u2212 1], . . . , m[1].

Hence the overall time complexity is O(n

2

).

NOTE: One (of several) alternate general subproblem form that also leads to an O(n

2

)

algorithm is to %uFB01nd the best solution to get from post i to post n where the canoe

cannot be exchanged until post j is reached (for 1 %u2264 i < j %u2264 n).

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.