\documentclass[12pt]{article}
\textwidth = 6.5 in
\textheight = 9 in
\oddsidemargin = 0.0 in
\evensidemargin = 0.0 in
\topmargin = 0.2 in
\headheight = 0.0 in
\headsep = 0.0 in
\parskip = 0.2in
\parindent = 0.0in

\usepackage{amsmath,amssymb,enumerate}
%\def\rmdefault{bch} % Use Charter for main text font.

% =========================================================
\begin{document}

\begin{center}
{\LARGE
\textbf{CS 173: Discrete Structures, Fall 2009}
\\
\textbf{Homework 4}
\\[1ex]}

This homework contains 6 problems worth a total of 50 regular points
plus 5 bonus points.
It is due on Friday, September 25th at noon.   Turn in your
homework in our new homework dropboxes, in the Siebel basement
corridor (just east of the big window lounge area).   The
issue last week with the doors of the boxes has supposedly been
fixed. 

Starting with this homework, we will take one point off your
homework score if your name and
the day and time of your section are not clearly visible on
the top sheet of your homework.   If you want to include the problem
statements with your homework, please staple them to the back (not the front)
of your solutions.

\end{center}

\bigskip\hrule


\begin{enumerate}

%----------------------------------------------------------------------
\item \textbf{[16 points] Sets}


Define the following sets

\begin{eqnarray*}
A &=& \{\{\text{Elm}\}, \{\text{Pine}\}\} \\
B &=& \{\text{Elm}, \text{Oak}, \text{Maple} \} \\
C &=& \{\text{Elm}, \text{Vine}, \text{Birch}, \text{Maple} \} \\
D &=& \{\text{Tree}, \text{Disease}, \text{Street} \} \\
\end{eqnarray*}


For each of the following expressions, list the elements of the set or
calculate the value (as appropriate).  

\begin{enumerate}
\item $\{ (x,y) \in \mathbb{Z}^2 \mid x \ge 0 \text{ and }  y \ge 0  \text{ and } x+y = 3 \}$
\item $\{ x \in \mathbb{Z} \mid -20 \le x \le 20 \text{ and }  x \equiv 2 \pmod{7}\}$
\item $\{ X \in \mathbb{P}(C) \ :\  |X| \text{ is even}\}$
\item $A \cap B$
\item $A \cap \mathbb{P}(B \cap C)$
\item $(B \cap C) \times D$
\item $|\mathbb{P}(C \times D)|$
\item $|\mathbb{P}(B \cap D)|$
\end{enumerate}

\newpage
%----------------------------------------------------------------------
\item \textbf{[8 points] Euclidean algorithm}

\begin{enumerate}
\item Trace the execution of the Euclidean algorithm (lecture 10 or p 229 in
Rosen) on the inputs $391$ and $2380$.  That is, give a table
showing the values of the main variables ($x$, $y$, $r$) for
each pass through the loop.   Explicitly indicate what the output value is.

\item The pseudo code for the Euclidean algorithm presented in lecture 
handles only positive number inputs, despite the fact that the definition
of gcd also works if the inputs are negative or (in some cases) zero.
Modify the recursive version of
the pseudocode so that it can take any two integers as input.
Your pseudocode should output an answer that follows our mathematical definition of gcd.
The pseudocode can signal errors  (e.g. illegal inputs) using the error
command, e.g.

\begin{verbatim}
  if (excessive_pressure)
     error ``Please don't squeeze the tomatoes.''
\end{verbatim}


\end{enumerate}

%----------------------------------------------------------------------
\item \textbf{[8 points]} Pseudocode

I found the following uncommented pseudocode in Professor Snape's lab notebook.

\begin{verbatim}
    procedure foo(n,m:  natural numbers)
       if (m = 0) return 1
       else return n*foo(n,m-1)

    procedure bar(n: natural number)
       p := 0
       for i := 0 to n
           p := p + foo(n,3)
       return p
\end{verbatim}

\begin{enumerate}
\item Describe the output of foo, as a (simple) function of the inputs $n$ and $m$.
\item Describe the output of bar, as a function of the input $n$.   Give your answer
as a summation and also in closed form (equation that doesn't involve a summation).
\end{enumerate}


%----------------------------------------------------------------------
\item \textbf{[10 points]} Direct proof using congruence mod k

In the book, you will find several equivalent ways to define
congruence mod k.  For this problem, use the following definition:
for any integers $x$ and $y$ and any positive integer $m$, 
$x \equiv y \pmod{m}$ if there is an
integer $k$ such that $x = y + km$.

Using this definition prove that, for all integers $x$, $y$, $p$, $q$ and
$m$, with $m > 0$, if $x \equiv p \pmod{m}$
and $y \equiv q \pmod{m}$, then $x^2 + xy \equiv p^2 + pq \pmod{m}$.

\newpage
%----------------------------------------------------------------------
\item \textbf{[8 points] Proof using inequalities}

Prove the following claims using direct proof.

\begin{enumerate}
\item  For any integers $m$ and $k$, if $0 < \frac{1}{k} < m$ then
$\frac{m}{m^2 + 1} < k$.
\item For any integers $m$ and $k$, if $k \le 7$ and $0 < m-3 \le \frac{k}{7}$,
then $m^2 -9 \le k$.
\end{enumerate}


%----------------------------------------------------------------------
\item \textbf{[5 points] Bonus proof}

(This is a bonus problem.   That is, if you have time to do it, it will
add a few bonus points to your homework average.   But it's ok to skip
it if you have run out of time or interest.)

Show that if $x$, $y$ and $m$ are integers with $m \ge 2$, then
if $x \equiv y \pmod{m}$ then $gcd(x,m) = gcd(y,m)$.


%----------------------------------------------------------------------
\end{enumerate}
\end{document}

