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

\ig{
\topmargin=0in
\textheight=8.5in
\textwidth=6.5in
\oddsidemargin=-.5in
\pagestyle{plain}
}

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

\begin{center}
{\bf\large Homework 7 UPDATED}
\end{center}

\begin{description}
\item[Assigned on:] Friday Oct 23, 2020.
\item[Due:] Wednesday Nov 4, 2020. 
\end{description}

\noindent This is a pen-and-paper homework, to be returned in class or with web handin.\\
\noindent The homework is worth 45 bonus points for ugrads and 20 points + 25 bonus points for grads .  \\

\hrule
%\vspace{\baselineskip}

\vspace{\baselineskip}

\tableofcontents

\section {{\bf Bonus} Researching Description Logic \hfill{\bf (Bonus 25 points)}}
Description Logic is a cornerstone of the Semantic Web technology.  In
this question, you are asked to research Description Logic {\em beyond
what is in your textbook}.  Write a two-page (typed) structured
summary about DL addressing whatever aspects you find meaningful and
interesting.  Below is a list of ideas {\em you may want to include},
they are mere suggestions.  Make sure you cite all your references.
\begin{enumerate}
\item 
What is the goal of DL? 

\item
To the extent possible, explain/state the syntax and semantics of DL.

\item 
How does DL relate to other types of Logic that we may or may not have
studies? 

\item
Explain some proof techniques used for DL and give their complexity.

\item 
Briefly describe the history/evolution of DL.
 
\item 
Discuss and compare various implementations of DL.

\item
Investigate the industrial impact of DL: list practical systems
implements some version of DL; are they public domain; have they
generated economic growth/benefit, etc.

\end{enumerate}

\section {Algorithms for Propositional Logic\\ (Mandatory for grad, bonus for ugrads) \hfill{\bf  (20 points)}}

Consider the following algorithms:
\begin{enumerate}
\item
{\sc TT-entails?}, AIMA Figure~7.10  page 248.

\item
{\sc PL-Resolution}, AIMA Figure~7.12  page 255.

\item
{\sc PL-FC-entails?}, AIMA Figure~7.15  page 258.

\item
{\sc DPLL-Satisfiable?}, AIMA Figure~7.17  page 261.


\item
{\sc WalkSAT}, AIMA Figure~7.18  page 263.
\end{enumerate}

For each of the above algorithms, carefully study the algorithm and
explain how it operates by 
\begin{itemize}
\item Clearly stating the input
\item Providing the representation on which it operates
\item Explaining when and why the algorithm stops
\item Stating what mechanism the algorithm implements (for example by relating it to
a known theorem.)
\end{itemize}
\hfill{(4 points for each algorithm)}



\vspace{0.2cm}
\end{document}

