What You Need to Do: If we were only interested in two relatively small collections, as shown in Table 3, the quadratic algorithm described above may be adequate. However, if N is very large, and/or there are many collections (i.e., k is very large), the quadratic algorithm may be too slow to be useful. There are a number of strategies that can be employed to reduce the running time, and at this point we have covered enough topics to design a more efficient algorithm. Based on the material covered thus far in this course, design and implement a more efficient algorithm for finding the common elements of a set of collections. Your algorithm should satisfy the following criteria: 1. It should be able to accept as input 0 to k collections, stored as simple arrays. 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 in order for comparisons between two items to be meaningful. 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; 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 kN2. Do not be concerned about average 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. 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(Object[] 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. 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.

Game Pittsburgh Steelers Baltimore Ravens Seattle Seahawks Indianapolis Colts Houston Texans Tennessee Titans Jacksonville Jaguars Arizona Cardinals New England Patriots Baltimore Ravens Cincinnati Bengals bye weelk Kansas City Chiefs Cincinnati Bengals Cleveland Browns San Francisco 49ers St. Louis Rams Cleveland Browns Baltimore Ravens Pittsburgh Steelers Tennessee Titans St. Louis Rams New York Jets bye weelk Houston Texans Jacksonville Jaguars Arizona Cardinals Pittsburgh Steelers Seattle Seahawks Cincinnati Bengals San Francisco 49ers Cleveland Browns Indianapolis Colts San Diego Chargers Cleveland Browns Cincinnati Bengals 2 4 7 8 9 10 12 13 15 16 17 Table 1. Regular season opponents of the Pittsburgh Steelers and Baltimore Ravens, listed in the order in which the games were played. Note that each team had a "bye" week, during which they did not play Common opponents are indicated in bold Seattle Seahawks Indianapolis Colts Houston Texans Tennessee Titans Jacksonville Jaguars Arizona Cardinals Cincinnati Bengals Cincinnati Bengals Cleveland Browns San Francisco 49ers St. Louis Rams Cleveland Browns Table 2. One possible correct result showing all common elements (duplicates included) between the two collections in Table 1 C1 Baltimore Ravens Seattle Seahawks Indianapolis Colt:s Houston Texans Tennessee Titans Jacksonville Jaguars Arizona Cardinals New England Patriots Baltimore Ravens Cincinnati Bengals bye week Kansas City Chiefs Cincinnati Bengals Cleveland Browns San Francisco 49ers St. Louis Rams Cleveland Browns C2 Pittsburgh Steelers Tennessee Titans St. Louis Rams New York Jets bye week Houston Texans Jacksonville Jaguars Arizona Cardinals Pittsburgh Steelers Seattle Seahawks Cincinnati Bengals San Francisco 49ers Cleveland Browns Indianapolis Colt:s San Diego Chargers Cleveland Browns Cincinnati Bengals Table 3. Regular season opponents of the Steelers and Ravens, with the bye weeks eliminated, generi cally referred to as C1 and C2, respectively Game Pittsburgh Steelers Baltimore Ravens Seattle Seahawks Indianapolis Colts Houston Texans Tennessee Titans Jacksonville Jaguars Arizona Cardinals New England Patriots Baltimore Ravens Cincinnati Bengals bye weelk Kansas City Chiefs Cincinnati Bengals Cleveland Browns San Francisco 49ers St. Louis Rams Cleveland Browns Baltimore Ravens Pittsburgh Steelers Tennessee Titans St. Louis Rams New York Jets bye weelk Houston Texans Jacksonville Jaguars Arizona Cardinals Pittsburgh Steelers Seattle Seahawks Cincinnati Bengals San Francisco 49ers Cleveland Browns Indianapolis Colts San Diego Chargers Cleveland Browns Cincinnati Bengals 2 4 7 8 9 10 12 13 15 16 17 Table 1. Regular season opponents of the Pittsburgh Steelers and Baltimore Ravens, listed in the order in which the games were played. Note that each team had a "bye" week, during which they did not play Common opponents are indicated in bold Seattle Seahawks Indianapolis Colts Houston Texans Tennessee Titans Jacksonville Jaguars Arizona Cardinals Cincinnati Bengals Cincinnati Bengals Cleveland Browns San Francisco 49ers St. Louis Rams Cleveland Browns Table 2. One possible correct result showing all common elements (duplicates included) between the two collections in Table 1 C1 Baltimore Ravens Seattle Seahawks Indianapolis Colt:s Houston Texans Tennessee Titans Jacksonville Jaguars Arizona Cardinals New England Patriots Baltimore Ravens Cincinnati Bengals bye week Kansas City Chiefs Cincinnati Bengals Cleveland Browns San Francisco 49ers St. Louis Rams Cleveland Browns C2 Pittsburgh Steelers Tennessee Titans St. Louis Rams New York Jets bye week Houston Texans Jacksonville Jaguars Arizona Cardinals Pittsburgh Steelers Seattle Seahawks Cincinnati Bengals San Francisco 49ers Cleveland Browns Indianapolis Colt:s San Diego Chargers Cleveland Browns Cincinnati Bengals Table 3. Regular season opponents of the Steelers and Ravens, with the bye weeks eliminated, generi cally referred to as C1 and C2, respectively