\documentstyle[fancyheadings,12pt]{article}

\pagestyle{fancy}

\addtolength{\headheight}{5pt}

\setlength{\headrulewidth}{1pt}


\setlength{\topmargin}{-0.6in}		%for dvi-imagen
\setlength{\oddsidemargin}{0.0in}   	%prev:-0.1 for dvi-imagen, -ve needed.
\setlength{\headheight}{.3in}
\setlength{\headsep}{.3in}
\setlength{\textheight}{8.8in}
\setlength{\textwidth}{6.5in} 
\setlength{\marginparwidth}{0in}
\setlength{\marginparsep}{0in}
\setlength{\marginparpush}{0in}

\lhead{Comp.Exam.}

\chead{Artificial Intelligence}

\rhead{Fall 1995}

\cfoot{}



\setcounter{secnumdepth}{3}	%to get numbers on subsubsection in text
				%default is 2.
\setcounter{tocdepth}{3}	%to get numbers on subsubsection in toc
				%default is 2.
\setlength{\unitlength}{1mm}
\renewcommand{\baselinestretch}{1.2}  % for kind of double spacing
%\setlength{\parskip}{.3in}
\setlength{\baselineskip}{0.5cm} %JUST CHANGED FROM 0.5
\setlength{\parindent}{0.3in} %JUST CHANGED FROM 0.2
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%55

\newcommand{\ria}{\rightarrow}
\newcommand{\Ria}{\Rightarrow}
\newcommand{\ul}{\underline}
\newcommand{\ol}{\overline}
\newcommand{\xsp}{\hspace{0.5em}}
\newcommand{\ysp}{\vspace{1.1ex}}
\newcommand{\appr}{\sqsubseteq}
\newcommand{\trr}{\triangleright}
\newcommand{\lf}{\tt} %%%%%%%%%%%%%%%%%%%%%%%%%%%% LISP FONT, MAYBE CHANGE LATER
\newcommand{\etal}{{\em et al.}} 
\newcommand{\etc}{{\em et cetera}} 
\newcommand{\eto}{ evaluates to }
\newcommand{\col}{ Common Lisp}

\def\heading#1{ \begin{center} {\bf \ul{#1}} \end{center}}

\newcommand{\asmtabs}
	{mmmmm\=mmmmmmmm\=mmmmmmmm\=mmmmmmmmmmmmmmm\=  \kill}
\newtheorem{thm}{Theorem}
\newtheorem{propn}[thm]{Proposition}
\newtheorem{defn}{Definition}
\newtheorem{examp}{Example}
\newtheorem{exercises}{Exercises}
\newtheorem{program}{Program}

\def\correct#1{\relax \ifmmode \expandafter #1 \else
$\expandafter #1$\fi}            % forces mathmode

\def\db#1{\correct{[\![ #1 ]\!]}}
\def\exer#1{\begin{exercises} \rm
{ #1 }
\end{exercises}}
\def\th#1{\begin{thm} \rm
{ #1 }
\end{thm}}
\def\exam#1{\begin{examp} \rm
{ #1 }
\end{examp}}
\def\lem#1{\begin{lemma} \rm
{ #1 }
\end{lemma}}
\def\prog#1{\begin{program} \rm
{ #1 }
\end{program}}
\def\verba#1{\begin{verbatim}
{ #1 }
\end{verbatim}}

\begin{document}
\setlength{\itemsep}{\parskip} 

{\bf Answer one of the first two questions, and all the remaining questions.}
\normalsize
%%%%%%%%%%%%%%%%%%%%%%
\begin{enumerate}
\item
Two astronomers make measurements $M_1$ and $M_2$
 of the number of stars $N$ in some small region of the sky,
 using their telescopes.
Each telescope can be out of focus (events $F_1$ and $F_2$),
 leading to errors in counting.
A final conclusion about $N'$, the number of stars, needs to be made
 based on the astronomers' measurements.

Construct a belief network or probabilistic
 inference network relating $M_1, M_2, N, N', F_1$ and $F_2$.
A priori, $P(N=1)= P(N=2) = 2*P(N=0) = 2*P(N=3)$.
The probability that a telescope is out of focus is 0.2.
If a telescope is out of focus, the resulting measurement may be 0,1,2 or 3
 with equal probability.
If a telescope is not out of focus, we can expect the resulting measurement
 to be accurate.

If $M_1 =1$ and $M_2 = 3$, what is the most likely number of stars ($N$)?
 Give clear reasons for your answer.
State all simplifying assumptions.

\item
Regions in a bitmap image are painted using the three patterns below:

\begin{tabular}{cccc}
010 &~~~~ 111 &~~~~ 101 \\
010 &~~~~ 111 &~~~~ 010 \\
010 &~~~~ 111 &~~~~ 101 
\end{tabular}

The first pattern consists of a single vertical line of 1's,
the second pattern is filled with 1's,
and third consists of alternating 1's and 0's.

The size of a region painted with a pattern may be arbitrarily large.
The following is an example of such an image containing each of these four patterns:\\
\begin{verbatim}
000000000111
000000000111
000000000111
101000000111
010000010000
101000010000
000000010000
000000010000
000000010000
\end{verbatim}

Design a neural network to identify the presence of such patterns in an image.


\item
\begin{quote} \sf
Animals can outrun any animals that they eat.
Carnivores eat other animals.
Outrunning is transitive.
Outrunning is antisymmetric.
Lions eat zebras.
Zebras outrun dogs.
Dogs are carnivores.
Dogs eat zebras. \rm
\end{quote}

Translate the above statements into first order logic,
 and use resolution to show that {\sf zebras eat lions}.
A formal proof is expected.

\item
Construct an augmented transition network 
for a library information retrieval system
in which users ask (in English)
for information about books on various subjects,
by various authors, and with various titles.
Each user query may contain a subject phrase, title,
 and/or author names.


\item
What is the Hough transform?
Where is it useful?
Describe an algorithm that uses the Hough transform.

\item
\begin{enumerate}
\item
How does search in A.I. differ from non-A.I. search techniques?
\item
How may  planning be viewed as a state-space search problem?
Identify the state space,
 initial and final goal states, move set, and 
 ``intelligent'' search methodology.

\end{enumerate}


\item
Describe the version space approach to concept learning.
What is the scope of applicability of this approach?

\end{enumerate}

\end{document}

