Answered step by step
Verified Expert Solution
Link Copied!
Question
1 Approved Answer

In Java: First: Define a Rectangle class (in Rectangle.java) that implements RectangleInterface. In addition, you should implement the Comparable interface, such that Rectangle objects can

In Java:

First:

Define a Rectangle class (in Rectangle.java) that implements RectangleInterface. In addition, you should implement the Comparable interface, such that Rectangle objects can be compared by their perimeter. That is, your class signature should be:

public class Rectangle implements RectangleInterface, Comparable 

Then:

Write a GenericMethods class (in GenericMethods.java) that implements GenericMethodsInterface.

There are two methods you must implement:

  • linearSearch: Iterate through the array linearly and search for a value equal (again, in the Comparable sense) to x. This must run in O(n) time. If the value is not found in the array, return -1. Else, return the index in the array where the value was found.
  • binarySearch: Implement a recursive binary search to find a value equal to x. Hint: The public binarySearch method, itself, should not be recursive. The private helper method should be. This private helper method with additional parameters should be called from the public binarySearch method. This must run in O(log n) time. If the value is not found in the array, return -1. Else, return the index in the array where the value was found.

To test your code, you might try creating a file with a main method that does the following:

  • Build an array of Rectangle objects
  • Demonstrate linearSearch functionality on the array
  • Sort the array with Arrays.sort (remember, input to binarySearch must be sorted)
  • Demonstrate binarySearch functionality on the array

Your GenericMethods class must implement the interface.

Next:

In a file called BigO.java, implement BigOInterface and write methods that have the following runtime requirements:

  • cubic must be O(n^3)
  • exp must be O(2^n)
  • constant must be O(1)

Where n is an integer which is passed into the function. The methods can contain any code fragments of your choice. However, in order to receive any credit, the runtime requirements must be satisfied. As in the previous two problems, you must implement the interface to receive full credit.

In addition to writing the code fragments, we will explore their actual runtimes, to observe big-O in action in the real world. In a file called Problem3.java write a main method which runs the code with various values of n and measures their runtime. Then, discuss the results you observed briefly in a file called Problem3.txt.

To properly time code runtime in Java, we must disable compiler optimizations. We do this by running the code with the -Xint flag, for example: java -Xint Problem3. The easiest way to time your run is to wrap each fragment with the following code:

long startTime = System.nanoTime(); // YOUR CODE HERE long endTime = System.nanoTime(); 

The elapsed time is the difference between these two variables.

You may see slightly erratic results due to noise and memory allocation delays. This is one of the factors you discuss in addressing outliers.

BigOInterface.java

public interface BigOInterface {

public void cubic(int n); public void exp(int n); public void constant(int n); }

GenericMethodsInterface.java

public interface GenericMethodsInterface {

public > int binarySearch(AnyType[] a, AnyType x); public > int linearSearch(AnyType[] a, AnyType x); }

Rectangles.java

public class Rectangle implements RectangleInterface, Comparable { }

RectangleInterface.java

public interface RectangleInterface { public double getLength(); public double getWidth(); }

Step by Step Solution

There are 3 Steps involved in it

Step: 1

blur-text-image
Get Instant Access to Expert-Tailored Solutions

See step-by-step solutions with expert insights and AI powered tools for academic success

Step: 2

blur-text-image_2

Step: 3

blur-text-image_3

Ace Your Homework with AI

Get the answers you need in no time with our AI-driven, step-by-step assistance

Get Started

Recommended Textbook for

Mastering Apache Cassandra 3 X An Expert Guide To Improving Database Scalability And Availability Without Compromising Performance

Authors: Aaron Ploetz ,Tejaswi Malepati ,Nishant Neeraj

3rd Edition

1789131499, 978-1789131499

More Books

Students explore these related Databases questions