Describe your idea and analyze complexity of your solution

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

Reference no: EM131310002

Questions Cloud

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?

Reviews

Write a Review

Programming Languages Questions & Answers

  Write a haskell program to calculates a balanced partition

Write a program in Haskell which calculates a balanced partition of N items where each item has a value between 0 and K such that the difference b/w the sum of the values of first partition,

  Create an application to run in the amazon ec2 service

In this project you will create an application to run in the Amazon EC2 service and you will also create a client that can run on local machine and access your application.

  Explain the process to develop a web page locally

Explain the process to develop a Web page locally

  Write functions

These 14 questions covers java class, Array, link list , generic class.

  Programming assignment

If the user wants to read the input from a file, then the output will also go into a different file . If the user wants to read the input interactively, then the output will go to the screen .

  Write a prolog program using swi proglog

Write a Prolog program using swi proglog

  Create a custom application using eclipse

Create a custom Application Using Eclipse Android Development

  Create a application using the mvc architecture

create a application using the MVC architecture. No scripting elements are allowed in JSP pages.

  Develops bespoke solutions for the rubber industry

Develops bespoke solutions for the rubber industry

  Design a program that models the worms behavior

Design a program that models the worm's behavior.

  Writing a class

Build a class for a type called Fraction

  Design a program that assigns seats on an airplane

Write a program that allows an instructor to keep a grade book and also design and implement a program that assigns seats on an airplane.

Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd