In this assignment you will implement two algorithms that compute the maximum subarray and compare their performance:

Divide and Conquer Algorithm

Kadane's Algorithm

However, you'll need to modify both of these algorithms to treat the array as a circular array; that is, the array wraps around from last to first value.

For example, for the array

4

-20

8

-30

2

3

the sum of the maximum subarray using the conventional algorithm would be 8, with index range [2,2] (using 0-based indexing). Treating this as a circular array, the last two values are adjacent to the first value, so the maximum subarray would have index range [4,0], and sum 9. Note that an index range where the second value is smaller than the first indicates wrap-around.

Your modifications to use a circular array should not increase the time complexity of the algorithm ((nlgn) for the Divide and Conquer algorithm, (n) for Kadane's algorithm).

Measuring Execution Time

For this assignment, you should experiment with the number of iterations to find the appropriate number of iterations. You should compute the number of iterations from the input size such that your program runs for at least a second or two with the smallest input size.

Input

Create the input array by reading all the integers from the file specified by the first program command line argument into an ArrayList (Java). Use type long for the data values and intermediate integer variables.

For testing create a random number generator for positive and negative numbers to test for timing

Output

Output should be written as two lines of text in a file. The text should be formatted as CSV (comma separated values). If you follow the format below then you will be able to export this file into a spreadsheet quite easily.

Each output line should contain four values, separated by commas:

n,algorithm,time,sum

n is the number of values in the input file.

algorithm is "R" for the recursive Divide and Conquer algorithm, and "K" for Kadane's algorithm (quotes should be included).

time is the average CPU time in seconds required for the specified algorithm and the specified input file.

sum is the sum of the maximum subarray within the input file, treated as a circular array.

For example, here is the sample output Timing_004096.txt.out:

4096,"R",5.3281145E-4,355487 4096,"K",1.3986065E-4,355487

Analysis

In addition to submitting your source code, you must write a short analysis of your results (at most just a few paragraphs, 1-2 pages including graph(s)).

Discuss how the two algorithms scale with regard to the size of the input (n).

Include at least one graph in your report showing how the two algorithms behave with regard to n. The CSV file written by your program can be imported directly into Microsoft Excel or other spreadsheet or graphing program for analysis. Use your own output, not the sample output.

The analysis should be contained in a PDF file named "Analysis.pdf". Include it in the zip file with your code.