ITCS6150_8150 - HW3 - Solved

 Game playing, CSP, and Bayesian Networks, Learning from Observations 

 

1.       [3 + 4 = 7 points]  

a.     State the purpose of alpha-beta pruning in your words and compare it with minimax algorithm.  

b.    Trace alpha-beta pruning algorithm in the following game-tree. Determine and clearly write the final alpha and beta values for each node.

  

 

2.       [15 points] You are in charge of scheduling for computer science classes that meet Mondays, Wednesdays and Fridays. There are 5 classes that meet on these days and 3 professors who will be teaching these classes. You are constrained by the fact that each professor can only teach one class at a time.  

The classes are:

§  Class 1 – Advanced Programming: meets from 8:00-9:00am

§  Class 2 – Intelligent Systems: meets from 8:30-9:30am  

§  Class 3 - Natural Language Processing: meets from 9:00-10:00am  

§  Class 4 – Cloud Computing: meets from 9:00-10:00am

§  Class 5 - Machine Learning: meets from 9:30-10:30am  The professors are:

§  Professor A, who is available to teach Classes 3 and 4.

§  Professor B, who is available to teach Classes 2, 3, 4, and 5. §    Professor C, who is available to teach Classes 1, 2, 3, 4, 5.  

a.     [3 points] Formulate this problem as a CSP problem in which there is one variable per class, stating the domains, and constraints. Constraints should be specified formally and precisely (e.g. 𝐶 ), but may be implicit rather than explicit.  

b.    [2 points] Draw the constraint graph associated with your CSP.

c.     [5 points] Give one solution to this CSP using Backtracking algorithm. Select and use variables and values alphabetically. Show your work in detail using tree and table (see template below). Mark and count the number of backtrackings.

List all values eliminated from neighboring variables 
Backtrack 
1 
 
 
 
2 
 
 
 
d.    [5 points] Give one solution to this CSP using Backtracking algorithm with Forward Checking. Select and use variables and values alphabetically. Show your work in detail using tree and table (see template below). Mark and count the number of backtrackings.

 

Step# 
Var assigned 
List all values eliminated from neighboring variables 
Backtrack 
1 
 
 
 
2 
 
 
 
 

3.       [5 points] Use the AC-3 algorithm to show that arc consistency can detect the inconsistency of the partial assignment {WA = green, V = red } for the problem shown in the following figure.

  

 

4.       [3 + 4 = 7 points]  

a.     What are the ways to identify a good attribute test while constructing a decision tree? Explain them in your words.

b.    For the following dataset, build an identification tree based on entropy. Consider Outlook, Temperature, Humidity, and Wind as attributes and the output is binary Yes or No decision on Play Tennis query.

   

 

5.       [6  points] Explain how to construct Bayesian Networks and give an example.