Due Date: 16 Nov 2004 6:30pm
Turnin procedure: Please email parag@cs.washington.edu before
class on Nov 16. Any of the Word,Postscript, PDF, HTML, or Plain text
formats should be fine.
Please use the subject "CSEP546: HW2 Submission", and in the text
part of the message include your name and student id.
You can also submit a hardcopy of your work at the beginning of
the class on Nov 16.
Notes: All homeworks are to be done
individually.
 What is the asymptotic worstcase time complexity of the sequential
covering (or "separate and conquer") algorithm for rule induction,
as a function of the number of examples n and the number of
attributes d? Assume that greedy search is used, and that error
rate is the evaluation measure used.

Planets around distant stars can sometimes be detected by the tiny
wobble they cause in the star's trajectory. Suppose that 2% of all
stars have planets orbiting them, 75% of stars with planets show a
wobble in their trajectory, and 10% of stars without planets show a
wobble due to other causes. If a star shows a wobble in its trajectory,
what is the probability that it has planets orbiting it?
 Consider a Bayesian network with two Boolean nodes A and B,
where A is the parent of B. Suppose you have a training set
composed of the following examples in the form (A,B), with "?"
indicating a missing value: (0,0), (0, ?), (0, 1), (0, ?), (1, 1),
(1, ?). Show the sequence of filledin values and parameter
estimates produced by the EM algorithm, assuming the parameters
are initialized ignoring missing values.
 Mitchell 4.5.
 Consider a population composed of three hypotheses, h1, h2 and h3,
whose fitnesses are respectively f1 = 10, f2 = 0 and f3 = 1.
Suppose the substitution rate is 33.3%, the mutation rate is 0%,
and rank selection is used. Compute each hypothesis' probability of
surviving unchanged into the next generation.
 Decision stumps are decision trees with only one node (the root).
Which ensemble method would you use to improve the accuracy of
decision stumps  bagging or boosting? Why?
