\documentclass[12pt]{article}

\begin{document}

\centerline{Homework 3, MORALLY Due Feb 18}
\newcommand{\implies}{\Rightarrow}

\centerline{\bf WARNING: THIS HW IS TWO PAGES LONG!!!!!!!!!!!!!!!!!}

\newif{\ifshowsoln}
\showsolntrue % comment out to NOT show solution inside \ifshowsoln and \fi blocks.

\begin{enumerate}

\item
(40 points)
\begin{enumerate}
\item
(20 points)
We are working in binary so all numbers are 0's and 1's.
When we input 2 bits to a circuit we think of it as a NUMBER in base 2.

00=0

01=1

10=2

11=3

The output will be 3 bits, intepreted as a number in base 2.

000=0, $\ldots$, 111=7

Write a truth table with 2 inputs 
and 3 outputs for the following function:

$f(xy) = (xy)^2 \pmod 8$.

So for example

$f(11)$ is computed by 11=3, $3^2=9$, $9 \pmod 8 = 1$, so the output is 001.

\item
(20 points)
Write a circuit for $f$ using AND, OR, and NOT using the method shown in class
(do not simplify- that would make it harder for the TA's to grade!)

\end{enumerate}

\centerline{\bf GO TO NEXT PAGE!!!!!!!!!!!!!!!!!!!!}

\newpage

\item
(60 points)
In this problem the inputs are considered bits that you add.
So if the input is $(1,0,1)$ it is NOT 101 in base 2 which is 5.
Its just three bits, separate.

The {\it Depth} of a circuit is the max number of gates from input to output.

The {\it Size} of a circuit is the total number of gates.

ALSO we allow as inputs variable AND their negations.

In this problem we will look at different circuits for:

$$f_n(x_1,\ldots,x_n)= x_1 + \cdots + x_n \pmod 2.$$

We allow AND, OR and NOT gates usual; however, the AND and OR gates can take
MANY inputs (as many as you want). 

You can assume that $n$ is a power of two if it makes the math easier.

\begin{enumerate}
\item
(30 points)
Show that, for all $n$, there is a circuit
for $f_n$ with depth 2. What is the circuit's size?
\item
(30 points)
Show that, for all $n$, there is a circuit for $f_n$ with size $O(n)$
(less than some constant times $n$). What is the constant? What is
the depth of the circuit?
(HINT: First get a circuit for $f_2(x_1,x_2)$. View this as a gate you can use.
Use that 
$$f_n(x_1,\ldots,x_n)=f_{n/2}(f_2(x_1,x_2),f(x_3,x_4),\ldots,f(x_{n-1},x_n)).$$
\item
(0 points but think about)
In part 1 you got a CONSTANT DEPTH but LARGE SIZE circuit.
In part 2 you got a SMALL SIZE but LOG DEPTH circuit.
Is there a circuit for $f_n$ which is constant depth and small size?
\end{enumerate}

\end{enumerate}
\end{document}