\input{/home/sc/yip/cs201-macro.tex}
\input{psfig}

\setlength{\textwidth}{6.25 in}
%\setlength{\textheight}{9.0 in}
\setlength{\topmargin}{-.6 in}


\begin{document} 
\pagestyle{empty}

\psetheader{Fall Semester, 1996}{Practice Problems -- Oct 17, 1996}

\leftbold{Problem: Rule-based System}

As a last-minute attempt to boost his campaign, candidate Bob Dole
hired you to build an expert system to manage his campaign.  
After a little thought, you decided that a forward-chaining reaction
system would be most appropriate to the task.  In this problem you are
to explore the issues involved in choosing a conflict resolution
strategy to handle multiple triggered rules.

For each of the reaction systems below, state which of the following
strategies is most promising:
\begin{itemize}
\item Rule ordering
\item Data ordering
\item Size ordering
\item Recency ordering
\end{itemize}

Explain your choice.

A. A system to determine actions to many situations ranging from bomb
threat to making empty promises to voters.

\onebox{6in}{.6in}

B. A system to dodge reporter questions by providing generic excuses.

\onebox{6in}{.6in}

C. A system to make the candidate appear sympathetic with the concerns
of voters who confronted him.

\onebox{6in}{.6in}

D. A system to carry a focussed conversation on a single topic at a
time.

\onebox{6in}{.6in}

\clearpage

\leftbold{Problem: CSP}

One can view the various constraint satisfaction algorithms of PS 5 as
different ways of filtering variable domains.  Consider a CSP with $n$
variables $v_1, v_2, \ldots, v_n$.  Call the variable currently being
instantiated by the {\tt backtrack} procedure the {\it present
variable}. Call the variables that have already been instantiated,
$v_1, v_2, \ldots, v_{k-1}$ the {\it past variables}, and the
variables that have not been instantiated $v_{k+1}, \ldots, v_n$ the
{\it future variables}.  It is also useful to group together the
present and future variables as the {\it non-past variables}.

Consider the following five algorithms:

1. backtrack \\
2. forward-check\\
3. AC3\\
4. backtrack that calls forward-check\\
5. backtrack that calls AC3\\

%BT  filter {k} against {1 .. k-1}
%FC  filter {k ... n} against {k-1}
%AC3 filter {k ... n} against {k-1 ... n}
%    or FC + filter {k ... n} against {k ... n}

For each of the following filtering schemes, state which algorithm 
best fits the description.  If none of the algorithm fits, write NONE
in the answer box.

A. The current variable domain is filtered against all past
variables. 

%BT

\onebox{.4in}{.2in} 

B. The current variable domain is filtered against all past
and future variables.

%NONE

\onebox{.4in}{.2in} 


C. All future variable domains are filtered against the current
variable.

%BT + FC

\onebox{.4in}{.2in} 

D. All non-past variable domains are filtered against all past
variables.

%NONE

\onebox{.4in}{.2in} 


E. All non-past variable domains are filtered against all non-past
variables.

%BT + AC3  or AC3


\onebox{.4in}{.2in} 



\end{document}