1. [12 pts]: Consider a scheduling problem, where there are five classes to be scheduled in three time slots. Suppose we represent the classes by the variables A, B, C, D and E, where the domain of each variable is {1,2,3} and the constraints are A>D, CA, BA, BE.

Part A: [5 pts] Draw the constraint graph for the above problem.

Part B: [5 pts] Using arc consistency, prune the domains as much as possible, and list the pruned domains below. (You can use your constraint graph above for pruning).

Class Pruned domain

A:

B:

C:

D:

E:

Part C: [2 pts] Suppose you do not achieve a unique solution, and were then to use variable elimination to eliminate variable E. Which constraints would be removed? A constraint would then be created on which variables?