I. Imagine that you are responsible for the arrangement of the classroom for the exam schedule of the department on a given day. You have 6 courses, namely CENG111, CENG213, CENG223, CENG315, CENG331 and CENG351. The availability of the classrooms are given as below:
You should arrange the schedule so that no two exams of the same grade (whose course codes start with the same digit) are held in the same time. You may assume that all of our students perfectly prepared for the exams, so no one will complain about having consequent exams in the same day.
a. (20 points) Formulate this problem as a Constraint Satisfaction Problem by defining variables, domains and constraints. You should write the constraints for each possible assignment for the pairs of courses (You may define a set of assignable pairs then use it for the pairs, there is no need for repetition.).
b. (10 points) Give an example for termination of search during the application of backtracking by forward checking.
c. (10 points) Give an example for termination of search during the application of backtracking by arc consistency.
For item b and c, you can draw a table or formally define the behavior.
1
II.
(30 points) Apply the alpha-beta cutoff for the game tree given below where the orange triangles and green circles represent the max’s and min’s turn respectively. Blue squares are final states with their values.
List v, α, β values of all explored nodes and indicate where α/β-prunning occurs in the tree (if exists).
Prove that K ⇒ L for the following knowledge base
III.
I∧J⇒K G∧H⇒I H∧D⇒J E∧H⇒G E∧F⇒H G∧A⇒E A∧B⇒E B∧C⇒F A
B C D
2
• •
•
by using;
a. (15 points) Forward chaining,
b. (15 points) Backward chaining.
Show your work step by step. In case of a tie-break during the selection of next premise, choose
the first premise in the alphabetical order.
