Consider the following set of candidate 3-itemsets: {p,q,r},{p,q,s},{p,q,t},{p,r,s},{p,r,t},{q,r,s},{q,r,t},{q,s,t},{r,s,t}. (a) (7 pts) Construct a binary hash tree for storing the above 3 -itemsets. Assume the hash tree uses a hash function where items p,r,t are hashed to the left child of a node, while items q,s,u are hashed to the right child. A candidate k-itemset is inserted into the tree by hashing on each successive item in the candidate and then following the appropriate branch of the tree according to the hash value. Once a leaf node is reached, the candidate is inserted based on one of the following conditions: Condition 1: If the depth of the leaf node is equal to k (the root node is assumed to be at depth 0 ), then the candidate is added to the leaf node irrespective of the number of itemsets already stored at the node. Condition 2: If the depth of the leaf node is less than k, then the candidate is added to the leaf node as long as the number of itemesets already stored at the leaf node is less than maxsize =2. Otherwise, change the leaf node into an internal node and distribute the candidates (including the new candidate to be added) to its children based on their respective hash values. Note: It is possible that a node will become non-existent (should be removed) if its parent node become a leaf (where some itemsets are stored). For example, If node 7 becomes a leaf node by having one itemset, then its children nodes, 14 and 15 , will be removed from the tree. (b) (7 pts) Suppose all the candidate 3-itemsets above are frequent. List all candidate 4itemsets that can be generated from the frequent 3itemsets using the candidate generation procedure for Apriori. (c) (7 pts) List all candidate 4-itemsets that survive the candidate pruning step of the Apriori algorithm. (d) (4 pts) Based on the list of frequent 3-itemsets given above, is it possible to generate a frequent 5-itemset