Hi,

I'm having a hard time figuring out how to make the below algorithm compile but also run in linear time. The more I look at it the more I'm getting confused and don't know what to do. Also, I'm supposed to complete test cases and submit test data, but I have never done that before and don't know what it actually means. Thanks for any help.

This is the question followed by what I have:

1. It should be able to accept as input 0 to k collections, stored as simple arrays. Were restricting the data structure to arrays since we havent 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, in all 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.

5. Your algorithm should designate one of the collections as the query collection, which is the collection that will be compared against the other collections.

7. Your algorithm may manipulate the input collections as needed to accomplish its purpose.

8. 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 The type of the argument is an array of Comparable arrays. 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, the following statement: 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. It is important that you adhere to the framework specification above. To facilitate testing of your program, I will use a test harness that will do the following:

1. Creates an instance of your CommonElements class.

2. Calls your findCommonElements method with a set of test collections as input.

3. Verifies that the collection that is returned by findCommonElements correctly contains the elements common to all the input collections.

4. Retrieves the number of comparisons that were performed, via your getComparisons() method.

5. Compares the number of comparisons performed to the target value stated in criterion #5 above for the algorithm. Thus, it is essential that you name your class and methods as described above, or my test harness will not work, and it will take longer to test your program. If your code doesnt meet the above specifications, I will notify you to change your implementation so that it meets the specifications I have described above.

A Note About Testing:

You will need to develop several sets of test collections for testing your algorithm. The grading rubric mentions covering the case where all the test collections have the same length, as well as covering the case where the test collections are of different lengths. You will also need to think about what constitutes the worst case scenario for this algorithm, since only that scenario will make your analysis of total comparisons performed a meaningful one. You can use the formulas in the grading rubric to tell you how many comparisons you should expect in the quadratic and linear cases. For example, if you have 5 total collections (1 query collection and 4 test collections), each of which contains 10 elements, the total number of comparisons performed in the worst case should be: (k - 1)N2, which for k = 10 and N = 10 is: (5 - 1)102, or 400 comparisons. For the linear algorithm, you should only have N*(k - 1), which is 10*(5 - 1), or 40 comparisons.

Some Hints:

1. This algorithm can be implemented without using higher order data structures, so dont assume the solution lies in using something we havent discussed in class.

2. In order to achieve the most efficient algorithm you will need to do some processing of the collections before you start trying to find the common elements. Think about what weve talked about thus far, and see if you can apply any of it to your solution.

3. Dont forget to handle special cases. It is valid to have an empty set of collections as input, as well as a set of collections that contains only a single collection.

4. You can make your algorithm more efficient if you abort a search as soon as you have determined that a given element is either common to all collections, or it is not.

5. Keep in mind that once you have determined whether an element is common to all collections or not, you should not need to use that element in any further comparisons, since it is impossible for the commonality of that element to change.

Code I have:

import java.*; import java.util.Arrays;

public class CommonElements { public static void main(String[] args) { int comparisons; Comparable[] col_1 = {3,4,1,2}; Comparable[] col_2 = {6,7,8,9}; Comparable[] col_3 = {1,2,3,4}; Comparable[][] collections = {col_1, col_2, col_3}; findCommonElements(collections);

}

public static Comparable[] findCommonElements(Comparable[][] collections){ int n = collections[0].length; Comparable[] returnNum = new Comparable[n]; int j = 0; for (int i = 0; i < collections.length; i++) collections[i] = Arrays.sort(collections[i]);

for (int i = 0; i < n; i++){ int count = 1; for (int k = 1; k < collections.length; k++){

if (bin_search(collections[0][i], collections[k]) == true) count += 1; }

if (count == collections.length) returnNum[j] = collections[0][i]; } return returnNum; } }