\documentclass{article}
\usepackage{6896}
\usepackage{epsfig}

\begin{document}

\header{Jeremy Fineman}{9}

\footnotenonumber{Collaborated with Team Supertech.}

\begin{problems}
  \problem { \
    \begin{lemma}
      Any VLSI layout can be transformed into a (nearly) square layout
      with an increase of no more than a constant factor to area.
    \end{lemma}
    \begin{proof}
      Suppose that the bounding box of the original circuit is $m
      \times n$, where $m \leq n$.  Then we can fold over the original
      circuit (like an accordion) at intervals of $\sqrt{mn}$ on the
      long edge.  Thus, we fold over the circuit into
      $\ceil{n/\sqrt{mn}}$ sections to fit inside a bounding box that
      is $\sqrt{mn} \times \paren{m \cdot \ceil{n/\sqrt{mn}}}$, which
      is no larger than a box that is $\sqrt{mn} \times
      \paren{\sqrt{mn} + m}$.  
      
      Next, we must take into account the extra wires added due to the
      folds.  Since the width of the circuit at the folds is only $m$,
      there can only be $m$ wires crossing the fold.  Thus, we can fit
      the circuit with the new wires inside a box that is
      $\paren{\sqrt{mn} + 2m} \times \paren{\sqrt{mn} +
        m}$\footnote{in the most unbalanced case, where
        $\ceil{n/\sqrt{mn}} = n/\sqrt{mn}$, we have a rectangle that
        is $\paren{\sqrt{mn} + 2m} \times \sqrt{mn}$.  This is
        ``nearly square'' because $m < n$, and hence $m <\sqrt{mn}$,
        so the longer dimension is at most $3$ times the shorter
        one.}, which fits inside a square box with dimensions
      $\paren{\sqrt{mn} + 2m} \times \paren{\sqrt{mn} + 2m}$.  The
      total area is thus less than $\paren{\sqrt{mn} + 2m}^2 = mn +
      4m\sqrt{mn} + 4m^2$.  Since $m<n$, we have that this area is
      less than $mn + 4mn + 4mn = 9mn$, and the total area of the
      circuit did not increase by more than the constant factor
      of~$9$.
    \end{proof}
  }

  \problem { \
    \begin{lemma}\lemlabel{root-to-leaf}
      For any VLSI layout of a complete binary tree with $n$-leaves in
      a straight line, the wire area of the longest\footnote{ties are
        broken arbitrarily} root-to-leaf path is at least $n/2-1$.
    \end{lemma}
    \begin{proof}
      This lemma is fairly obvious.  Since the leaves are in a
      straight line, the distance between the leftmost and rightmost
      leaves must be at least $n-1$.  By the triangle inequality, one
      of the root-to-leaf paths (just considering the leftmost and
      rightmost leaves) is at least $(n-1)/2 > n/2 - 1$. 
    \end{proof}

    \begin{theorem}
      For any VLSI layout of a complete binary tree with $n$-leaves in
      a straight line, the total wire area is $\Omega(n\log n)$.
    \end{theorem}
    \begin{proof}
      We can prove this lemma with a simple recurrence.  Consider any
      VLSI layout of a complete binary tree with $n$-leaves in a
      straight line.  We let $A(n)$ be the minimum total wire area,
      not counting the longest root-to-leaf path in the tree, of any
      such layout.  Then we will show that the recurrence is $A(n)
      \geq 2A(n/2) + n/4 -1 = 2A(n/2) + O(n)$, which can be solved
      with the master method to get $A(n) = \Omega(n \log n)$.
      
      Consider any complete subtree $T$ with $k$ leaves in the VLSI
      layout.  The tree $T$ is composed of two $k/2$-leaf subtrees,
      $T_1$ and $T_2$, with a root node connecting to the roots of
      $T_1$ and $T_2$.  Without loss of generality, the longest
      root-to-leaf path in $T$ includes the longest root-to-leaf path
      in $T_1$.\footnote{The longest root-to-leaf path has to pass
        through the roots of one of the subtrees, so it must include
        the root-to-leaf path of one of the subtrees} Let $l_2$ be the
      length of the longest root-to-leaf path in $T_2$.  Let $A_1$ and
      $A_2$ be the total wire area of each of the subtrees $T_1$ and
      $T_2$, respectively, not counting the longest root-to-leaf
      paths.  Then the total wire area $A$ of $T$ not counting the
      longest root-to-leaf path is given by $A \geq A_1 + A_2 + l_2$.
      Since $T_1$ and $T_2$ have $k/2$ leaves, $T_1 \geq A(k/2)$, and
      $T_2 \geq A(k/2)$.  Thus, $A \geq 2A(k/2) + l_2$.  Applying
      \lemref{root-to-leaf}, we get $A(k) \geq 2A(k/2) + k/4 - 1$.
    \end{proof}

    Note that the above proof does not depend on the ordering of
    leaves in the VLSI layout.  That is to say, the leaves of the two
    $n/2$-leaf subtrees of an $n$-leaf VLSI layout can be interleaved
    and reordered arbitrarily without affecting correctness of the proof.
  }
  
  \problem { \ 
    That a binary tree with an even number of nodes can be cut exactly
    in half by cutting $O(\log n)$ edges follows directly from lecture
    on April~21.  We have the following two lemmas from class:
    
    \begin{lemma}\lemlabel{1-sep}
      Binary trees are $1$-separable.\qed
    \end{lemma}

    \begin{lemma}
      If a graph $G$ is $S$-separable, then $G$ is strongly
      $\Gamma_s$-separable.\qed
    \end{lemma}
    
    In class, we defined 
    \[
    \Gamma_s(n) = \sum_{i=0}^{\ceil{\log_{3/2} n}} S\paren{\paren{\frac{2}{3}}^i n}
    \ .
    \]
    By \lemref{1-sep}, we have that $S(n) = 1$ for a binary tree and
    any $n$ with $1 \leq n$.  Thus, $\Gamma_s(n) = O(\log n)$, and a
    binary tree is strongly $O(\log n)$-separable, meaning that it can
    be cut exactly in half by cutting $O(\log n)$ edges.

    Now, we consider the constants.  We have that $\Gamma_s(n) =
    \sum_{i=0}^{\ceil{\log_{3/2} n}} 1 = \ceil{\log_{3/2} n}$.  So the
    binary tree can be cut in half by cutting at most
    $\ceil{\log_{3/2} n}$ edges.  We can compute the appropriate
    constants by changing the base of the $\log$.
    
    \ 

    \ 
    
    For a binary tree, there is also a simple more direct\footnote{not
      relying on what we did in class, but similar} approach.
    Basically, i claim that for any binary tree with $n$ nodes, and a
    given number $k$, with $k\leq n$,  I can cut off a subtree with
    between $k/2$ and $k$ nodes with a single cut.
    
    \begin{lemma}\lemlabel{tree}
      Given a binary tree with $n$ nodes and an input $k$, with $1
      \leq k < n$, there is a cut of a single edge that cuts off
      between $k/2$ and $k$ nodes.
    \end{lemma}
    \begin{proof}
      Consider the depth (distance from root) of every node in the
      tree.  Iterate through all the nodes in order of depth starting
      from the deepest node, calculating the size of the full subtree
      rooted at each node.\footnote{ For example, a leaf is a subtree
        of size $1$.  A node with two leaves as children is the root
        of subtree with size $3$.}  Stop once a subtree with size
      $k/2$ to $k$ is found.  Cut the single edge connecting this
      subtree to the rest of the tree.
      
      The only point to prove is that we will always find a subtree of
      the correct size.  Assume for the sake of contradiction that the
      smallest subtree with a size at least $k/2$ that we can
      find is rooted at a node $v$ and has a size of $l > k$.  If $v$
      is a leaf, then we are done, because the size of the tree rooted
      at $v$ is $1$ (and $1 \not> k$).  If $v$ has $1$ child $v_1$,
      then the subtree rooted at $v_1$ has size $l-1$, which is
      better.  Suppose instead that $v$ has two children $v_1$ and
      $v_2$.  Then the size of $v$ is one more than the sum of the
      sizes of $v_1$ and $v_2$.  Thus, the sum of the sizes of the two
      subtrees is at most $k$, and it follows that one of the subtrees
      must be at least $k/2$, which generates a contradiction.
    \end{proof}
      
    Using \lemref{tree}, we can cut a binary tree exactly in half by
    cutting at most $\lg n$ edges.  For example, in the first cut, we
    ask for a subtree of size $n/2$.  In the worst case, we only get a
    subtree of size $n/4$, and we still need to cut off $n/4$ nodes.
    Thus, we ask for a subtree of size $n/4$ on the next iteration and
    may be unlucky again, getting a subtree of size $n/8$.  In the
    worst case, our cuts produce subtrees of size $\ceil{n/4} +
    \ceil{n/8} + \ceil{n/16} + \ldots$, requiring $\lg n$ cuts to cut
    the tree exactly in half.  
  }
  
  \problem { 
    \ We proved the following lemma in class
    on April~14.
    \begin{lemma}\lemlabel{butterfly}
      There is a layout for an $n$-input butterfy with only $O(n^2)$~area.\qed
    \end{lemma}

    Now, we show the following corollary, which is just a rewrite of
    the above lemma.
    \begin{corollary}
      There is a layout for a cube-connected-cycles network (or
      butterfly) with $n = k2^k$ vertices with only
      $O(n^2/\log^2n)$~area.
    \end{corollary}
    \begin{proof}
      A butterfly with $n = k2^k$ vertices is a butterfly with $m=2^k$
      inputs.  So, applying \lemref{butterfly}, there is a layout that
      takes $O(m^2) = O((2^k)^2)$ space.  We also have that $\lg n =
      \lg k + k$, or $k = \lg n - \lg k$.  Since $n > k$, we have $k =
      \Theta(\lg n - \lg \lg n)$.  Thus, we have that the area is
      $O((2^{\lg n - \lg \lg n})^2) = O((2^{\lg n} / 2^{\lg\lg n})^2)$,
      which reduces to $O(n^2 / \log^2 n)$.
    \end{proof}
  }
\end{problems}

\end{document}


