\newcommand{\ig}[1]{}
\documentclass[12pt]{article}
\usepackage[dvips]{graphicx}
\usepackage{shortvrb}
\usepackage{epsfig}

\setlength{\textwidth}{6.5in}
\setlength{\textheight}{9.0in}
\setlength{\topmargin}{-.5in}
\setlength{\oddsidemargin}{-.0600in}
\setlength{\evensidemargin}{.0625in}

\MakeShortVerb{\|}

\begin{document}
\noindent
{\bf CSCE476/876 \hfill Spring 2009}

\begin{center}
{\bf\large Homework 6}
\end{center}

\begin{description}
\item[Assigned on:]  Wednesday, March 2, 2009.
\item[Due:] Friday, March 13, 2009. 
\item[Points:] 87 points + 10 Points bonus
\end{description}

\hrule\vspace{\baselineskip}



\tableofcontents
\vspace{\baselineskip}

\noindent {\bf Alert:} If you submit your homework handwritten, it must be {\em  absolutely neat} 
or it {\em will not} be corrected. If you type your homework (preferable), submit using webhandin.\\

\hrule\vspace{\baselineskip}

\vspace{\baselineskip}

\section{Dynamic Variable Ordering \hfill (8 points)} 

\begin{enumerate}

\item Explain the principle for dynamic variable ordering in Backtrack Search. 
\hfill (2 points)

\item Describe three heuristics that implement this principal. 
\hfill (6 points)

\end{enumerate}

\section{Constraint propagation \hfill (6 points)}
Consider the CSPs represented by the constraint networks below:\\

\begin{center}
\begin{tabular}{ccc}
\psfig{file=ac-1.eps,height=3cm} & &
\psfig{file=ac-2.eps,height=3cm}\\
{\bf CSP I} & & {\bf CSP II}
\end{tabular}
\end{center}

For each CSP,
\begin{enumerate}
\item
State whether or not the CSP is arc-consistent. 

\item
If it is, explain why.

\item
If it is not, explain which domain must be reduced to make the CSP
arc-consistent, and specify the constraint that can be used to reduce
the domain.

\end{enumerate}



\section{Simple scheduling problem (I) \hfill (10 points)}
\mbox{}\hfill{\em\small Courtesy of Rina Dechter}\\
 Consider the problem of scheduling five tasks: $T_1$, $T_2$, $T_3$,
 $T_4$, and $T_5$, each of which takes one hour to complete.  The
 tasks may start at 1:00, 2:00, 3:00.  Any number of tasks can be
 executed simultaneously provided the following restrictions are satisfied. 
 \begin{itemize}
 \item $T_1$ must start after $T_3$.
 \item $T_3$ must start before $T_4$ and after $T_5$.
 \item $T_2$ cannot execute at the same time as $T_1$.
 \item $T_2$ cannot execute at the same time as $T_4$.
 \item $T_4$ cannot start at 2:00.
 \end{itemize}
 \begin{enumerate}
 \item Formulate the problem as a CSP by stating: the variables, their domain, 
  and the applicable constraints.   \hfill{(4 points)}\\
  {\em Hints:} focus on the start time of a task.

 \item Draw the constraint graph. \hfill (2 points)

 \item Apply arc-consistency to each constraint in the CSP until no values 
  can be ruled out (i.e., the CSP becomes arc-consistent). \hfill (4 points)
 \end{enumerate}


\section{Simple scheduling problem (II) \hfill (15 points)} 
\mbox{}\hfill{\em\small Courtesy of Daphne Koller}\\
Mr.\ Smith is the owner of a factory that is about to produce solar
power flashlights.  He wishes to see if he can make a torch in
\underline{four hours}.  The construction of the torch consists
of four tasks: 
\begin{enumerate}
\item constructing the bulb: {\bf B\/} duration time is 2 hours
\item making the solar panel: {\bf P\/} duration time is 1 hour
\item doing the wiring:  {\bf W\/} duration time is 2 hours
\item assembling the housing: {\bf H\/}  duration time is 1 hour
\end{enumerate}
If Mr.\ Smith could perform all the tasks simultaneously, he would be
able to make a torch in 2 hours.  However, some of the tasks need to
be completed before others can proceed. The housing cannot start
before the bulb has been built; the wiring cannot be started before
the panel is made.  This information is summarized in the precedence
graph below:\\

\centerline{\psfig{file=preced.eps,height=2cm}}

Moreover, the only person qualified to construct the bulb and panel is
Constance, the electrical engineer.  Therefore, the bulb and panel
cannot be made simultaneously.
\begin{enumerate}
\item  Formulate this scheduling problem as a CSP. \hfill (10 points)\\
 {\em Hints:} Choose the variables to be time point at which a task is
 started.  State the initial domain of each variable as a set of
 \underline{discrete} values, one value per hour.  Specify the unary
 constraints that restrict the start time of a task given its duration
 to the duration of the entire job (i.e., four hours). For example, a
 task whose duration is 1 hour cannot start at `time point' 4.
 Specify the binary constraints that link the variables as an
 algebraic constraint.  The constraint expressions we are looking for
 are of the form $S_b + 2 < S_w$ (this example expression is only to
 give you an idea of what to write: it is {\em not\/} one of the
 constraints listed above.)

\item Draw the {\em complete\/} search tree generated by a backtrack-search 
  procedure {\em with forward-checking\/} using a static variable
  ordering of your choice.  Specify, as best you can, the domains
  filtered after each forward-checking step. \hfill (5 points)\\
\end{enumerate}


\section{$N$-Queen Problem as a CSP \hfill (14 points)}

Consider the 4-queens problem where each queen is associated with a
row and can be assigned to any column in the row. 

 \begin{enumerate}

 \item 
 Define this problem as a CSP.  Specify the variables and their
 domain, and each binary constraint by `extension.' \hfill{(1 point)}

 \item Define a binary constraint $C_{Q_i,Q_j}$ between two variables
 $Q_i$ and $Q_j$ by `intension.'\\\mbox{} \hfill{(4 points)}

 \item What is the size of this CSP (which is the size of the search
 tree it may yield)? \hfill{(1 point)}

 \item Draw the constraint graph. \hfill{(2 points)}

 \item Arc-consistency of a binary constraint $C_{Q_i,Q_j}$ between
 two variables $Q_i$ and $Q_j$ ensures that every value for the
 variable $Q_i$ has a support (at least one consistent value) in the
 domain of $Q_j$ and vice-versa.  Run manually arc-consistency on the
 4-Queens problem.  Can you remove any value?  At the end of the
 operation the CSP is said to be\\ arc-consistent. \hfill{(2 points)}


 \item Arc-consistency is also called 2-consistency because it
 considers all combinations of two variables at the same time.  Let's
 consider all combinations of 3 variables at the same time and let's
 check whether or not every value in the domain of a given variable
 has a support in the domain of the two other variables
 (simultaneously).  If it does not, the value can be removed. Can you
 remove any value?  This consistency property is called
 (1,2)-consistency.  \hfill{(4 points)}

 \end{enumerate}

\section{Consistency checking \hfill (10 points)} 
\mbox{}\hfill{\em Courtesy of Rina Dechter, UC-Irvine.}\\

Consider the simple coloring problem shown in Figure~\ref{fig:coloring-dechter}.
\begin{figure}[ht]
\centerline{\psfig{file=coloring-dechter.eps,height=4cm}}
\caption{\small {\it A simple CSP.}}
\label{fig:coloring-dechter}
\end{figure}
\begin{enumerate}
\item
Compute the equivalent network that is {\em strong} 3-consistent.  As
a reminder, {\em strong} 3-consistency requires that the network be
both arc-consistent (i.e., 2-consitent) and path-consistent (i.e.,
3-consitent).  Also note that path-consistency requires considering
{\em all\/} combinations of 3 variables, replacing all univeral
constraints with tighter ones.
\item
Find a solution to the CSP.
\end{enumerate}

\section{Latin square \hfill (Bonus 10 points)} 
\mbox{}\hfill{\em Adapted from of Daphne Koller, Stanford University.}\\

A Latin Square is a $N \times N$ array filled with colors, in which no
color appears more than once in any row or column.  Finding a solution
to a $4 \times 4$ Latin Square can be formulated as a CSP, with a
variable for each cell in the array, each having a domain of $\{r, g,
b, y\}$, and a set of constraints asserting that any pair of cells
appearing in the same row must have different colors, and that any
pair of cells appearing in the same column must have different colors.

\begin{figure}[ht]
\centerline{\psfig{file=figure.eps,height=4cm}}
\caption{\small {\it Current state of search.}}
\label{fig:latin-square}
\end{figure}

At this point in the search, seven of the cells have been instantiated
(displayed in \textbf{boldface} in Figure~\ref{fig:latin-square}), and
the initial domains of the remaining cells are shown.  (The next cell
to instantiate has the domain values in \textit{italics}, but this
information is irrelevant for this exercise.)

Re-execute (from scratch) the same 7 first assignments in the
specified order and, at \underline{\em each} assignment, draw the
Latin Square while filtering the domains of the relative future
variables.  Do this process for the two following look-ahead
strategies:
\begin{itemize}
\item the partial look-ahead strategy, forward checking (FC)
\item the full look-ahead strategy, maintaining arc consistency.
\end{itemize}
Indicate eliminated values by crossing them out or just erasing them.  

\section{Reduction of 3SAT into a CSP \hfill (24 points)}
\begin{enumerate}
\item Formulate 3SAT as a CSP. \hfill (15 points)\\
 {\em Indications:} Your formulation should be as general as possible
 and should represent each of the elements of the 3SAT and its
 question in the terminology of a CSP.  Consider $X$, the set of
 Boolean variables of a 3SAT instance.  What are the values that a
 variable can take?  Use this to define the variables of the CSP and
 their values.  A clause is a disjunction of literals.  How to
 represent a clause in the CSP formalism? A 3SAT sentence is a
 conjunction of clauses.  How is the sentence represented in the CSP
 formalism?  Finally, state how the question of 3SAT is reduced as a
 question to the CSP and prove that a solution to 3SAT exists if and
 only if a solution to the corresponding CSP exists.

\item 
What is the arity of the constraints of the resulting CSP? \hfill (2
points)

\item 
As a direct application of your reduction, transform the following
3SAT problem into a CSP.  Specify the variables, their domains, define
the constraint in extension, and draw the corresponding constraint
graph: \hfill (4 points) \[ (c_1 \vee c_2 \vee c_3) \wedge (c_2 \vee
c_3 \vee c_4) \wedge (\neg c_1 \vee c_5) \wedge (c_1 \vee c_4 \vee
c_5)\]

\item 
Knowing how a 3SAT clause (which is a disjunction of exactly~3
literals) is represented in the CSP, how do you propose to represent a
clause of SAT (which has an arbitrary number of literals in the
clause)? \hfill (3 points)
 
\end{enumerate}

\end{document}


