NEED GETTING STARTED WITH THE FIRST PART (BRUTE FORCE)

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> i. You are given a cost array R(i, j) giving the cost of these rentals for 1s isjs n. We will have to assume that R(i, i-0 and R(i, j) = oo if i > j. For example, with n 4, the cost array may look as follows: The rows are the sources (i-s) and the columns are the destinations (j's) 1 2 3 4 10 2 3 7 0 2 4 3 0 The problem is to find a solution that computes the cheapest sequence of rentals taking you from post 1 all the way down to post n. In this example, the cheapest sequence is to rent from post 1 to post 3 (cost 3), then from post 3 to post 4 (cost 2), with a total cost of 5 (less than the direct rental from post 1 to post 7, which would cost 7) 3 YOUR TASKS 3.1 BRUTE FORCE (4 points): Design a brute force solution to solve this problem. You need to print the cheapest solution, as well as the sequence. What is the asymptotic complexity of this algorithm? 3.2 DIVIDE AND CONQUER (7 points): Express the problem with a purely divide-and-conquer approach. Implement a recursive algorithm for the problem. Be sure to consider all sub-instances needed to compute a solution to the full input instance in the self-reduction, especially if it contains overlaps. As before, you need to print the solution, as well as the sequence. What is the asymptotic complexity of this algorithm? 3.3 DYNAMIC PROGRAMMING (7 points): Design a dynamic programming table for this problem. How is the table initial ized? In what order will the table be filled? How would you use the table to find the cheapest sequence of canoe rentals from post 1 to post n? Implement the corresponding dynamic programming solution