Quadratic maximum contiguous subsequence sum algorithm (algorithm 2)

Linear-time maximum contiguous subsequence sum algorithm. (algorithm 4)

Recursive maximum contiguous subsequence sum algorithm. (algorithm 3)

CSCI3320 Programming Assignment #1 (Due: 11:59 PM, June, 2017) Problems Description: Note that the maximum contiguous subsequence sum algorithms in the text do not give any indication of the actual sequence. In this assignment, you will modify these algorithms, and measure their execution times with various input sizes. (a) Modify Algorithm 2, 3 & 4 so that they return in the value of the maximum subsequence and the starting and ending indices of the maximum subsequence. Your algorithm should take input size (N) from the user and generate a random sequence of N integers ranging from -9999 to 9999. If N is less than 50, your program must print the randomly generated numbers, and find the maximum subsequence. Your program should measure (print) the execution time of these algorithms (Algorithm 2, 3 & 4) in nanoseconds. > java maxSumTest Please enter the size of the problem (N): 15 673 -869 -153 214 -139 40 65 -925 -639 -696 956 823 -714 500 967 Algorithm 2: MaxSum: 2532, S_index: 10, E_index: 14 Execution Time: 13 milliseconds Algorithm 3: MaxSum: 2532, S_index: 10, E_index: 14 Execution Time: 18 milliseconds Algorithm 4: MaxSum: 2532, S_index: 10, E_index: 14 Execution Time: 9 milliseconds (b) Measure and compare the executions times of your algorithms at least 10 times, and find the averaged worst-case execution times of these algorithms. The execution time of each test case must be recorded in a table. A template of the table for input size =8000 is shown below for your reference. You have to add a similar table per each input size. Plot the worst-case execution times of Algorithm 2 & Algorithm 3 for input sizes 8000, 16000, 32000, 64000, 128000 and 256000. Plot the worst-case execution times of Algorithm 3 & Algorithm 4 for input sizes 8000, 16000, 32000, 64000, 128000 and 256000. (execution time on the vertical axis and input size on the horizontal axis) for input (To generate a reasonable graph, please feel free to use different input sizes as needed) Input size (8000) Algorithm 2 Algorithm 3 Algorithm 4 Test 1 Test 2 Test 3 Test 4 Test 5 Test 6 Test 7 Test 8 Test 9 Test 10 Average (c) Compare the Big-Oh complexities of Algorithm 2, 3 & 4 with your experimental results (b). If there is any major discrepancy between your results and the algorithm complexities in Big-Oh, discuss where the discrepancy came from. Deliverable: A zipped file including source codes with compiling/running instructions, two graphs for the averaged execution times of three methods (Note: A handdrawn graph will not be accepted), and a document that includes tables of ten measured execution times per each algorithm and each input size (the document must include part (c) answer if there is any major discrepancy between the graphs and the analysis). (Upload a SINGLE zipped file to Blackboard. Note that the zipped file must includes all electric copies of your source codes with brief running instruction, the graphs, and the MS-Word document) Note that your code should be tested on the loki.ist.unomaha.edu machine. For full credit, your code should be well documented with comments, and the style of your code should follow the following guidelines: Your programs must contain enough comments. Programs without comments or with insufficient and/or vague comments will cost you 30%. Every file should have a comment header describing who wrote the program and what is in the file. An example header comment is shown below: /*************************************************** * Program Title: XXXXXXXXXXXXXXXXXXXXXX * * Author: XXXXX XXXXXX * * Class: CSCI3320, Fall/Spring/Summer 201X * * Assignment #1 * ****************************************************/ Every method or function should have a comment header describing inputs, outputs, and what it does. An example function comment is shown below: /*************************************************** * FUNCTION xxyyzz : (function name) * * the purpose of this function * * INPUT PARAMETERS : * * a list of all parameters and their meaning * * OUTPUT : * * the description about returning value * ****************************************************/ Inline comments should be utilized as necessary (but not overused) to make algorithms clear to the reader. Not-compile programs receive 0 point. By not-compile, I mean any reason that could cause an unsuccessful compilation, including missing files, incorrect filenames, syntax errors in your programs, and so on. Double check your files before you submit, since I will not change your program to make it work. Compile-but-not-run programs receive no more than 50%. Compile-but-not-run means you have attempted to solve the problem to certain extent but you failed to make it working properly. A meaningless or vague program receives no credit even though it compiles successfully. Programs delivering incorrect result, incomplete result, or incompatible output receive no more than 70%