\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{Ph.D. Comp.Exam.}

\chead{Artificial Intelligence}

\rhead{Spring 1996}

\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} 

\normalsize
%%%%%%%%%%%%%%%%%%%%%%
\begin{enumerate}
\item
Discuss whether:
\begin{enumerate}
\item
 All propositions expressed by a semantic network
 can be expressed using relational databases.

ANSWER: Yes, every network arc can be expressed as a 3-tuple.

\item
 All propositions expressed by a semantic network
 can be expressed using relational databases.

ANSWER: Yes, every tuple in a relation can be assigned a unique label,
 and each tuple can then be
 expressed as a combination of 3-tuples, each containing that label.
Each 3-tuple can be expressed as an arc in a semantic network.
\end{enumerate}


\item
\begin{enumerate}
\item
Describe the {\bf admissibility} criterion
 in the context of the A* algorithm.
What are the properties of instances of the A* algorithm
 that  satisfy this criterion?
\item
Describe the  {\bf consistency} criterion
 in the context of the A* algorithm.
What are the properties of instances of the A* algorithm
 that  satisfy this criterion?
\end{enumerate}

ANSWER: Described in the text.

\item
What is the relation between theorem-proving (automated reasoning)
 and logic programming?

ANSWER: Logic programming using languages such as Prolog
 relies on resolution, and 
 the execution of a pure Prolog program can be viewed
 as an attempt to conduct refutational theorem-proving,
 using a linear strategy.

\item
Suggest an algorithm that can perform automated reasoning
 with statements that include  
 special predicates {\bf After(X,Y), Before(X,Y), Never(X), Henceforth(X)},
 with the obvious intended time-related meaning
 (e.g., {\bf Henceforth(X)} means X is true
	 at every instant from the present instant
         onwards, including the present instant).

ANSWER: These predicates can be expressed by quantifying over time,
 treating the present time as a special constant,
 and exressing transitivity of relations such as `After.'
Refutation usign resolution can then be performed.

\item
Describe the ID3 algorithm.

ANSWER: Described in the text.

\item
What are the main components of a computer program
 developed to learn a grammar for a 
 natural language such as English?

ANSWER: (NOTE:answers other than the following are also possible.)  \\
Non-terminals for the grammar must be inferred
 based on frequencies with which pairs of words occur,
 and based on relative positions in sentences.
For instance, frequent occurrences of  phrases such as 
 ``the boy,'' ``the girl,'' etc., 
 could be used to infer a non-terminal (BG) representing
 both ``boy'' and ``girl'' with 
 grammar rules of the form ``BG $\rightarrow $ boy'';
 another non-terminal (TBG) could be inferred representing phrases 
 of the form ``the BG'' with grammar rules such as ``TBG $\rightarrow$ the BG''.
Everytime a sentence is encountered, the ``strength''
 associated with some such rules can be increased by the learning system.
The final grammar may contain rules with  high strength.

\item
Are there any obvious disadvantages of moving-average filtering?

ANSWER: Described in the text. 

\item
What is the phagocyte heuristic?
 
ANSWER: Described in the text.  

\item Answer one of the following parts:
\begin{enumerate}
\item
What are the assumptions and weaknesses of
 Prospector's probabilistic inference network?

ANSWER: Independence assumptions may not hold in real life.
Treatment of unknown and low probabilities is not clearly
 demarcated.

\item
For what classes of problems would the use of 
 a neural network be more appropriate than
 a rule-based expert system? 

ANSWER: Neural networks are more appropriate when
 raw data and specific examples are available,
 instead of experts that can readily supply
 knowledge that can be encoded as rules.

\end{enumerate}
\end{enumerate}

\end{document}

