Solved–Computing and Algorithms III: Program 3– Solution

Description

The Problem

You have been assigned to organize the first annual Kettering CS Department canoe trip down the Flint River. Canoes are available for rent at a sequence of n trading posts along the river, numbered 0, 1, . . . , n − 1. The trip begins at post 0 and ends at post n − 1.

However, individuals do not have to keep the same canoe for the entire trip; one can stop at any post, drop off the canoe used to reach that post, and rent another canoe. One may make as many stops on the river as desired. All canoe rental costs are positive integers. There is no added charge for exchanging canoes at a post. Travel down the river is one-way (downstream).

For all pairs (a, b) with a < b, the cost of renting a canoe at post a and dropping it off at post b is given by a two-dimensional array C[a, b].

A sample cost matrix is shown below (with n = 4).

		0	1	2	3
	0	− 10		15	50
	1	−	−	40	20
	2	−	−	−	35
	3	−	−	−	−

Since most of those participating in the canoe trip are students, there is significant interest in finding the minimum cost sequence of canoe rentals. In the example above, the optimal solution is to rent a canoe between posts 0 and 1, and another canoe between posts 1 and 3, for a total cost of 30.

The Assignment

Write a Java program which takes as input the name of a file in the current directory. The first line of the file will contain an integer n, giving the number of posts along the river. The remaining n − 1 lines of the file will contain the integers of the cost matrix, delimited by white space, omitting the unnecessary entries.

For example, the matrix shown above could be represented by the following data file:

4

10 15 50

40. 20

35

(Note that white space is not significant in the file.)

Using a dynamic programming algorithm, your program will then compute the optimal costs of traveling between any two posts (i, j) where i < j. The goal is to determine the optimal cost for (0, n − 1).

After performing that calculation, your program will print the optimal cost matrix: I.E. the optimal cost between any two posts (i, j) for all values 0 ≤ i < j ≤ n − 1. Additionally, your program will print the actual sequence of rentals to be used for the route between posts 0 and n − 1 (not just its optimal cost).

Your program should use “good style”. See the separate handout on style requirements for CS-203 programs. In particular, note that you should describe the algorithms you implement in sufficient detail to demonstrate your deep understanding of the algorithms in question.

Additionally, you should create the following ordinary text files:

• README: Information on how to compile and run your program.

• ANALYSIS: An analysis of your program, including:

– A description of the (recursive) formula used to calculate the optimal costs be-tween posts

– A theoretical analysis of the run time of your program, based upon that recursive formula

Note that an empirical timing analysis is NOT required.

Submitting Your Program

Before 11:59:59 p.m., Thursday, 29 November 2018 (9th Thursday), you must upload a zip archive to the course Blackboard assignment for Programming Assignment 3. This zip archive must contain all source code files for your program, along with the two text files named above.

No code printouts are required.

Explain Your Program

You must explain your program to the instructor before 5:00 p.m., Thursday, 6 December 2018 (10th Thursday), either in the lab or in the office hour. Highly encourage you to explain your program before the submission deadline, which is 11:59:59 p.m., Thursday, 29 November 2018 (9th Thursday). Then, you can modify your program if the instructor finds problems.

3