1-Write programs to implement the algorithm of HW#1(Part-1) and compute the CPU

Question

1-Write programs to implement the algorithm of HW#1(Part-1) and compute the CPU time for different sets of unsigned integers generated by a random number generator Write an efficient function that compute the intersections of two sorted arrays of integers Write an efficient function that compute the intersection of two arrays of integers (not necessary sorted) 1. 2. 2. Write programs to implement the algorithmofHW#1(Part#2) using HashSet and BitSet structure) and compute the CPU time for different set of integers generated by a random number generator Test both parts using the same data sets: at least three of size 1000 integers, at least three of size 10000 integers, at least three of size 100000, at least three of size one million integers, and at least three of size 10 million integers Summarize the CPUT times using the following table format. Use system.nanoTime) to compute the cpu time This is the HW#1 HW 1 if (a1 a2]) CFU time for CPU of sorted CPU time for CPUof orting the arrays data set using algorithm(Part1)arrays using arrays using arrays using o Java sort function CPU af unserted Data Set unsorted unsorted else elgorithms of Hasiset Partll (sum of the previous two columns BitStt cout

Explanation / Answer

I am going to answer last 2 question (intersection of two arrays)

1 ) compute intersection of two arrays of integer(with soring)

code :

import java.util.Arrays;

class Intersection
{
  
   // will print intersection of array[0 to array.length-1]
   void Intersec(int array1[], int array2[], int m, int n)
   {
       // array1 must be array1[0 to m-1]
       if (m > n)
       {
           int tempp[] = array1;
           array1 = array2;
           array2 = tempp;

           int temp = m;
           m = n;
           n = temp;
       }

       // sort the array1
       Arrays.sort(array1);

      
       for (int i = 0; i < n; i++)
       {
           if (binarySearch(array1, 0, m - 1, array2[i]) != -1)
               System.out.print(array2[i] + " ");
       }
   }

   //return the position of x
   int binarySearch(int arr[], int l, int r, int x)
   {
       if (r >= l)
       {
           int mid = l + (r - l) / 2;

      
           if (arr[mid] == x)
               return mid;

          
           if (arr[mid] > x)
               return binarySearch(arr, l, mid - 1, x);

      
           return binarySearch(arr, mid + 1, r, x);
       }

  
       return -1;
   }

   // test the programe
   public static void main(String[] args)
   {
       Intersection obj = new Intersection();
       int array1[] = {6, 0, 4, 1, 2, 5};
       int array2[] = {2, 8, 5, 18, 6};
       int m = array1.length;
       int n = array2.length;
       System.out.println("Intersection : ");
       obj.Intersec(array1, array2, m, n);
   }
}

2 ) compute intersection of two array(without sorting)

code :

import java.util.Arrays;

class Intersection
{
  
   // will print intersection of array[0 to array.length-1]
   void Intersec(int array1[], int array2[], int m, int n)
   {
       // array1 must be array1[0 to m-1]
       if (m > n)
       {
           int tempp[] = array1;
           array1 = array2;
           array2 = tempp;

           int temp = m;
           m = n;
           n = temp;
       }

      
   // dont sort the array1

      
       for (int i = 0; i < n; i++)
       {
           if (binarySearch(array1, 0, m - 1, array2[i]) != -1)
               System.out.print(array2[i] + " ");
       }
   }

   //return the position of x
   int binarySearch(int arr[], int l, int r, int x)
   {
       if (r >= l)
       {
           int mid = l + (r - l) / 2;

      
           if (arr[mid] == x)
               return mid;

          
           if (arr[mid] > x)
               return binarySearch(arr, l, mid - 1, x);

      
           return binarySearch(arr, mid + 1, r, x);
       }

  
       return -1;
   }

   // test the programe
   public static void main(String[] args)
   {
       Intersection obj = new Intersection();
       int array1[] = {6, 0, 4, 1, 2, 5};
       int array2[] = {2, 8, 5, 18, 6};
       int m = array1.length;
       int n = array2.length;
       System.out.println("Intersection : ");
       obj.Intersec(array1, array2, m, n);
   }
}

I hope you will understand the code. fell free to ask a question if you have a doubt

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

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