1) (Exercise 8.4 in Chapter 8 of the textbook) It is important to calculate the worst-case computational complexity of the decision tree algorithm. Given data set D, the number of attributes n, and the number of training tuples |D|, show that the computational cost of growing a tree is at most n |D| log(|D|).

2) (Exercise 8.7 in Chapter 8 of the textbook) The following table consists of training data from an employee database. The data have been generalized. For example, 31 . . . 35 for age represents the age range of 31 to 35. For a given row entry, count represents the number of data tuples having the values for department, status, age, and salary given in that row

Let status be the class label attribute.

a) How would you modify the basic decision tree algorithm to take into consideration the count of each generalized data tuple (i.e. of each row entry)?

b) Use your algorithm to construct a decision tree from the given data.

c) Given a data tuple having the values systems, 26. . . 30, and 4650K for the attributes department, age, and salary, respectively, what would a nave Bayesian classification of the status for the tuple be?

.

department status age salary 31...35 46K... 50K 30 count senior junior 26...30 26K..30K 40 junior 31...35 31K...35K 40 systems junior 21...25 46K...50K 20 systems systems junior 26..30 46K...50K 3 systems marketing seior 36...40 46K...50K 10 marketing junior 31...35 41K. 45K4 secretary senior 46...50 36K...40K4 secretary junior 26...30 26K...30K 6 senior 31...35 66K... 70K 5 senior 41...45 66K... 70K 3