Programming Assignment
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]$