Homework 1
CS522, Fall 2008

Due: Wednesday, October 8

Please upload your solutions to CSNS. Your file must be in text, MS Word, OpenDocument Text (ODT), or PDF format. Note that file uploading will be disabled automatically after 11:59PM of the due date, so please turn in your work on time.

[Readings]

[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,*,?).