\documentclass[12pt]{amsart}
\usepackage{amsmath} \usepackage{amsthm} \usepackage{amstext}
\usepackage{amsfonts} \usepackage{graphicx} \usepackage{latexsym}
\usepackage{epsfig}
% \input epsf
\def\p{\partial} \def\O{\Omega} \def\c{\cal} \def\a{\alpha}
\def\r{\rho} \def\e{\epsilon} \def\g{\gamma} \def\d{\delta}
\def\D{\Delta} \def\t{\theta} \def\T{\Theta} \def\N{\nabla}
\def\L{\Lambda} \def\l{\lambda} \def\m{\mu} \def\f{\frac}
\def\dis{\displaystyle} \def\s{\sigma}
\newcommand{\lx}{\left} \newcommand{\rx}{\right}
\setlength{\parindent}{0in} \setlength{\parskip}{\baselineskip}
\setlength{\textheight}{9.0in} \setlength{\textwidth}{6.5in}
\setlength{\topmargin}{0.0in} \setlength{\evensidemargin}{0in}
\setlength{\oddsidemargin}{0in}

\begin{document} %(
\baselineskip 24pt

\title{Problem Set 09}
% YOUR NAME GOES HERE under Author
\author{Your Name}
\maketitle

\begin{enumerate} %(

\item Using Huffman's algorithm, how many bits would it take to encode
the string:
\begin{verbatim}
AN_ANT_NEST_TENANT_SET_TEN_ANTENNA_TENTS
\end{verbatim}
(Not including the number of bits to encode the encoding tree itself.)
Note that ``\_'' is also a character.

% Answer below this line.
\item Write a logical expression that's equivalent to the following
but uses only $\bar{\wedge}$s (NAND).
\begin{enumerate} %(
\item $\sim A$
% Answer below this line.
{\bf Answer:} $\sim A = A \bar{\wedge} A$

\item $A \wedge B$

% Answer below this line.

\item $A \vee B$

% Answer below this line.

\end{enumerate} %)

\item A universal Boolean operator is one (such as NAND) that can be used to
define any other Boolean operator.  Prove or disprove the following
(you can assume that NAND is universal, since we just showed that you
can use it to make AND, OR, and NOT):
\begin{enumerate} %( 
\item NOR ($\bar{\vee}$) is universal (hint, the computer that was
used to guide the Apollo space mission was built using only NOR
gates).

% Answer below this line.

\item (BONUS) XOR is universal.

% Answer below this line.

\end{enumerate} %)


\item (This is exercise 11.14) A palindrome is a string that reads the
same backward as it does forward.  Find a context-free grammar that
generates the set of all palindromes over the alphabet $\lx\{A,
D\rx\}$.

% Answer below this line.

\item On a scale from 0 to 1, what do you think your
attendance/participation grade ought to be?  Please briefly justify
your answer.

% Answer below this line.

\end{enumerate} %)
\end{document} %)