Question
Project 1: Brute Force Algorithm for the Element Uniqueness Problem Please write a complete working code in Java. In this project, you will implement the
Project 1: Brute Force Algorithm for the Element Uniqueness Problem Please write a complete working code in Java. In this project, you will implement the brute force algorithm discussed in Module 1 for the "Element Uniqueness Problem." Each of you have been assigned two 'm' values that correspond to the maximum value for an element in the array. The two 'm' values are independent of each other and should be considered separately. For a particular 'm' value, the values for the array size 'n' are: 0.1m, 0.2m, 0.3m, 0.4m, 0.5m, 0.6m, 0.7m, 0.8m, 0.9m, m. For example, if m = 100, the values of the array size 'n' are: 10, 20, 30, 40, 50, 60, 70, 80, 90, 100. As part of your code, you should generate an array of size 'n' whose values are generated randomly in the range [1...m]. Your algorithm should keep track of the number of comparisons needed to determine whether the array of random elements (generated as above) is unique or not. You should run your algorithm/code several times (say, 10000 times using an automated loop) for each (n, m) pair and determine the average number of comparisons. For each of the two 'm' values (with 'n' varying from 0.1m to m as described above), plot the values for 'n' vs. the average number of comparisons for the n value. Maximum Possible value (m) of the elements in your arrays: m values: (500, 5000) Your code should be written in Java. A word document containing the two Excel plots (as required above for each 'm' value) and your explanation interpreting the results are to be included in your assigment. Start up code: public class Brute_Force_Project_1 { import java.util.*; class ElementUniqueness{ public static void main(String[] args){ try{ Scanner input = new Scanner(System.in); System.out.print("Enter the maximum integer value: "); int mValue = input.nextInt(); int numTrials = 10000; Random randGen = new Random(System.currentTimeMillis()); for (double nFraction = 0.1; nFraction <= 1.0; nFraction += 0.1){ int totalComparisons = 0; int arraySize = (int) (nFraction*mValue); for (int trials = 1; trials <= numTrials; trials++){ int array[] = new int[arraySize]; for (int index = 0; index < array.length; index++){ array[index] = 1 + randGen.nextInt(mValue); } // Implement here the brute force algorithm to test for uniqueness // we will start with the assumption that the array // has unique elements and could break from the loops from testing // for uniqueness once we come across a pair that is not unique }// trials loop System.out.println(nFraction+" "+arraySize+" "+(((double) totalComparisons)/numTrials)); }// nFraction loop } catch(Exception e){e.printStackTrace();} } }
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started