Description
Create an 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
N (k – 1) comparisons, where N is the number of elements in the query set and k is the total number of
sets in the collection. This can only be achieved if each element in the non-query collections only
participates in at most 1 comparison (with a few exceptions)
– 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.
– 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.
– Duplicate elements should be allowed; e.g., if there are M instances of the value, “XYZ”, in all the
input collections, there should be M instances of the value, “XYZ”, in the collection of common
elements.
– The collections should be allowed to be of varying lengths; i.e., some collections may have more
items than others.
– 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.
– 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 N^2 (k – 1). 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:
– Create a class called CommonElements, to contain your algorithm and associated methods and attributes.
– 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};
– 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.
– 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.
