\documentclass[12pt]{article}

\newtheorem{claim}{Claim}

\usepackage{fullpage}
\begin{document}
\begin{center}
\textbf{CS 181b} \\ Advanced Topics in Algorithms \\ Spring 2002 \\
Problem Set 5a \\ Due Thursday, February 21 in class
\end{center}

\begin{enumerate}

  \item \textbf{[15 Points]  Tally Circuits!} A tally circuit has $n$
binary inputs and 
  $\lceil \log_2 (n+1) \rceil$ outputs.  Interpreted as a binary number,
  the outputs give the number of 1's in the input.  For example,
  if the input is $1101111$ then the output is $110$, indicating that
there are six 1's in the input.  Describe a tally circuit with
depth $O(\log n)$ and size $O(n)$.  Show your analyses.

  \item \textbf{[15 Points]  Majority Circuits!}
 A majority circuit with
$n$ boolean inputs $x_{1}, x_{2}, \ldots, x_{n}$ outputs a 1
if $x_{1} + x_{2} + \ldots + x_{n} > n/2$ and outputs 0 otherwise.
Describe a circuit for an $n$-input majority function that has depth
$O(\lg n)$.  Describe and analyze your circuit carefully.  What is the
size of your circuit?

\end{enumerate}
\end{document}