Part 1
Mining information from sales data is a common task in both traditional and online stores. Past sales information can guide purchasing and enable the company to make recommendations to customers about what they may like to buy.
Part 1 performs two data mining tasks. First, it determines the ranking of products according to how many of each product has been sold. Second, it also determines the five other products most commonly bought with each product.
While these tasks are not particularly complex, performing these tasks on large data sets is computationally expensive and the use of data structures and algorithms that facilitate fast searching and sorting is desirable.
Requirements
Write a Java program called SalesInfoMiner that reads in a file of products, stored in text format (2 lines per entry). The program must then read in information about past sales transactions and output all the products to a new file, sorted by product description, along with their sales rank and the five other products with which they were most commonly purchased.
The program accepts four command line arguments and must not expect any user interaction from the keyboard. The first parameter to the program is the name of the product list to read in; the second parameter is the file containing information about past transactions. The third parameter is the name of the file to which the ordered product list will be written, and the fourth parameter is the name of the file to which any error or warning messages will be output.
Product File
This file contains data for one or more products
- Each product occupies two lines
- Line 1 contains the product id, which is a string of 13 digits
- Product IDs are unique
- Line 2 is the description of the product, which is not an empty string
- You can assume that the file is not empty.
Thus, the data for a product has the format shown below:
(A thirteen digit string)
(A text string)
For example:
1234567890123
Milk - full cream 600ml
9832983102938
Bread - wholemeal loaf
1299128391283
Eggs, Extra Large, Barn laid
Sales Transaction File
This file contains data for one or more sale transactions
- Each sale transaction has 2 + n lines, where n is the number of items in this sale transaction (as specified on line 2 of the sale transaction)
- Line 1 has the format Receipt number: where is a positive integer
- Receipt numbers are unique
- Line 2 has the format Number of items: where is a positive integer
- Each sale item occupies a line, which contains the product id of the item
- All product IDs in a sale transaction are distinct and must exist in the product file
- You can assume that the file is not empty
Thus, data for a sale has the format shown below:
Receipt number: ( is an integer)
Number of items: ( is an integer)
...
For example:
Receipt number: 1
Number of items: 3
1234567890123
9832983102938
1299128391283
Receipt number: 2
Number of items: 4
9832983102938
1234567890123
1299128391283
1234567890123
Product Output File
- For each product, the program determines its sale transaction count, i.e. number of transactions that the product appears in.
- The program lists the products in an output file, sorted by sale transaction count, in decreasing order.
- When there is a tie in the sale transaction count, the products are listed in alphabetical order of their descriptions (see example below)
- For each product, the program also lists the top 5 products that are most frequently bought with this product.
- The "top 5" list may have less than 5 products. It can also have for than 5 due to ties.
Whenever there is a tie in the frequency, the products are listed in alphabetical order of their descriptions (see example below)
- The format is as shown below
Product:
ID:
Sales Count:
This product was purchased most often with:
1: () -
2: () -
3: () -
4: () -
5: () -
For example:
Product: Milk - full cream 600ml
ID: 1234567890123
Sales Count: 82
This product was purchased most often with:
1: (1299128391283) Eggs, Extra Large, Barn laid [8]
2: (9832983102938) Bread - wholemeal loaf [5]
3: (3289742398473) Apples - Golden Delicious [4]
4: (9348029348934) Chocolate, Dark, 200g [4]
5: (3024823094839) Noodles, Udon - Fresh 250g [4]
6: (0002011106917) Nuts, almonds, dry roasted [4]
Product: Pork - cured, ham, separable fat, boneless
ID: 0000140956153
Sales Count: 82
This product was purchased most often with:
. . .
"Sales count" is the number of transactions that a product appears in. The numbers in square brackets are the number of transactions a product appears with another product
Calculating the most frequent items purchased with a product: With every product, we need to output the 5 other items with which it was most frequently purchased. These other items must be listed in order of frequency. The item listed at position 1 would have been bought more frequently with the item than the item at position 2, and so on. Though we are interested in the "top 5", the list may have more than five items due to ties. In that case, more than five items are to be included and items involved in a tie are to be ordered by product description. If a product has not been bought with 5 other items, then less than 5 items are output.
Error File
In the sales transaction file, a sales transaction "record" is considered to include all the lines from the line starting with "Receipt number"
? Up to, but not included, the next line starting with "Receipt number:"
? Or up to the end of the file.
When a particular line does not conform, as expected, to the description given above,
? the error should be detected
? an error message is written to the error file (the fourth command-line argument), which indicate
o the type of the error
o the file in which the error occurs
o and the line number of the line on which the error occurs
? no result (i.e. listing of products as described in Section B) is output, i.e. the product output file (the third command-line-argument) is empty.
? and the program terminates
Based on the specification in Section A, Based on the descriptions of the product file (the first command-line-argument) and the transaction file (the second command-line-argument), we can have the following types of data error (in addition to errors such as file
does not exists, etc.)
For product file:
1. Product ID is invalid - not consisting of 13 digits
2. Product description is empty/missing
3. Product ID is not unique
For sales transaction file:
1. Line 1 of a sale transaction does not start with "Receipt number:"
2. Receipt number (on line 1) is not a positive integer
3. Line 2 of a sale transaction does not start with "Number of items:"
4. Number of items (on line 2) is not a positive integer
5. Product ID does not consists of 13 digits
6. Product ID in a sale transaction has duplicates
7. Product ID does not exist in the product file
8. There are not enough product ID's listed for a particular transaction (i.e. less than the number listed on line 2)
The error messages will have the following format:
ERROR:
For example:
ERROR: Invalid Product ID
Product 8763726273678 in receipt 4 is not in the product file
Product discarded, processing of transaction continued
The program is terminated
You can assume that in the sales transaction file
o There are no blank lines
o There are no duplicated receipt numbers
Restriction on the Use of Classes in the Java Collection Framework
Except for ArrayList and Linkedlist, you are not permitted to use any other classes in the Java Collection Framework.
Testing Your Program
You will test your program against some large data sets, which will be posted on LMS. When testing your program against large data set, please do not run your program on the latcs6 server, use the simula server instead. For some large data sets you may need to request, especially when you test your program on Windows, more memory by using the -Xmx option of the java command.
Execution of the Program
The program will be run with the following command:
java SalesInfoMiner
If an incorrect number of arguments is supplied, then the program must output an error message explaining the arguments required before terminating.
Part 2
(a) In terms of the big-oh notation, what is the complexity of the gnome sort for the average case? Justify your answer. The justification can be based on approximate calculations.
Hint: Initially m (the "marker") is at position 1. After a number of comparisons (and swapping), m is at position 2 for the first time. Then after a number of comparisons, m is at position 3 for the first time. Now, suppose m is at position i, approximately how many comparisons would it take for it to advance to position i + 1 for the first time?
(b) Using the classes GnomeSort and RandomIntegerArray given below, write a program to generate some numerical data to verify your answer for the gnome sort's complexity.
Include your answers in the report. Part 2 is worth 10 marks.
public class GnomeSort
{
/* Performs the gnome sort and returns the number of comparisons
*/
public static long sort(int [] a)
{
int m = 1; // m for 'marker', the place from which we
// compare the element with the one on the
// left to see if we should move left or right
long comparisons = 0; // to count the number of comparisons
// for the sorting
while(true)
{
if (m == a.length) // m is past the last element,
{ // the sorting is done
break;
}
else if (m == 0) // m is at the beginning of the array,
{ // move right
m = 1;
}
else if (a[m] >= a[m-1]) // the element at m is greater than or
{ // equal to the element on the left,
m++; // move right
comparisons++;
}
else // the element at m is < the element
{ // on the left, swap the two elements
int temp = a[m]; // and move to the left
a[m] = a[m-1];
a[m-1] = temp;
m--;
comparisons++;
}
}
return comparisons;
}
}
public class RandomIntegerArray
{
/* Return an array of size n, of random integers of value
btween 0 and n, inclusively
*/
public static int [] getRandomIntegerArray(int n)
{
int [] a = new int[n];
for(int i = 0; i < n; i++)
{
a[i] = (int) (Math.random() * (n+1));
}
return a;
}
}