This is the code i need the table and graph if the array size is 1 then 2 then 3
ID: 3675151 • Letter: T
Question
This is the code i need the table and graph if the array size is 1 then 2 then 3 then 4 the 5
- Your Statistics ( ArraySize-execution time ) table and graph
- Compare your results with the expected selection algorithm running time
import java.util.HashSet;
import java.util.Scanner;
public class Median
{
//BSelect by Blum, Floyd, Pratt, Rivest, Tarjon (1972)
//@Author Kishore Ravindran
//@Date of Creating 21-Feb-2011
//Algorithm: DeterministicSelect
//Step 1: Break n elements into blocks of 5 each.
//Step 2: Compute the median of each 5-element block in constant time.
//Step 3: Collect together the n/5 medians and recursively compute their median.
//Step 4: Chose the resulting element as a pivot
public static void main (String[] args)
{
System.out.println("Please enter the size of the array");
Scanner myscan = new Scanner(System.in);
// Handle InputMismatchException exception here;
int number = myscan.nextInt();
Integer [] input = new Integer[number];
System.out.println("Please enter the array elements");
System.out.println("");
for(int i=0;i<number;i++)
{
input[i] = myscan.nextInt();
}
System.out.println("Enter a number less than the size of the array");
System.out.println("");
// Check and InputMismatchException exception needs to be handled here;
number = myscan.nextInt();
Median m = new Median();
System.out.println("The " + number + "th smallest element in the input is " + m.DeterministicSelect(input, number));
}
// simple module to find the median of a array
int median(Integer[] array)
{
if (array.length == 1)
{
return array[0];
}
int smallerCount = 0;
for (int i = 0 ; i < array.length ; i++)
{
for (int j = 0 ; j < array.length ; j++)
{
if (array[i] < array[j])
{
smallerCount++;
}
}
if (smallerCount == (array.length - 1)/2)
{
return array[i];
}
smallerCount = 0;
}
return -1; //should never happen
}
// finds pivot element of a given array recursively using DeterministicSelect
int Pivot(Integer[] array)
{
if (array.length == 1)
{
return array[0];
}
//Divide A into n/5 groups of 5 elements each
int numGroups = array.length / 5;
if (array.length % 5 > 0)
{
numGroups++;
}
Integer[] setOfMedians = new Integer[numGroups];
for (int i = 0 ; i < numGroups ; i++)
{
Integer[] subset;
if(array.length % 5 > 0)
{
if (i == numGroups - 1)
{
subset = new Integer[array.length % 5];
}
else
{
subset = new Integer[5];
}
}
else
{
subset = new Integer[5];
}
for (int j = 0; j < subset.length ; j++)
{
subset[j] = array[5*i+j];
}
//Find the median of each group
setOfMedians[i] = median(subset);
}
//Use DeterministicSelect to find the median, p, of the n/5 medians
int goodPivot = DeterministicSelect(setOfMedians, setOfMedians.length/2 );
return goodPivot;
}
//The algorithm in words:
//1. Divide n elements into groups of 5
//2. Find median of each group (How? How long?)
//3. Use Select() recursively to find median x of the n/5? medians
//4. Partition the n elements around x. Let k = rank(x)
//5. if (i == k) then return x else (i > k) use Select() recursively to find (i-k)th
//smallest element in last partition
//source
//Lecture PDF mentioned in the blog post
//and MIT Lecture 6 order statistics.
int DeterministicSelect(Integer[] array, int k)
{
if (array.length == 1)
{
return array[0];
}
int pivot = Pivot(array);
//set is used to ignore duplicate values
HashSet<Integer> A1 = new HashSet<Integer>();
HashSet<Integer> A2 = new HashSet<Integer>();
for (int i = 0; i < array.length ; i++)
{
if (array[i] < pivot)
{
A1.add(array[i]);
}
else if (array[i] > pivot)
{
A2.add(array[i]);
}
}
if (A1.size() >= k)
{
return DeterministicSelect(A1.toArray(new Integer[0]) ,k);
}
else if (A1.size() == k-1)
{
return pivot;
}
else
{
return DeterministicSelect(A2.toArray(new Integer[0]) , k - A1.size() - 1);
}
}
}
A selection problem is a problem to find the kth order static element from a set of n distinct numbers. Input: a set A of n distinct numbers (unsorted) and an integer k. Output: the element x which is larger than k-1 other elements in A. Read Sections 9.2 & 9.3 from the text book (Untroduction to algorithms by Cormen, Leiserson Stein 2nd or 3rd edition The presented selection algorithm depend on divide-and-conquer algorithm and the expected running time O(n).The important part in this algorithm is choosing the pivot for partitioning (randomly or median-of-medians) Implement the selection algorithm Lusing both method of selecting the pivot) using an object oriented programming language. Your code should be readable and well designed with a strategy pattern. (read about a strategy pattern) Run your code multiple times with different size of Array A, display your results in x-y plane where: X is the Size of the array Y is the execution time Requirements: - Reading sections 9.2 & 9.3 from text book - Reading about the strategy pattern Submission: each student should submit a soft-copy (upload in OCS) and a hard-copy (in class) including the following: - Readable, well designed program code (add comment for clarification) - Your Statistics (ArraySize-execution time) table and graplh Compare your results with the expected selection algorithm running timeExplanation / Answer
startPage.java
import java.io.IOException;
import java.util.Scanner;
public class startPage {
@SuppressWarnings("resource")
public static void main(String args[]) throws IOException {
System.out.println("Choose among the following : 1: Random-Number-Uniform-Distribution-Generation " +
"2: Random-Number-Normal-Distribution-Generation " +
"3: Top-k-Random " +
"4: KthSmallest 5: KthSmallest-Random-Pivot 6: Top-k-MedianOfMedian ");
Scanner scanner = new Scanner(System.in);
String choice = scanner.next();
choose(choice);
}
public static void choose(String choice) throws IOException {
switch(choice) {
case "1":
RandomNumber rm = new RandomNumber();
rm.randomNumber_uniform_dist();
break;
case "2":
RandomNumberNormalDist rmd = new RandomNumberNormalDist();
rmd.randomNumber_normal_dist();
break;
case "3":
TopkRandom topk = new TopkRandom();
topk.TopkRandom();
break;
case "4":
KthSmallest ks = new KthSmallest();
ks.kthsmallest();
break;
case "5":
KthSmallestRandomPivot ksrp = new KthSmallestRandomPivot();
ksrp.Kthsmallestrandompivot();
break;
case "6":
TopKMedian topm = new TopKMedian();
topm.TopkMedian();
break;
default:
System.out.println("Program exited!");
break;
}
}
}
KthSmallest.java
import java.io.File;
import java.io.FileReader;
import java.util.HashSet;
import java.util.Scanner;
public class KthSmallest
{
public void kthsmallest()
{
try{
//Read the data form the input file
System.out.println("Select the random numbers to work on: 1.Normal Distribution data 2.Uniform Distribution");
Scanner s = new Scanner(System.in);
String choice = s.next();
FileReader inputFile = null;
switch(choice){
case "1":
inputFile = new FileReader("random_normal_dist.txt");
break;
case "2":
inputFile = new FileReader("random.txt");
break;
default:
System.out.println("Enter a valid choice either 1 or 2");
break;
}
if(inputFile!=null){
Scanner sc = new Scanner(inputFile);
String[] firstLine;
int i=0;
firstLine = sc.nextLine().split(" ");
int number = Integer.parseInt(firstLine[1]);
int size = Integer.parseInt(firstLine[0]);
float[] input = new float[size];
while(sc.hasNext()){
input[i]=Float.parseFloat(sc.nextLine());
i++;
}
//Divide A into n/3,5 or 7 groups of 3,5 or 7 elements each
System.out.println("Divide in groups of 3, 5 or 7 or random pivot (R)?: ");
Scanner scn =new Scanner(System.in);
int tmp = scn.nextInt();
int groupSize = 0;
if(tmp == 3){
groupSize = 3;
}
else if(tmp == 5){
groupSize = 5;
}
else if(tmp == 7){
groupSize = 7;
}
else
System.out.println("Invalid number");
KthSmallest m = new KthSmallest();
double stime = System.nanoTime();
System.out.println(stime);
System.out.println("The " + number + "th smallest element in the input is " + m.select(input, number, groupSize));
double etime = System.nanoTime();
System.out.println(etime);
double time = etime-stime;
System.out.println("time= "+time);
}
}
catch(Exception e){
e.printStackTrace();
}
}
//find the median of a array
float median(float[] array)
{
if (array.length == 1)
{
return array[0];
}
int scount = 0;
for (int i = 0 ; i < array.length ; i++)
{
for (int j = 0 ; j < array.length ; j++)
{
if (array[i] < array[j])
{
scount++;
}
}
if (scount == (array.length - 1)/2)
{
return array[i];
}
scount = 0;
}
return -1;
}
// finds pivot element of a given array recursively using DeterministicSelect
float Pivot(float[] array, int groupSize)
{
if (array.length == 1)
{
return array[0];
}
int groups = array.length / groupSize;
if (array.length % groupSize > 0)
{
groups++;
}
float[] setOfMedians = new float[groups];
for (int i = 0 ; i < groups ; i++)
{
float[] subset;
if(array.length % groupSize > 0)
{
if (i == groups - 1)
{
subset = new float[array.length % groupSize];
}
else
{
subset = new float[groupSize];
}
}
else
{
subset = new float[groupSize];
}
for (int j = 0; j < subset.length ; j++)
{
subset[j] = array[groupSize*i+j];
}
//Find the median of each group
setOfMedians[i] = median(subset);
}
//Use select to find the median, p, of the n/5 medians
float goodPivot = select(setOfMedians, setOfMedians.length/2, groupSize );
return goodPivot;
}
float select(float[] array, int k, int groupSize)
{
if (array.length == 1)
{
return array[0];
}
float pivot = Pivot(array, groupSize);
//set is used to ignore duplicate values
HashSet<Float> A1 = new HashSet<Float>();
HashSet<Float> A2 = new HashSet<Float>();
for (int i = 0; i < array.length ; i++)
{
if (array[i] < pivot)
{
A1.add(array[i]);
}
else if (array[i] > pivot)
{
A2.add(array[i]);
}
}
if (A1.size() >= k)
{
float[] r = new float[A1.size()];
java.util.Iterator<Float> i =A1.iterator();
int index=1;
r[0] = i.next();
while(i.hasNext() && index<A1.size()){
r[index] = i.next();
index++;
}
return select(r ,k, groupSize);
}
else if (A1.size() == k-1)
{
return pivot;
}
else
{
float[] r = new float[A2.size()];
java.util.Iterator<Float> i =A2.iterator();
int index=1;
r[0] = i.next();
while(i.hasNext() && index<A2.size()){
r[index] = i.next();
index++;
}
return select(r , k - A1.size() - 1, groupSize);
}
}
}
KthSmallestRandomPivot.java
import java.io.File;
import java.io.FileReader;
import java.util.HashSet;
import java.util.Scanner;
public class KthSmallestRandomPivot
{
public void Kthsmallestrandompivot(){
{
try{
System.out.println("Select the random numbers to work on: 1.Normal Distribution data 2.Uniform Distribution");
Scanner s = new Scanner(System.in);
String choice = s.next();
FileReader inputFile = null;
switch(choice){
case "1":
inputFile = new FileReader("random_normal_dist.txt");
break;
case "2":
inputFile = new FileReader("random.txt");
break;
default:
System.out.println("Enter a valid choice either 1 or 2");
break;
}
if(inputFile!=null){
//Read the data form the input file
Scanner scn = new Scanner(inputFile);
String[] firstLine;
int i=0;
firstLine = scn.nextLine().split(" ");
int number = Integer.parseInt(firstLine[1]);
int size = Integer.parseInt(firstLine[0]);
float[] input = new float[size];
while(scn.hasNext()){
input[i]=Float.parseFloat(scn.nextLine());
i++;
}
KthSmallestRandomPivot m = new KthSmallestRandomPivot();
double stime = System.nanoTime();
System.out.println(" The " + number + "th smallest element in the input is " + m.select(input, number));
double etime = System.nanoTime();
double time = etime-stime;
System.out.println("time= "+time);
}
}
catch(Exception e){
e.printStackTrace();
}
}
}
// finds pivot element of a given array recursively using select
float Pivot(float[] array)
{
return array[0];
}
float select(float[] array, int k)
{
if (array.length == 1)
{
return array[0];
}
float pivot = Pivot(array);
//set is used to ignore duplicate values
HashSet<Float> A1 = new HashSet<Float>();
HashSet<Float> A2 = new HashSet<Float>();
for (int i = 0; i < array.length ; i++)
{
if (array[i] < pivot)
{
A1.add(array[i]);
}
else if (array[i] > pivot)
{
A2.add(array[i]);
}
}
if (A1.size() >= k)
{
float[] r = new float[A1.size()];
java.util.Iterator<Float> i =A1.iterator();
int index=1;
r[0] = i.next();
while(i.hasNext() && index<A1.size()){
r[index] = i.next();
index++;
}
return select(r ,k);
}
else if (A1.size() == k-1)
{
return pivot;
}
else
{
float[] r = new float[A2.size()];
java.util.Iterator<Float> i =A2.iterator();
int index=1;
r[0] = i.next();
while(i.hasNext() && index<A2.size()){
r[index] = i.next();
index++;
}
return select(r , k - A1.size() - 1);
}
}
}
TopKMedian.java
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.io.PrintStream;
import java.util.Scanner;
public class TopKMedian {
public void TopkMedian() throws IOException {
int n,i;
System.out.println("Select the random numbers to work on: 1.Normal Distribution data 2.Uniform Distribution");
Scanner s = new Scanner(System.in);
String choice = s.next();
FileReader inputFile = null;
switch(choice){
case "1":
inputFile = new FileReader("random_normal_dist.txt");
break;
case "2":
inputFile = new FileReader("random.txt");
break;
default:
System.out.println("Enter a valid choice either 1 or 2");
break;
}
if(inputFile!=null){
//Read the data form the input file
BufferedReader br = new BufferedReader(inputFile);
//Take only the 1st argument that is the array size
String n1 = br.readLine().toString();
String[] n2 = n1.split(" ");
n = Integer.valueOf(n2[0]);
int k = Integer.valueOf(n2[1]);
float arr[] = new float[n];
for(i = 0; i<n;i++){
arr[i] = Float.valueOf(br.readLine().toString());
}
//Divide A into n/3,5 or 7 groups of 3,5 or 7 elements each
System.out.println("Divide in groups of 3, 5 or 7");
Scanner scn =new Scanner(System.in);
int groupSize = scn.nextInt();
if(!(groupSize==3 || groupSize==5 || groupSize==7))
{
System.out.println("Enter a valid number:");
}
else{
//Check if the array length is empty
if (arr.length == 0) {
System.out.println("Empty Array");
System.exit(0);
}
//Check if the array length is one
else if (arr.length == 1) {
System.out.println("Array has one element");
}
else {
//Else call top k method to find top k elements
TopKGenerateMedian topme = new TopKGenerateMedian();
double stime = System.nanoTime();
System.out.println(stime);
topme.topk(arr, 0, n-1, k, groupSize);
double etime = System.nanoTime();
System.out.println(etime);
double time = etime-stime;
System.out.println("time= "+time);
}
//write the output into the new file
File ranfile = new File("Top_k_Median_of_Median.txt");
@SuppressWarnings("resource")
PrintStream write = new PrintStream(ranfile);
for (i = arr.length-1; i >= arr.length - k; i--){
write.println(arr[i]+" ");
}
}
}
}
}
TopkRandom.java
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.io.PrintStream;
import java.util.Scanner;
public class TopkRandom {
public void TopkRandom() throws IOException {
int n,i;
System.out.println("Select the random numbers to work on: 1.Normal Distribution data 2.Uniform Distribution");
Scanner s = new Scanner(System.in);
String choice = s.next();
FileReader inputFile = null;
switch(choice){
case "1":
inputFile = new FileReader("random_normal_dist.txt");
break;
case "2":
inputFile = new FileReader("random.txt");
break;
default:
System.out.println("Enter a valid choice either 1 or 2");
break;
}
if(inputFile!=null){
//Read the data form the input file
@SuppressWarnings("resource")
BufferedReader br = new BufferedReader(inputFile);
//Take only the 1st argument that is the array size
String n1 = br.readLine().toString();
String[] n2 = n1.split(" ");
n = Integer.valueOf(n2[0]);
//Take second argument as k
int k = Integer.valueOf(n2[1]);
System.out.println(k);
System.out.println("first no "+n);
//Create a new array to put all the data read from the file
float arr[] = new float[n];
for(i = 0; i<n;i++){
arr[i] = Float.valueOf(br.readLine().toString());
}
//Check if the array length is empty
if (arr.length == 0) {
System.out.println("Empty Array");
System.exit(0);
}
//Check if teh array length is one
else if (arr.length == 1) {
System.out.println("Array has one element");
}
else {
//Else call topk method to find top k elements
TopKGenerate top = new TopKGenerate();
double stime = System.nanoTime();
top.topk(arr, 0, arr.length-1, arr.length-k);
double etime = System.nanoTime();
double time = etime-stime;
System.out.println("time= "+time);
}
//write the output into the new file
File ranfile = new File("Top_k_Random.txt");
@SuppressWarnings("resource")
PrintStream write = new PrintStream(ranfile);
for (i = arr.length-k; i <= arr.length - 1; i++){
write.println(arr[i]+" ");
}
}
}
}
TopKGenerate.java
import java.util.Random;
public class TopKGenerate {
public static void topk(float[] array, int l, int n, int k){
//calls the method topk which calls partition to find random pivot
int pivotIndex = partition(array, l, n);
if(pivotIndex == k){
return;
}
//Call partition recursively from first to pivot - 1
else if(k < pivotIndex){
topk(array, l, pivotIndex -1, k);
}else{
//Call partition recursively from pivot+1 to n
topk(array, pivotIndex +1 , n, k);
}
}
public static int partition(float[] array, int p, int q) {
//Pick a random Pivot
Random rand = new Random();
int pivotIndex = p + rand.nextInt(q - p + 1);
float temp1 = array[pivotIndex];
array[pivotIndex] = array[p];
array[p]=temp1;
float x = array[p];
System.out.println("x= "+x);
int i = p;
for (int j = (p + 1); j <= q; j++) {
if (array[j] <= x) {
i = i + 1;
if(i < j){
float temp = array[j];
array[j] = array[i];
array[i] = temp;
}
}
}
float temp2 = array[p];
array[p] = array[i];
array[i] = temp2;
return i;
}
}
RandomNumberNormalDist.java
import java.io.File;
import java.io.FileNotFoundException;
import java.io.PrintStream;
import java.util.Random;
import java.util.Scanner;
public final class RandomNumberNormalDist {
public void randomNumber_normal_dist() throws FileNotFoundException{
RandomNumberNormalDist gaussian = new RandomNumberNormalDist();
int MEAN = 1000000;
int VARIANCE = 800000;
int i,n,k,firstrange,lastrange;
@SuppressWarnings("resource")
Scanner scanner = new Scanner(System.in);
System.out.println("Enter the number of random numbers to be generated");
n = scanner.nextInt();
System.out.println("Enter the kth element");
k = scanner.nextInt();
File ranfile = new File("random_normal_dist.txt");
@SuppressWarnings("resource")
PrintStream write = new PrintStream(ranfile);
write.println(n+" "+k);
for (i= 1; i<= n; ++i){
write.println(Math.abs(gaussian.getGaussian(MEAN, VARIANCE)));
}
}
private Random fRandom = new Random();
private float getGaussian(int aMean, int aVariance){
float num = (int) (aMean + fRandom.nextGaussian() * aVariance);
return num;
}
}
TopKGenerateMedian.java
import java.util.HashSet;
public class TopKGenerateMedian {
public void topk(float[] array, int l, int n, int k, int groupSize){
int pivotIndex = partition(array, l, n, k, groupSize);
if(pivotIndex == k){
return;
}
else if(k < pivotIndex){
topk(array, l, pivotIndex -1, k,groupSize);
}
else{
topk(array, pivotIndex +1 , n, k,groupSize);
}
}
public static int partition(float[] array, int f, int n, int k, int groupSize) {
int i = f;
int j = n;
float tmp;
//Choose pivot as median of medians
float pivot = select(array, k, groupSize);
while (i <= j) {
//Take all the elements less than the pivot and move to the left of the array
while (array[i] < pivot)
i++;
//Take all the elements more than the pivot and move to the right of the array
while (array[j] > pivot)
j--;
if (i <= j) {
tmp = array[i];
array[i] = array[j];
array[j] = tmp;
i++;
j--;
}
};
return i;
}
static float select(float[] array, int k, int groupSize)
{
if (array.length == 1)
{
return array[0];
}
float pivot = Pivot(array, groupSize);
//set is used to ignore duplicate values
HashSet<Float> A1 = new HashSet<Float>();
HashSet<Float> A2 = new HashSet<Float>();
for (int i = 0; i < array.length ; i++)
{
if (array[i] < pivot)
{
A1.add(array[i]);
}
else if (array[i] > pivot)
{
A2.add(array[i]);
}
}
if (A1.size() >= k)
{
float[] r = new float[A1.size()];
java.util.Iterator<Float> i =A1.iterator();
int index=1;
r[0] = i.next();
while(i.hasNext() && index<A1.size()){
r[index] = i.next();
index++;
}
return select(r ,k, groupSize);
}
else if (A1.size() == k-1)
{
return pivot;
}
else
{
float[] r = new float[A2.size()];
java.util.Iterator<Float> i =A2.iterator();
int index=1;
r[0] = i.next();
while(i.hasNext() && index<A2.size()){
r[index] = i.next();
index++;
}
return select(r , k - A1.size() - 1, groupSize);
}
}
static float Pivot(float[] array, int groupSize)
{
if (array.length == 1)
{
return array[0];
}
int groups = array.length / groupSize;
if (array.length % groupSize > 0)
{
groups++;
}
float[] setOfMedians = new float[groups];
for (int i = 0 ; i < groups ; i++)
{
float[] subset;
if(array.length % groupSize > 0)
{
if (i == groups - 1)
{
subset = new float[array.length % groupSize];
}
else
{
subset = new float[groupSize];
}
}
else
{
subset = new float[groupSize];
}
for (int j = 0; j < subset.length ; j++)
{
subset[j] = array[groupSize*i+j];
}
//Find the median of each group
setOfMedians[i] = median(subset);
}
//Use select to find the median, p, of the n/5 medians
float goodPivot = select(setOfMedians, setOfMedians.length/2, groupSize );
return goodPivot;
}
static float median(float[] subset)
{
if (subset.length == 1)
{
return subset[0];
}
int scount = 0;
for (int i = 0 ; i < subset.length ; i++)
{
for (int j = 0 ; j < subset.length ; j++)
{
if (subset[i] < subset[j])
{
scount++;
}
}
if (scount == (subset.length - 1)/2)
{
return subset[i];
}
scount = 0;
}
return -1;
}
}
RandomNumber.java
import java.io.File;
import java.io.FileNotFoundException;
import java.io.PrintStream;
import java.util.Random;
import java.util.Scanner;
public class RandomNumber {
public void randomNumber_uniform_dist() throws FileNotFoundException {
int i,n,k,firstrange,lastrange;
@SuppressWarnings("resource")
Scanner scanner = new Scanner(System.in);
Random random = new Random();
firstrange = 1;
lastrange = 100000;
System.out.println("Enter the number of random numbers to be generated");
n = scanner.nextInt();
System.out.println("Enter the kth element");
k = scanner.nextInt();
File ranfile = new File("random.txt");
@SuppressWarnings("resource")
PrintStream write = new PrintStream(ranfile);
write.println(n+" "+k);
for (i= 1; i<= n; ++i){
if (firstrange > lastrange) {
throw new IllegalArgumentException("Wrong Range. Example (1,1000)");
}
long range = (long)lastrange - (long)firstrange + 1;
long f = (long)(range * random.nextDouble());
float randomNumber = (f + firstrange);
write.println(randomNumber);
}
System.out.println("Random Numbers Generated in random.txt file");
write.close();
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.