Activist Data Mining Homework (Dennis Shasha, Lipari summer school 2003)

1.  (Combinatorial Design)
If you have 6 inputs: prenitro, precarbon, prelight,
postnitro, light, and carbon.
All have two values (0 and 1) except postnitro which has four
(0, 1, 2, 3). Find the smallest two factor no pivot design, i.e. one such that
every combination of values from every pair of inputs is found
in one experiment.
Hint: a mere 8 experiments if possible.

2. (Adaptive Combinatorial Design)

1a. Given an 8 experiment solution to problem 1, which 8 additional experiments
would you add to obtain a pivot on prelight?

2b. Which five additional experiments would you add to the solution of problem 1
to get a half-pivot on prelight compared to a background of all 0s?

3. (Burst Detection)
Suppose you were interested in all window sizes up to 16 in a burst
detection setting. 
Suppose that the thresholds for the window sizes were:
size | thresh
1 | 4
2 | 4
3 | 4
4 | 4
5 | 4
6 | 4
7 | 5
8 | 5
9 | 5
10 | 6
11 | 6
12 | 6
13 | 6
14 | 6
15 | 7
16 | 7

With which thresholds would you design the shifted wavelet tree?


4. (AQuery)
4a. Given a schema
ticks(ID, date, endofdayprice)
find the maximum and minimum return of each stock
where return is the ratio of the price of day i compared with 
the price of day i-1.


4b. Assuming ticks were already sorted by ID, how would
you process the above query if you had complete control
of the optimization process?