\documentclass{article}
\usepackage{graphicx}
%\usepackage{url,supertech}

\pagestyle{empty}

\newcommand{\comment}[1]{}
\newif\ifsolutionset
%\solutionsettrue
\solutionsetfalse


\newcommand{\solution}[1]{}
\ifsolutionset
\renewcommand{\solution}[1]{
  \bigskip
  {\bf Solution:} #1
  \bigskip
}
\fi

\input{6896-stuff}

\newcommand{\theproblemsetnum}{1}

\newcommand{\tup}[1]{\langle #1 \rangle}

\begin{document}

\handout{ps1}{Problem Set 1}

\textbf{Due:} In class on Wednesday, February 11.

Starred problems are optional.

\begin{problems}

\problem{}
  
Design an efficient algorithm to sort $N$ numbers in
$\Theta(N)$ time using $\Theta(\lg N)$ processors, where each
processor can hold an unlimited amount of data.  You may use any
fixed-connection network you wish.  (\hint Refresh your memory on
serial sorting algorithms.)

\hfill \\
\hrule
\hfill \\ 

\problem{} 
Argue persuasively that any $P$-processor fixed-connection
network with at most $d$ neighbors per processor has
diameter~$\Omega(\log_d P)$.

\hfill \\
\hrule
\hfill \\ 

\begin{center}
\includegraphics[angle=-90,scale=0.5]{fsquad.epsi}\\[12pt] \textbf{Figure 1}
\end{center}

\problem{*}  A firing squad has been formed as a one-dimensional array
of $n$ soldiers, as shown in Figure~1.  Each soldier is a finite
automaton whose next state is dependent only on its current state and
the current states of its two neighbors.  There is no global
communication, but the state transitions of the soldiers are
synchronized by a global clock.  The goal is for all the soldiers to
shoot their guns at the same time.

All the soldiers begin in the same \const{quiescent} state, and all
soldiers are identical, except for first and last soldiers.  The last
soldier knows he or she is the last soldier.  The first soldier is the
general, who, at the start of the computation, enters the
\const{fire-when-ready} state.  The goal is for all soldiers to enter
the \const{shoot} state \emph{on exactly the same clock tick}.

Give a design for the soldier automaton so that all soldiers fire at
the same time.  Your algorithm should run in $\Theta(N)$ time.

\end{problems}

\end{document}


