\documentclass[11pt]{article}
\usepackage{fullpage}
\usepackage{6895}

\begin{document}

%\newcommand{\hint}{\textit{Hint:\ }}
%\newcommand{\defn}[1]{\emph{#1}}

\problems{Due: Thursday, November 27th}{12}{15}

\begin{problem}
  Denote the butterfly network running from major cycles to minor
  cycles by $W$, let its ``transpose'' $W\transpose$ be the butterfly
  network running from minor cycles to major cycles.  Thus, the
  Bene\v{s} network is essentially the network $WW\transpose$.  We've
  seen that $WW\transpose$ can route any permutation (offline) by
  node-disjoint paths.

  \begin{problempart}
    Show that the network $WWWW$, formed by $4$ butterfly networks
   connected in tandem, can route any permutation through
   node-disjoint paths.  (\hint Show that $WW$ can implement the
   \defn{bit-reverse} permutation.)
  \end{problempart}
  \begin{problempart}
    (\textit{Harder.}) Show that the network $WWW$ can route any
    permutation by node-disjoint paths.
  \end{problempart}
  \begin{problempart}
    (\textit{Open research problem.}) Can the network $WW$ route any
    permutation by node-disjoint paths?
    \end{problempart}
\end{problem}

\begin{problem}
\textbf{Shuffling}

\begin{problempart}
  Show that $r$ perfect out-shuffles return an $N=2^d$-card deck to
  its original order if and only if $2^r \equiv 1 \pmod{N-1}$.
\end{problempart}
\begin{problempart}
  Show that $8$ perfect out-shuffles are necessary and sufficient to
  restore a $52$-card deck to its original order.
\end{problempart}
\begin{problempart}
  How many perfect out-shuffles are necessary and sufficient to
  restore a $54$-card deck to its original order?
\end{problempart}
\end{problem}

\begin{problem}
  \textbf{De Bruijn}
  
  \begin{problempart}
    Construct a $32$-bit de Bruijn sequence.
  \end{problempart}
  \begin{problempart}
    Prove that the bisection width of an $N$-node de Bruijn network is
    $O(N/\lg N)$.  If you wish, you may use the fact that the
    bisection width of an $N$-node shuffle-exchange network is
    $O(N/\lg N)$.
  \end{problempart}
\end{problem}

\newpage

\begin{problem}
  \textbf{Kautz networks} \\
%%
  A \defn{$(d,k)$ Kautz network} is defined as follows:
  \begin{closeitemize}
    %%
  \item Each node is a word $\ang{x_1,x_2,\ldots,x_k}$ on the alphabet
  $\set{0,1,\ldots, d}$, where $x_i\neq x_{i+1}$ for
  $i=1,2,\ldots,k-1$.
    %%
  \item For each node $\ang{x_1,x_2,\ldots,x_k}$ and all $z\in
      \set{0,1,\ldots,d}-\set{x_k}$, an edge exists from
      $\ang{x_1,x_2,\ldots,x_k}$ to
      $\ang{x_2,\ldots,x_k,z}$.
      %%
  \end{closeitemize}
  \begin{problempart}
    Draw a $(2,3)$ Kautz network.
  \end{problempart}
  \begin{problempart}
    Prove that every node in a $(d,k)$ Kautz network has out-degree
    $d$ and in-degree~$d$.  Prove (careful: two cases) that the
    diameter is~$k$.
  \end{problempart}
  \begin{problempart}
    How many nodes $N$ does a $(d,k)$ Kautz network contain in terms
    of $d$ and~$k$?  (Give a precise answer, not a bound.)  Prove it.
  \end{problempart}
  \begin{problempart}
    Conjecture a good upper bound on the bisection width of a $(d,k)$
    Kautz network.  \textit{Optional:} Prove your bound.
  \end{problempart}
  \begin{problempart}
    Some architects have recently become enamored with the idea of
    interconnecting the processors of a parallel computer with a
    $(d,k)$ Kautz network, typically with $d\geq 4$.  List salient
    pros and cons.
  \end{problempart}
\end{problem}

\end{document}
