Here is the original question: I need to make a more efficient algorithm for fin
ID: 3871757 • Letter: H
Question
Here is the original question:
I need to make a more efficient algorithm for finding the common elements of a set of collections. Ideally, the goal is to achieve an algorithm that will only need to perform at most on the order of (k - 1)N comparisons. This can only be achieved if each element in the non-query collections only participates in at most 1 comparison (with a few exceptions).
The algorithm should satisfy the following criteria:
1. It should be able to accept as input 0 to k collections, stored as simple arrays. We’re restricting the data structure to arrays since we haven’t covered higher order data
structures yet.
2. The elements of the collections should all be of type Comparable, and they should all be derived from the same base class (not counting the Object class). Implementation of the Comparable interface is necessary since the elements must be compared to each other in order to determine commonality. They must all be derived from the same base class since
comparisons between different data types is undefined.
3. Duplicate elements should be allowed; e.g., if there are M instances of the value, “XYZ”, inall the input collections, there should be M instances of the value, “XYZ”, in the collection of common elements.
4. The collections should be allowed to be of varying lengths; i.e., some collections may have more items than others.
5. One of the collections must be designated as the “query” collection, which is the collection containing the elements to which the elements in the other collections are compared.
6. The total number of element comparisons performed should be less than the value for the quadratic solution described above. That is, the total number of comparisons in the worst
case should be less than (k - 1)N2. Do not be concerned about average performance or best case performance. Also, the total number of comparisons is defined, for this assignment, to
be only those comparisons that are performed once the traversal of the query collection begins, and the other collections are checked for the presence of the elements in the query
collection. Any comparisons performed to manipulate the data prior to searching for the common elements should be ignored.
The framework for your algorithm should satisfy the following criteria, for ease in testing:
1. Create a class called CommonElements, to contain your algorithm and associated methods and attributes.
2. In your CommonElements class, encapsulate your algorithm within a method called findCommonElements, that has the following signature:
public Comparable[] findCommonElements(Comparable[][] collections).
The argument to this method, collections, will be the set of k collections discussed earlier. Each collection will be represented as an array of objects of type Comparable. Note that in
Java, a 2D array will support arrays of varying sizes provided it is initialized without first specifying the two dimensions. For example:
Comparable[][] collections = {{“A”}, {“A”, “B”}, {“A”, “B”, “C”}};
results in an array of 3 Comparable arrays of varying sizes. The following syntax also works:
Comparable[] col_1 = {“A”};
Comparable[] col_2 = {“A”, “B”};
Comparable[] col_3 = {“A”, “B”, “C”};
Comparable[][] collections = {col_1, col_2, col_3};
3. The value returned by your findCommonElements method should be a collection of Comparable elements that contains only the elements common to all the input collections.
4. Since you are being asked to evaluate your algorithm based on the number of comparisons performed, you will need to have your findCommonElements method maintain a running total
of comparisons performed for each set of collections tested. You should create an attribute called comparisons in your CommonElements class to store the number of comparisons, and
provide a getter method called getComparisons() to return this value. In order to keep a running total of comparisons, you will need to instrument your code by incrementing the
comparisons attribute each time a comparison between two elements is made. Since element comparisons are typically performed in if statements, you may need to increment
comparisons immediately before each comparison is actually performed. Although that may sound counter-intuitive, if you try to increment comparisons inside the if statement, after
the element comparison has been made, you will miss all the comparisons that cause the condition inside the if statement to evaluate to false.
Here is the code I have, can you help me get it to properly compile?
//Define a class
public class CommonElements <T> implements Comparable <T>
{
//Declare variable
private int comparisons = 0;
//Define array
private Comparable[][]mArray;
//Define a constructor
CommonElements()
{
}
//Define a constructor
CommonElements(Comparable [][] collections)
{
//Assign value
mArray=collections;
}
//Define a method
public Comparable [] findCommonElements(Comparable[][]collections)
{
//Try
try
{
//Call method
insertionSort(collections);
}
//Catch
catch(NullPointerException e)
{
//Display message
System.out.println("Error: Empty Array!");
}
//Define array
Comparable [] lCmmnCllctn;
//If length greater than 0
if(collections.length > 0)
{
//Create new instance
lCmmnCllctn = new Comparable[collections[0].length];
//Create instance
Comparable [] lQryCllctn = createQuery(collections);
//Create instance
Comparable [][] lOthrCllctn = createOther(collections);
//Declare variable
int lFll = 0;
//Loop
for(Comparable query : lQryCllctn)
{
//Declare variable
boolean lMtch = true;
//Loop
for(int li = 0; li < lOthrCllctn.length; li++)
{
//Loop
for(int lj = 0; lj <lOthrCllctn[li].length; lj++)
{
//Increment
comparisons++;
//If value matches
if(query.compareTo(lOthrCllctn[li][lj])==0)
{
//Assign value
lMtch = true;
//Break
break;
}
//Otherwise
else
//Assign value
lMtch = false;
}
}
//If value is true
if(lMtch == true)
{
//Assign value
lCmmnCllctn[lFll] = query;
//Increment value
lFll++;
}
}
}
//Otherwise
else
{
//Assign value
lCmmnCllctn = createQuery(collections);
}
//Return
return lCmmnCllctn;
}
//Define a method
public int getComparisons()
{
//Return
return comparisons;
}
//Define a method
public Comparable[][] getArray()
{
//Return
return mArray;
}
//Define a method
public void lStArry(Comparable[][]collections)
{
//Assign value
mArray = collections;
}
//Define a method
private Comparable[] createQuery(Comparable[][]collections)
{
//Create an instance
Comparable[]lQryCllctn = new Comparable[collections.length];
//Loop
for(int li = 0; li<collections[0].length; li++)
{
//Assign value
lQryCllctn[li] = collections[0][li];
}
//Return
return lQryCllctn;
}
//Define a method
private Comparable[][] createOther(Comparable[][]collections)
{
//Create instance
Comparable[][]lOthrCllctn = new Comparable[collections.length-1][];
//Loop
for(int li = 1; li<collections.length; li++)
{
//Loop
for(int lj = 0; lj<collections[li].length; lj++)
{
//Assign value
lOthrCllctn[li][lj] = collections[li][lj];
}
}
//Return
return lOthrCllctn;
}
//Define a method
private Comparable[][] insertionSort(Comparable[][]collections)
{
//Loop
for(int lj = 0; lj<collections.length; lj++)
{
//Loop
for(int li = 1; li < collections[lj].length; li++)
{
//Assign value
Comparable firstUnsorted = collections[lj][li];
//Assign index
int index = li - 1;
//Loop
while(index >= 0 && firstUnsorted.compareTo(collections[lj][index]) <0)
{
//Assign value
collections[lj][index + 1] = collections[lj][index];
//Decrement
index--;
}
//Assign value
collections[lj][index + 1] = firstUnsorted;
}
}
//Return
return collections;
}
//Define a method
public void toString(Comparable[][]collections)
{
//Loop
for(int li = 0; li<collections.length; li++)
{
//Loop
for(int lj = 0; lj<collections[li].length; lj++)
{
//Display message
System.out.println("Set " + li + ": " + collections[li][lj]);
}
}
}
//Define a method
public void toString(Comparable[]collections)
{
//Loop
for(int li = 0; li<collections.length; li++)
{
//Display message
System.out.println("Set " + li + ": " + collections[li]);
}
}
//Override
@Override
//Define a method
public <T> int compareTo(T other)
{
//Compare
if(this.compareTo(other)<0 || this.compareTo(other)>0)
//Return
return Integer.signum(this.compareTo(other));
//Otherwise
else
//Return
return 0;
}
}
Explanation / Answer
As asked for removal of compilation error below is the code which will compile properly and won't change the functionality of the code:
//Define a class
public class CommonElements<T> implements Comparable<T> {
// Declare variable
private int comparisons = 0;
// Define array
private Comparable[][] mArray;
// Define a constructor
CommonElements() {
}
// Define a constructor
CommonElements(Comparable[][] collections) {
// Assign value
mArray = collections;
}
// Define a method
public Comparable[] findCommonElements(Comparable[][] collections) {
// Try
try {
// Call method
insertionSort(collections);
}
// Catch
catch (NullPointerException e) {
// Display message
System.out.println("Error: Empty Array!");
}
// Define array
Comparable[] lCmmnCllctn;
// If length greater than 0
if (collections.length > 0) {
// Create new instance
lCmmnCllctn = new Comparable[collections[0].length];
// Create instance
Comparable[] lQryCllctn = createQuery(collections);
// Create instance
Comparable[][] lOthrCllctn = createOther(collections);
// Declare variable
int lFll = 0;
// Loop
for (Comparable query : lQryCllctn) {
// Declare variable
boolean lMtch = true;
// Loop
for (int li = 0; li < lOthrCllctn.length; li++) {
// Loop
for (int lj = 0; lj < lOthrCllctn[li].length; lj++) {
// Increment
comparisons++;
// If value matches
if (query.compareTo(lOthrCllctn[li][lj]) == 0) {
// Assign value
lMtch = true;
// Break
break;
}
// Otherwise
else
// Assign value
lMtch = false;
}
}
// If value is true
if (lMtch == true) {
// Assign value
lCmmnCllctn[lFll] = query;
// Increment value
lFll++;
}
}
}
// Otherwise
else {
// Assign value
lCmmnCllctn = createQuery(collections);
}
// Return
return lCmmnCllctn;
}
// Define a method
public int getComparisons() {
// Return
return comparisons;
}
// Define a method
public Comparable[][] getArray() {
// Return
return mArray;
}
// Define a method
public void lStArry(Comparable[][] collections) {
// Assign value
mArray = collections;
}
// Define a method
private Comparable[] createQuery(Comparable[][] collections) {
// Create an instance
Comparable[] lQryCllctn = new Comparable[collections.length];
// Loop
for (int li = 0; li < collections[0].length; li++) {
// Assign value
lQryCllctn[li] = collections[0][li];
}
// Return
return lQryCllctn;
}
// Define a method
private Comparable[][] createOther(Comparable[][] collections) {
// Create instance
Comparable[][] lOthrCllctn = new Comparable[collections.length - 1][];
// Loop
for (int li = 1; li < collections.length; li++) {
// Loop
for (int lj = 0; lj < collections[li].length; lj++) {
// Assign value
lOthrCllctn[li][lj] = collections[li][lj];
}
}
// Return
return lOthrCllctn;
}
// Define a method
private Comparable[][] insertionSort(Comparable[][] collections) {
// Loop
for (int lj = 0; lj < collections.length; lj++) {
// Loop
for (int li = 1; li < collections[lj].length; li++) {
// Assign value
Comparable firstUnsorted = collections[lj][li];
// Assign index
int index = li - 1;
// Loop
while (index >= 0 && firstUnsorted.compareTo(collections[lj][index]) < 0) {
// Assign value
collections[lj][index + 1] = collections[lj][index];
// Decrement
index--;
}
// Assign value
collections[lj][index + 1] = firstUnsorted;
}
}
// Return
return collections;
}
// Define a method
public void toString(Comparable[][] collections) {
// Loop
for (int li = 0; li < collections.length; li++) {
// Loop
for (int lj = 0; lj < collections[li].length; lj++) {
// Display message
System.out.println("Set " + li + ": " + collections[li][lj]);
}
}
}
// Define a method
public void toString(Comparable[] collections) {
// Loop
for (int li = 0; li < collections.length; li++) {
// Display message
System.out.println("Set " + li + ": " + collections[li]);
}
}
// Override
@Override
// Define a method
public int compareTo(T other) {
// Compare
if (this.compareTo(other) < 0 || this.compareTo(other) > 0)
// Return
return Integer.signum(this.compareTo(other));
// Otherwise
else
// Return
return 0;
}
}