A.Amazon product purchases: A buyer usually buys more than one item from an online site. When you go to a shopping site, and are thinking about buying a product, you may have seen other product recommendations based on the product you are about to buy. These shopping sites promote products for sale using the idea Customers who bought this item also bought these other items. For instance, if you bought printer ink, the products recommended for you might include paper, pen, pencils, etc.
Find attached a dataset amazon0302.txt . This data was collected from the Amazon website about products that were co-purchased in the year 2003. You can also directly download the dataset from https://snap.stanford.edu/data/amazon0302.html For simplicity, product names are replaced with integers, 0,1,2, etc., in the dataset. Each product with an integer label can be represented as a node in a graph. If an item p was frequently co-purchased with item q, then you can represent the relationship as a directed edge q to p in the directed graph. In the dataset, you will find two integers per line a fromNodeId and a toNodeId which is the same as saying q to p. As an example, you can say that item 3 was frequently co-purchased with item 0, hence there will be an edge from node 0 to node 3. But there is no edge from 3 to 0 and hence it is not symmetrical. (Take a look at the first several lines of the dataset). Your goal is to do the following:
1.You will write Java code to build a directed graph G=(V,E) where |V|= 262,111 and |E|=1,234,877. In other words, there are a total of 262,111 nodes and 1,234,877 edges that you will create by reading in the dataset. You will pay close attention to storage efficiency and run-time efficiency. We discussed several data structures for creating and storing a graph in class and Java code for them, which you may consider as such or with further modifications. Not all of them may be appropriate for this problem in terms of efficiency.
2.Your code will have a void printStatistics() method which will provide answer to the following question: What is the maximum number of items co-purchased with a product over all products? Please make sure that the answer is for over all products and not for a particular product. In the example on question 3 below, the answer would be 2, because two items (0 and 1) were co-purchased with product 3 and all others had only one item that was co-purchased.
3.Your code will have a method void popularProduct() that prints out the most popular product that was co-purchased frequently over all product purchases and its frequency. As an example, if there are only four products 0, 1,2, 3 and the edges are 0->1, 1->2, 2->3, 3->1, and 3->0, then the most popular product that is co-purchased is product 1 with frequency 2, because product 1 is co-purchased with products 0, and 3. Other products have less co-purchase frequency.
4.Your code will have a method void productTwins() which will print out the number of distinct pairs of products that are purchased together. For instance, , if there are only four products 0, 1,2, 3 and the edges are 0->1, 0->3, 1->2, 2->1, 2->3, 3->1, and 3->0, then productTwins() will print out 2 as the answer. This is because there are two productTwins namely, (0,3), and (1,2). These refer to symmetrical edges( 0->3, 3->0) and ( 1->2, 2->1). In the dataset, you can see that (0,2) is a productTwin, among others.
5.Estimate the storage complexity for the graph in terms of number of bytes or using big-Oh notation. What is the time complexity of popularProduct() and productTwins() method using big-Oh notation?
You are not allowed to process the data file and change its contents for building the graph or solving the problems. You will not get any credit if you tried that approach. The first four lines of the data file contain information about the data. These lines can be deleted, if you like. That is the only modification that is allowed. Furthermore, for all the questions 1 through 4 above, efficiency in storage and time-complexity is of utmost importance and 50% of the credit is assigned to these criteria. Correctness accounts for the remaining 50%.
B. Consider the following recursive function F(n) defined for all integer values 0,1,2,3, etc.
F(0)=0, F(1)=1, and F(2)=2 (or F(i) =i if i=0,1,2 )
F(n)=F(n-1)+F(n-3) for n>=3
No code is needed. Draw the stack-tree diagram for computing F(6) and show the computed value.
C.For the input (9,7,3,17,10,15,6,8,75,22,57,6) where each number is presented to the build-heap algorithm in the left-to-right order, show the diagram of the final max-heap. I do not need to see the intermediate steps, just the last step when the max- heap is fully constructed.
(ii) Can you say anything, in general, as to where the minimum value might be found in a max-heap? Please do not provide the answer for the above example but a general observation regardless of the data.
D.Write Java code for extending the LinkedList< E >class of java.util.* to ExtLinkedList< E > that includes the following two methods:
public ExtLinkedList < E> oddList()
public ExtLinkedList< E> evenList()
Method oddList() will return a linked list containing the nodes with odd index values, namely, 1,3,5, etc. and evenList() will return a linked list containing the nodes with even index values namely, 0,2,4,... etc. Your code should work for any size including the empty list and any parameter E and should be as efficient as possible. If the original list contains only one node, then oddList() will return an empty list. Estimate the run-time complexity of the methods assuming the size of the original list is n.
E. For space-efficient, hashing using linear probing that we discussed in class and in the homework 7, please find the attached Java code. Your objective is to write a single method remove() as follows:
public boolean remove(String s) {
}
// removes the string s from the hash table, if found and returns True. If not found, returns false.