< Programming Assignment #1>
Description: Your algorithm first takes an input size (N) from the user and generates a random sequence of N integers ranging from -99999 to 99999. If N is less than 50, your program must print the randomly generated numbers on the screen. After the generation of the random array, your program takes an input K from the user again, and determines if there are two numbers whose sum equals a given number K. For instance, if the random numbers are 8, 4, 1, 6 & 3 and K is 10, then the answer is ‘yes’ (since 4 + 6 = K).
Do the following:
(a) Give O(N2) algorithm to solve this problem. Describe your idea and analyze the complexity of your solution.
(b) Give O(N log N) algorithm to solve the problem (Hint: Sort the array first and find such numbers). Describe your idea and analyze the complexity of your approach.
(c) Give O(N) algorithm to solve the problem. Analyze the complexity of your algorithm. Describe your approach and analyze the complexity of your algorithm.
(d) Code these solutions and compute the running times of your algorithms.
(Write your code in Java for (a), (b) and (C))
(e) Measure and compare the executions times of your algorithms at least 10 times, and plot the average and worst execution time of these methods (i.e. execution time on the vertical axis and input size on the horizontal axis) for input sizes 4000, 8000, 16000, 32000, and 64000 (the range of your input sizes can vary based on the speed of your computer); Turn in the softcopies of two graphs (one for the average execution time and the other for the worst-case execution time).
Deliverable: A single zipped file that includes the followings -
· For (a), (b) and (c): In an MS-word file, list your algorithms with a brief explanation of your method and the complexity analysis of them (O(N2), O(NlogN) & O(N) algorithms)
· A table that includes ten measured execution times per each algorithm and each input size. A template of the table for input size =4000 is shown below for your reference. You have to add a similar table for each input size.
Input size (4000)
|
O(N2) algorithm
|
O(NlogN) algorithm
|
O(N) algorithm
|
Test 1
| |||
Test 2
| |||
Test 3
| |||
Test 4
| |||
Test 5
| |||
Test 6
| |||
Test 7
| |||
Test 8
| |||
Test 9
| |||
Test 10
| |||
Average
| |||
Worst Case
|
· Two graphs (Average cases and worst cases)
· All source files
· A brief compiling/running instruction
Here is a sample execution of the program:
[Mike Capito @vulcan Test]$ java k_Sum
1. Quadratici algorithm
2. Logarithmic algorithm
3. Linear algorithm
4. Exit the program
Choose an algorithm: 1
Enter size of random array: 10
754 395 -42 -260 -347 61 296 -715 -686 -654
Enter the K value: -390
Running the O(N^2) algorithm...
K = -390, (296 + -686)
Yes, there are two numbers whose sum equals to K
Execution time in nanoseconds: 350000
1. Quadratici algorithm
2. Logarithmic algorithm
3. Linear algorithm
4. Exit the program
Choose an algorithm: 3
Enter size of random array: 64000
Enter the K value: 22345
Running the O(N) algorithm...
No, the algorithm could not find two numbers whose sum equals to K
Execution time in nanoseconds: 217000
1. Quadratici algorithm
2. Logarithmic algorithm
3. Linear algorithm
4. Exit the program
Choose an algorithm: 4
[jyoun@vulcan Test]$
For full credit, your code should be well documented with comments, and the style
of your code should follow the following guidelines:
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, Summer 20XX *
* 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%
