Your cart is currently empty!
For this lab you will implement several methods to determine if an array of integers in a certain range contains duplicate elements. First, you need to write a method that receives two integers n and m and builds and returns an array of length n that contains random integers in the 0 to m −…
For this lab you will implement several methods to determine if an array of integers in a certain range contains duplicate elements. First, you need to write a method that receives two integers n and m and builds and returns an array of length n that contains random integers in the 0 to m − 1 range. Then implement the following methods to determine if the array contains duplicates:
public static boolean hasDuplicates(int []A){
boolean duplicates = false;
for (int i=0;i<A.length;i++)
for (int j=0;j<A.length;j++)
if (A[i]==A[j] && i!=j)
duplicates = true;
return duplicates;
}
Write a method that sorts the array using selection sort, then finds duplicates by performing a single pass through the sorted array.
Use a Boolean array S of length m to indicate if elements in the array have been seen before. Then determine if there are duplicates by performing a single pass through the unsorted array.
Determine the big-O running time of each of the previous methods. Run experiments with several different values of n and m (with m < n) and determine the running times with respect to n and illustrate this by means of plots or tables. Discuss whether the theoretical results match the outcomes of the experiments, making sure you evaluate the algorithms’ behavior with a wide range of values of n. Write a report discussing your work, as described in the syllabus.