Question: Java For Each Of The Algorithms Unique1 And Unique2, Whi

Link will be apear in 30 seconds.

Well done! you have successfully gained access to Decrypted Link.

 

Question:

Java

For each of the algorithms unique1 and unique2, which solve the element uniqueness problem, perform an experimental analysis to determine the largest value of n such that the given algorithm runs in one minute or less. Hint: Do a type of “binary search” to determine the maximum effective value of n for each algorithm.

public static boolean unique1(int[] data) {
    int n = data.length;
    for (int j=0; j < n-1; j++)
      for (int k=j+1; k < n; k++)
        if (data[j] == data[k])
          return false;                    // found duplicate pair
    return true;                           // if we reach this, elements are unique
  }

  /** Returns true if there are no duplicate elements in the array. */
  public static boolean unique2(int[] data) {
    int n = data.length;
    int[] temp = Arrays.copyOf(data, n);   // make copy of data
    Arrays.sort(temp);                     // and sort the copy
    for (int j=0; j < n-1; j++)
      if (temp[j] == temp[j+1])            // check neighboring entries
        return false;                      // found duplicate pair
    return true;                           // if we reach this, elements are unique
  }

---

Answer:

Java code:

import java.util.concurrent.TimeUnit;
import java.lang.Math;
import java.util.Arrays;

public class timeSearch
{
public static boolean unique1(int [] data,int n)
{
    //int n=data.length;
    for(int j=0;j<n-1;j++)
    {
        for(int k=j+1;k<n;k++)
        {
            if(data[j]==data[k])
                return(false);
        }
    }
    return(true);
}

public static boolean unique2(int [] data,int n)
{
    int []temp=Arrays.copyOf(data,n);
    Arrays.sort(temp);
    for(int j=0;j<n-1;j++)
    {
        if(temp[j]==temp[j+1])
            return(false);
    }
    return(true);
}

public static void main(String args[])
{
    int sz=(int)Math.pow(2,20);
    int data[]= new int[sz];
    int i;

    for(i=0;i<sz;i++)    //fill array
    {
        data[i]=sz-i+1;
    }

    long startTime,endTime,totalTime;

    i=1;
    totalTime=0;
    while(totalTime/Math.pow(10,6)<1)
    {
        startTime = System.nanoTime();
        unique1(data,i);
        endTime   = System.nanoTime();
        totalTime = endTime - startTime;
        i++;
    }

    System.out.println("Value of n for which unique1 takes 10^(-6)second(1 microsecond):"+i);

    totalTime=0;
    i=1;
    while(totalTime/Math.pow(10,6)<1)
    {
        startTime = System.nanoTime();
        unique2(data,i);
        endTime   = System.nanoTime();
        totalTime = endTime - startTime;
    i++;
    }
    System.out.println("Value of n for which unique1 takes 10^(-6)second(1 microsecond):"+i);
}
}

output: