\documentstyle{article}

\setlength{\topmargin}{-0.8in}
\setlength{\oddsidemargin}{0in}
\setlength{\textwidth}{6.5in}
\setlength{\textheight}{9.25in}
\pagestyle{empty}

\begin{document}

\noindent
{\large Design and Analysis of Algorithms \hfill Neal Young}

\noindent
{\large Computer Science 45 \hfill}

\noindent
{\large Due: in class Friday, April 25, 1997 \hfill}

\vspace{.3in}

{\LARGE 
\begin{center}
Problem Set 3
\end{center}}
\vspace{.2in}

\begin{enumerate}

\item

  In class you figured out that the number of 5-digit decimal numbers
  with their digits summing to 27 was
  $$[z^{27}] \left(\frac{1-z^{10}}{1-z}\right)^5.$$
  (Recall that $[z^n] f(z)$ denotes the coefficient of $z^n$ in $f(z)$.)

  Figure out the actual number.\footnote{
    HINT: Use
    $(1-z^{10})^5 = 1 - 5 z^{10} + 10 z^{20} - 10 z^{30} + 5 z^{40} - z^{50}$.
    }

\item

  Let $S$ be the set of binary strings not containing ``011'' as a substring.

  (a) Give a deterministic finite automata accepting $S$.

  (b) Derive a generating function $\sum_n s_n z^n$ for $S$,
  where $s_n$ is the number of strings in $S$ of size $n$.\footnote{%
    HINT: for each state $q$ of your DFA, let $S_q$ denote the
    set of strings taking the DFA from the start state to $q$.
    Set up an unambiguous context free grammar for the sets $S_q$,
    from this obtain a set of equations relating the generating
    functions for the $S_q$'s.  Solve the equations.
    }
  
  (c) Use your generating function to obtain the best estimates
  you can for $s_n$.

\item
  The goal of this problem is to derive a closed form
  for the generating function $\sum_{n=0}^\infty {2n \choose n}z^{2n}$.

  Let $W$ be the set of binary strings with with equal numbers of 0's and 1's.

  (a) Why are there exactly ${2n \choose n}$ strings of length $2n$ in $W$?

  Let $P$ be the subset of $W$ such that every prefix of the string
  has as many 0's as 1's  (essentially this is balanced parens).

  Let $Q$ be the subset of $P$ such that every {\em proper} prefix of the
  string has {\em more} 0's than 1's.
  
  (b) Argue that $P \equiv Q^*$.

  (c) Argue that $Q \equiv \{0\}\times P \times \{1\}$.

  (d) Argue that
  $W \equiv \left( \{\mbox{up},\mbox{down}\}\times Q\right)^*$.

  (e) Use (b,c,d) to derive a generating function for $W$.

\item Exercise 33.7-2.
  
\end{enumerate}
\end{document}
