Reference no: EM131310002
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]$
|
How does the song you have chosen reflect the ideas
: How does the song you have chosen reflect the ideas, opinions, and writings of people involved in the movements we have been studying?These are the civil rights, black power, anti-Vietnam War, counterculture, and feminist movements. Your paragrap..
|
|
Should this antivirus software be installed on mail server
: What other actions should the Drib take to limit incoming computer worms and viruses in attachments? Specifically, what attributes should cause the Drib to flag attachments as suspicious, even when the antivirus software reports that the attachmen..
|
|
What are the port strategic goals
: 1. Background information about the port: industry classification; markets, location, # of employees, products & services, suppliers, other pertinent information 2. What are the port's strategic goals? 3. What are the strengths of the port?
|
|
Find and display the max value and the index of the max
: Find and display the max value and the index of this max. Display the Even elements. Sorts and displays the numbers from lowest to highest using Arrays.sort() method from java.util.Arrays class.
|
|
Describe your idea and analyze complexity of your solution
: Describe your idea and analyze the complexity of your solution. Give O(N) algorithm to solve the problem. Analyze the complexity of your algorithm. Describe your approach and analyze the complexity of your algorithm.
|
|
Purpose of an organizational chart
: In 2-3 paragraphs, explain the purpose of an organizational chart and what it accomplishes for a healthcare organization. Discuss the limitations of what an organizational chart communicates and how an organizational chart can be used for strateg..
|
|
Concept of backward scheduling
: Explain the concept of backward scheduling and give examples of how you use backward scheduling in your personal life. (Question 7, page 546)
|
|
Price of shorter-term bond when interest rates change
: An investor has two bonds in his portfolio that have a face value of $1,000 and pay a 10% annual coupon. Bond L matures in 15 years, while Bond S matures in 1 year. Why does the longer-term bond’s price vary more than the price of the shorter-term bo..
|
|
Operations and supportive of the organizational goals
: In three or four paragraphs, describe the organizational structure at your current or most recent place of employment, Do you think it is appropriate to the operations and supportive of the organizational goals?
|