\documentstyle{article}
\renewcommand{\baselinestretch}{1.10}
\topmargin 0pt
\textheight 22cm
\hfuzz=6pt
\pagestyle{empty}
\begin{document}

\begin{center} {\large \bf
Artificial Intelligence \\
 CIS Ph.D. Comprehensive Exam., Spring 1997, Closed-Book \\
Answer all questions in four hours} \end{center}

\begin{enumerate}
\item %1
How may machine learning be viewed as a task involving heuristic search?
Identify the states, operators/moves, heuristics, and goal states,
 preferably in the context of a specific machine learning algorithm.

\item %2
Consider the sentences
\begin{quote}
           The apprentice painted the hull of the ship with a toothbrush.
\\         The apprentice painted the ship with green paint after dinner.
\\         The apprentice painted the ship with the toothbrush with soft bristles.
\end{quote}
       Describe a simple context-free grammar which will yield
       a correct parse of these sentences.  
	What are all the parses   obtained  for  these  sentences?
  From among these, how can  a
       language recognition system find the semantically meaningful
 correct parses?

\item %3
\begin{enumerate}
\item
Precisely what is meant when it is claimed that
resolution provides a proof procedure that is complete?
\item
Why is resolution theorem-proving harder (or easier)
 when the equality predicate is included?
\item
What is the ``factor'' of a clause in first order logic?
\end{enumerate}


\item %5
Speakers of one language often import grammatical features 
 from the language they first learnt (mother tongue)
 into a language they learn later.
For instance, a speaker of Spanish may speak
 English words arranged
 in a manner that would be more reasonable in Spanish than in English.
Suggest the design of a language understanding system
 tailor-made to understand such sequences of English words,
 e.g., if the system is informed that the speaker's 
 original language is Spanish.

\item %6
Discuss the main problems to be addressed in
three-dimensional object recognition,
assuming that algorithms are available 
to perform two-dimensional exact shape matching
invariant to rotation, translation and scaling.
Structure your answer, separating issues related to representation,
 matching, inference, etc.

\item %4
Answer one of the following:
\begin{enumerate}
\item
Suggest an adaptive algorithm that adds hidden
 nodes to a feedforward network
 as needed for a specific problem.
\item
Suggest an adaptive algorithm that constructs and modifies
 a probabilistic inference system
 as new example data become available  for a problem.
\end{enumerate}

\end{enumerate}
\end{document}
