1.  a)  What is bias in learning? What biases are used by the decision tree learning algorithm? 
 b)   A machine learning problem involves four attributes plus a class. The attributes have 3, 2, 2, and 2 possible values each. The class has 3 possible values.
i.  How many possible different examples are there? 
ii.  How many possible different conjunctive rules are there? 

 c)  Describe the difference between the kind of decision boundaries formed by decision tree algorithms and nearestneighbor instancebased learning algorithms. 
 d)  Briefly describe a commercial application of machine learning. 
 e)  Why is a decision tree that fits the data really well not necessarily better than another that doesn't fit it so well?

2.   State, in the form of pseudocode and in as much detail as you can, the basic algorithm for these two machine learning schemes: 
 a)  RIPPER 
 b)  kNN 
   In each case be sure to include
i.  The basic idea of the algorithm; 
ii.  Pseudocode for the algorithm; 
iii.  A discussion of the effect of errors, or noise, in the example; 
iv.  A summary of the advantages and disadvantages of the method compared with other methods of machine learning.


3.  a)  Does pruning a decision tree such as that produced by the basic (ID3) algorithm increase or decrease performance on the training set? on the test set? sometimes or always? 
 b)  With the version space method, do either of (i) the computation time taken, (ii) the final concept learned, depend on the sequence in which examples are presented? 
 c)  What is the difference between a "supervised" and an "unsupervised" learning scheme? What is the difference between an "incremental" and a "nonincremental" scheme? 
 d)  Define human learning in terms of (a) knowledge acquisition, and (b) performance improvement. What goes wrong when you apply these definitions to machines? 
 e)  Give an example of a concept description language that produces an infinite set of concepts.

4.   Consider a classification problem with four binary attributes, A, B, C, and D, in which the classification is positive if either A=B=0 or C=D=0 and negative otherwise. 
 a)  Draw a decision tree for this problem. 
 b)  Describe a simple method for converting a decision tree to rules and illustrate it using this example. 
 c)  What is the drawback of this simple method for converting a decision tree to rules, and how can it be overcome? 
 c)  If it is overcome using the method you suggest, what are the rules that result?
