1.The Apriori algorithm makes use of prior knowledge of subset support properties:
a. Prove that all nonempty subsets of frequent itemsets must also be frequent?
b. Prove that the support of any nonempty subset s' of itemset s must be at least as great as the support of s?
2. Most frequent pattern mining algorithms consider only distinct items in a transaction. However, multiple occurrences of an item in the same shopping basket, such as 4 cakes and 3 jugs of milk, can be important in transactional data analysis. How can one mine frequent itemsets efficiently considering multiple occurrences of items? Propose modification to the well-known algorithms, such as Apriori and FP-growth to adapt to such situation?
3. We wish to use the Flajolet Martin algorithm (Section 4.4) to count the number of distinct elements in a stream. Assume that there are 10 possible elements {1, 2, ..., 10} that could appear in the stream but only 4 of them have actually appeared. To make our estimate of the count of distinct elements, we hash each element to a 4-bit binary number. Element X is hashed to {(3X + 7) modulo 11}. For example element 8 hashes to 3*8+7 = 31 modulo 11 = 9 which maps into the 4-bits (1001). A set of 4 of the elements 1 through 10 could give an estimate that is exact (if the estimate is 4) or too high or too low. Figure out under Page 2 of 2
what circumstances a set of the following 4 elements give the exact correct estimate:
a. (2,6,8,10)
b. (1,3,9,10)
c. (3,7,8,10)
d. (1,6,7,10)
e. (4,5,6,7)
f. (2,5,7,10)
g. (4,5,6,10)
h. (1,3,6,8)
i. (1,2,3,9)
4. A bipartite graph has nodes ai and bi for i = 0, 1,..., 5. There is an edge between ai and bi if i-j is divisible by 2 or 3. For example, a0 is connected to b0, b2, b3, and b4. Also, a3 is connected to b0, b1, b3, and b5. Another way to understand this graph is to realize that ai is connected to bj unless j = i+i or j = i-1, where arithmetic is modulo 6. Say a complete bipartite subgraph is maximal if no nodes can be added to it and the "complete" property be maintained. Which of the following instances of K2,2 is NOT maximal?
a. {a2, a5, b2, b5}
b. {a0, a3, b0, b3}
c. {a1, a3, b3, b5}
d. {a2, a3, b0, b5}