Question $4$: Decision treesQuestion $5$: Constraint satisfaction problems

A local wildlife farm wants to donate animals to the local Zoo. These include lions,

zebras, elephants and rhinos. The Zoo has enclosures where they can place

these animals. They want to avoid placing the same species of animal in adjacent

cages. The lions are a problem as well, because the zoo cannot place the lions

adjacent to the zebras.

The map layout of the enclosures are as in the diagram below. For example, $E$ is

adjacent to $B,C,D,F,G$ and $H,$ but not adjacent to A and I.

$($a$)$ Consider the task of deciding which animals need to be placed into which

enclosure as a constraint satisfaction problem $($CSP$).$ Define the variables,

the domains of the variables, as well as the constraints of the problem, using

the variables you have defined. Use the correct mathematical notation and

operators.

$($b$)$ Draw the constraint graph for this CSP$.$

$($c$)$ Using any form of backtracking search, solve this CSP problem. Start with

assigning Lion to a node $($think about which node is a good place to start the

search$).$ Assign the rest of the animals in the sequence Elephant, Giraffe,

Rhino $($this is alphabetical$).$

$($d$)$ BONUS MARKS $-$ What would happen to this CSP problem if you defined

the alldiff$()$ constraint for the placement of the animals?

$(2($bonus$))$Question $5$: Constraint satisfaction problems

A local wildlife farm wants to donate animals to the local Zoo. These include lions,

zebras, elephants and rhinos. The Zoo has enclosures where they can place

these animals. They want to avoid placing the same species of animal in adjacent

cages. The lions are a problem as well, because the zoo cannot place the lions

adjacent to the zebras.

The map layout of the enclosures are as in the diagram below. For example, $E$ is

adjacent to $B,C,D,F,G$ and $H,$ but not adjacent to A and I.

$($a$)$ Consider the task of deciding which animals need to be placed into which

enclosure as a constraint satisfaction problem $($CSP$).$ Define the variables,

the domains of the variables, as well as the constraints of the problem, using

the variables you have defined. Use the correct mathematical notation and

operators.

$($b$)$ Draw the constraint graph for this CSP$.$

$($c$)$ Using any form of backtracking search, solve this CSP problem. Start with

assigning Lion to a node $($think about which node is a good place to start the

search$).$ Assign the rest of the animals in the sequence Elephant, Giraffe,

Rhino $($this is alphabetical$).$

$($d$)$ BONUS MARKS $-$ What would happen to this CSP problem if you defined

the alldiff$()$ constraint for the placement of the animals?

$(2($bonus$))$

The data in Table $1$ shows attributes that might influence a family's decision on

where to go for their vacation. The target variable is whether the family chose the

destination $($Yes or No$).$

Table $1$: Vacation destination attributes and family's choices.

$($a$)$ Explain what Entropy and Information Gain represent in the context of the

ID$3$ algorithm to construct decision trees. Explain what these values mean in

practice.

$($b$)$ Calculate the base Entropy of this data set. Show every step of your calcula$-$

tion, including how you determine the ratios.

$($c$)$ Calculate the Information Gain for each of the attributes. Show all the ratios,

steps and calculations.

$($d$)$ Based on your calculations, which attribute$($s$)$ will be used as the root node

of the decision tree? Explain why.

$($e$)$ Discuss how ID$3$ proceeds once it has determined the root node. Use your

root node as an example to start your discussion. Indicate how the dataset

gets modified in the next steps of the algorithm.