\documentclass[12pt]{article}
\newcommand{\Bonus}[1]{\textbf{[#1 Points OPTIONAL Bonus Problem]}}
\newcommand{\Points}[1]{\textbf{[#1 Points]}}
\newcommand{\Name}[1]{\textbf{#1}}
\usepackage{amsfonts}
\usepackage{graphicx}
\usepackage{geometry}

\begin{document}
\begin{center}
	\bf
	Algorithms \\
	Computer Science 140 \& Mathematics 168 \\
	Spring 2009 \\
	\rm
	Homework 11b\\
	Due Tuesday, April 21
\end{center}

\begin{enumerate}

\item \Points{20} \Name{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 in detail.
 (Careful here -- achieving the depth and size requirements will require
 some care.)
 
   \item \Points{20} \Name{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?  

\item \Points{20 Points} \Name{More fun with Norelco Shavers!}
Give efficient EREW algorithms to compute the preorder, inorder, and
postorder numberings for an arbitrary binary tree with $n$ nodes.  For
each of the three parts of this problem (preorder, inorder, and
postorder), describe the values that must be placed in processors $A, B,
C$, explain where the solution is found, and briefly explain why your
algorithm works.

\item \Points{15 Points} \Name{Parallel Matrix Multiplication!}
In this problem we'll investigate the problem of finding the product
of two $n \times n$ matrices using a shared-memory parallel computer
with $n^{3}$ processors.
        \begin{enumerate}
                \item Show that this can be done in $O(\lg n)$ time
                if the machine has CREW.  Is this algorithm
work-efficient?  No!
                \item Now describe the fastest algorithm you can
                find for this problem that operates on a machine with
EREW.  
        \end{enumerate}
        
        \item \Points{15}  \Name{Sorting in Parallel!}
Give a parallel algorithm for sorting $n$ numbers in $O(\log n)$ time
using $n^2$ processors.  What model (EREW, CREW, or CRCW) does your
algorithm require?  (Use the ``weakest'' model that you can!  EREW is weaker than CREW is weaker than CRCW.)


\end{enumerate}
\end{document}