Project 1: Brute Force Algorithm for the Element Uniqueness Problem Please write

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 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();}
}
}

Explanation / Answer

Please find the java program with the method brute force for array element uniqueness below:

-----------------------------------

Sample run output:

Enter the maximum integer value: 500
0.1 50 453.3814
0.2 100 489.4747
0.30000000000000004 150 493.2829
0.4 200 496.827
0.5 250 491.1422
0.6 300 507.7942
0.7 350 495.2703
0.7999999999999999 399 501.0665
0.8999999999999999 449 495.4296
0.9999999999999999 499 496.4506

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.