## Description

1. [10 points] Show that arc-consistency does not necessarily solve a CSP instance but just

reduces the search space. When is a CSP instance 4-consistent? What is the Ame

complexity of checking 4-consistency in a CSP instance? Are the constraints added by

enforcing 4-consistency already implied by the given constraints in the CSP instance?

Why don’t we generally enforce 4-consistency or higher?

2. [10 points] Is CSP backtracking search complete or incomplete? What method is used to

implement Look-Back techniques in CSP backtracking search? Pick a problem of interest

in Data Science which can be solved efficiently using CSP Look-Ahead techniques.

Describe the problem and the applicaAon of the CSP Look-Ahead techniques on it.

3. [10 points] In the Dynamic Variable/Value Ordering technique, which variable do we

instanAate next and in what order should the values of that variable be tried? Give an

example of a problem that can be solved efficiently using Dynamic Variable/Value

Ordering techniques. Draw the normal (staAc) search tree and the dynamically ordered

search tree for that example and explain why the dynamically ordered search tree is

beXer.

4. [10 points] What are Simple Temporal Problems (STPs)? How can they be solved

efficiently? What are the earliest and latest schedules for a consistent STP instance?

What are DisjuncAve Temporal Problems (DTPs)? Where do they arise? What is the

complexity of solving them? How can they be solved efficiently in pracAce?

5. [10 points] What are Bayesian Networks (BNs)? What are the various kinds of queries

that can be formulated on a BN? Compare CSPs and BNs with respect to their

representaAonal power, the queries they support, the techniques used for answering

the queries, and the efficiency of doing so.