DSCI 599 Homework 3
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.
