Details: In this assignment, you will implement algorithmic techniques in Java. There is also a bonus challenge that also involves these techniques and an implementation

in Java. Homework should be electronically submitted via Canvas by midnight on the due date. Each

group is expected to submit the following files:

Report.ThesubmittedreportMUSTbetypesetusinganycommonsoftwareandsubmit- ted as a PDF. We strongly recommend using LATEX to prepare your solution. You could use any LATEX tools such as Overleaf, ShareLatex, TexShop etc. When presenting your results, use log-scale graphics if/when results are too different (tiny vs. huge) to coexist on the same linear-scale graphic.

Java source code. Submit one single Java file containing all your code, except for the challenge which must be in one single separate Java file.

You must name your source code tcss343.java for the normal part of this assignment, and challenge.java for the bonus challenge.

Yourinputtestingfiles.Submitalltheinputtestingfilesyoudocumentedinyourreport. The input testing files are tab-delimited text file. An example is provided on Canvas, except for the challenge (where all arguments are given in the command line).

1

Execution. We will use the following command to execute your program for the normal part of this assignment:

java tcss343 < input.txt 

The challenge has its own format describes below. Remember to cite all sources you use other than the text, course material or your notes.

2

2 PROBLEM STATEMENT

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 1 i j n . We will have to assume that R (i , i ) = 0 and R (i , j ) = if i > j . For example, with n = 4, the cost array may look as follows: Therowsarethesources(i-s)andthecolumnsarethedestinations(js).

1234 10237 2 024 302 40

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.

What is the asymptotic complexity of this algorithm?

3

3.4 DOCUMENTATION

(4 points): Provide a well prepared document that describes your solutions, complexity analy- ses, and result analyses. Use log-scale graphics whenever the discrepancy between the cases you consider is so large than linear-scale graphics will make it too hard to compare those cases visually.

You must submit your code which should be well documented as well. If there is any known error in the code, you must point that out.

Also, document the division of labor (who did what) in your report. Remember: your presentation should briefly describe all of these items.

3.5 TESTING

(4 points): Call a pseudo-random number generator to create a cost table of size n n (notice only the upper diagonal of this matrix is full) for the following values of n: 25, 50, 100, 200, 400, 800.

For each n, consider two circumstances: in the first, the costs are entirely random (apart

from being positive); in the second, the costs are random but increasing along each row of the

cost matrix (add a random non-negative increment from the previous value on that row). Save your input testing files as tab-delimited text files. An example input file corresponding to the example input described in Section 2 is provided on Canvas as sample_input.txt.

Include your java code of the above input generator in the source code of your submission. Your code is expected to read in one input testing file, and generate the solution correspond-

ing to each of the three approaches described in Sections 3.1, 3.2 and 3.3. 3.6 ANALYSIS OF RESULTS

(4 points): Analyze the results using visualization (you may use MS Excel or equivalent spread- sheet software for that). Use log-scale whenever the numbers you get are too discrepant to be easily distinguished in linear scale.

1. qualityofthesolutions(y-axismustpresentthecost,i.e.,theobjectivefunctionvalue) for varying x.

2. running time of the algorithms (y-axis will present the machine time the algorithms need to compute) for varying x.

Your analyses should be included in the submitted document.

Remember: use log-scale graphics if/when results are too different to coexist (i.e. when one

results is tiny and the other is huge), both in the submitted documentation and in your final

presentation.

4

4 BONUS CHALLENGE (5 POINTS): THE PYRAMIDAL WARING PROBLEM

A pyramidal number is a positive integer p of form p = (m3 m)/6 for some m 2. The so-

called pyramidal Waring conjecture is that any positive integer k can be represented as the

sum of no more than five pyramidal integers (not necessarily distinct). Write a Java program that, given as input an integer n, checks if the pyramidal Waring conjecture holds for all positive integers up to n. Test your program for as large a value of n as possible within a time limit of no more than one hour: n = 103,104,105,106,..., and plot the

running times (use log-scale if the running times are too discrepant). What is the asymptotic complexity of your solution as a function of n?