Homework 1
CS522, Fall 2008

Due: Wednesday, October 8

• Chapter 3, 4.1 (except 4.1.4), and 4.2 of the textbook.

[Exercises]

For each exercise, you must explain your reasoning and/or show the intermediate steps, i.e. not just giving the final result.

1. (10pt) Exercise 3.5

2. (10pt) Exercise 3.13

3. (10pt) Exercise 4.1

4. (10pt) Exercise 4.4

5. (10pt) Consider the following dataset with three dimensions A={a1,a2}, B={b1,b2,b3}, C={c1,c2,c3,c4} and the measure SUM:

(a2,b1,c1,2)
(a1,b2,c2,3)
(a2,b3,c2,2)
(a1,b3,c4,4)
(a1,b1,c3,3)
(a2,b3,c3,2)

List all the cells in the iceberg cube with min_sup > 2 in the order produced by the BUC algorithm.

6. (10pt) Consider the the following dataset with five dimensions A, B, C, D, E and measure SUM:

T1: (a1,b1,c1,d1,e1,70)
T2: (a1,b2,c1,d2,e1,10)
T3: (a1,b2,c1,d1,e2,20)
T4: (a2,b1,c1,d1,e2,40)
T5: (a2,b1,c1,d1,e3,30)

(a) Construct shell fragments (A,B) and (C,D,E).

(b) Use the shell fragments you constructed in (a) to answer the query (*,b1,*,d1,*,?).