\documentstyle[psfig,11pt]{article}


\newcounter{problem}

\newenvironment{problems}{\begin{enumerate}\setcounter{enumi}{\theproblem}}{\setcounter{problem}{\theenumi}\end{enumerate}}
%\newenvironment{problems}{\begin{enumerate}}{\end{enumerate}}

\pagestyle{empty}

\textheight 9.3in
\addtolength{\oddsidemargin}{-0.7in}
\addtolength{\textwidth}{1.2in}
\topmargin -0.3in
\headheight 0.1in
\headsep 0.1in

\begin{document}
{\large
\fbox{\parbox{6.1in}{
\hbox to \hsize{\ \ \ 10 Powerful Ideas  \hfil 
Bruce Maggs}
\vskip 0.1in
\hbox to \hsize{\ \ \ Quiz 2 Review Exercises \hfil Quiz 2: {\bf Monday, March 16, 1998}}
}}}
\vskip 0.1in

% magic for a Postscript figure:
%
%\begin{figure}[h]
%\centerline{\psfig{file=,width=}}
%\caption{}
%\end{figure}

Solutions to these problems will be available on the course Web site
by Saturday.

\section*{Counting}

\begin{problems}

\item
How many 5 card hands (from a 52 card deck) have the same
number of Spades and Hearts?

\item 
How many ways to rearrange the letters ``{\bf INSTRUCTOR}''?

\item 
How many ways to rearrange ``{\bf INSTRUCTOR}'' 
with all vowels consecutive?

\item 
How many ways to rearrange ``{\bf INSTRUCTOR}'' 
with no two vowels consecutive?

\item
How many integer solutions to the following equation?
\[ X_1 + X_2 + X_3 + X_4 + X_5 = 100,\ \  0 \leq X_i \leq 30 \]

\item Give a closed-form formula for
the sum of the 10th powers of the numbers 1 through $n$. (If $n=3$,
that would be $1^{10} + 2^{10} +3^{10} = 60074$.)  {\it Hint: see
the end of Lecture 12.}

\end{problems}


\section*{Infinity}

\begin{problems}

\item
Show that $N \times N$ (the set of ordered pairs of natural numbers) is
countable.

\item
Show that the set of all $C$ programs is countable, or prove that it is not.

\item
Recall that the powerset ${\cal P} (S)$ of a set $S$ is the set of all
subsets of $S$.
\begin{enumerate}
\item
If $|S| = n$, what is $|{\cal P} (S)|$?

\item
Show that ${\cal P} (N)$ is uncountable.
\end{enumerate}

\item 
Imagine a language with a countably infinite alphabet---in which, for example,
anyone could make up a new letter whenever they wanted. Is the set of all
strings in this language countable?

\end{problems}

\section*{Undecidability}

Recall that the halting problem is undecidable, i.e., it is impossible
to write a program $X$ that takes as its input a description of any
program $Y$ and determines whether $Y$ will halt when given its own
description as input.  I.e., $X$ cannot decide whether $Y(Y)$ will
halt for all values of $Y$.

\begin{problems}

\item It might seem a little strange to feed a program a description
of itself as input, since, after all, very few programs take
descriptions of other programs as inputs.  So, let's simplify the
problem by doing away with $Y$'s input altogether.  Is it possible to
design a program $X'$ that takes as its input a description of a
program $Y$ that contains no input statements, and determines whether
$Y$ halts?

\item Suppose that as a compiler writer, you have a more modest goal.
You'd like your compiler $X$ to take as its input a program $Y$ (that
takes no inputs) and determine whether or not $Y$ initializes all of
its variables before they are used.  Using a reduction from the
halting problem to this problem, show that this problem is still
undecidable.

\item How about this problem -- is it possible to write a program
$X''$ that takes as its input a $C$-program $Y$ and determines whether
each variable has been declared before it is used in $Y$?

\end{problems}

\section*{NP-Completeness}

\begin{problems}

\item
How many different 4-cliques does a 10-clique contain?

\item
Suppose you are given a subroutine that solves the $k$-clique decision
problem.  Show how to use this subroutine to solve the $k$-clique
search problem in polynomial time, assuming that a call to the
subroutine takes only one step.

\item In class we noted that the problem of 3-coloring a graph is
NP-complete, and that the problem of determining, when given a graph
$G$ and a number $k$ as input, whether $G$ has a $k$-clique, is also
NP-complete.  What about the problem of determining if a graph has a
3-clique?  Show that there is an algorithm for solving this problem in
$O(n^3)$ time, where $n$ is the number of vertices in the graph.
Is this a contradiction?  If not, why not?

\item Ben Bitdiddle, an aspiring 15-299 student, has just made the
discovery of a lifetime: Ben has found a polynomial-time reduction
from the problem of finding the shortest path in a graph (where all
edges have non-negative weights) to the $NP$-complete problem of
3-coloring a graph.  From 15-211, Ben knows that the problem of
finding the shortest path in a graph in which all edges have
non-negative weights can easily be solved in polynomial time.  Before
Ben turns his discovery in for extra credit, he wants to run it by
you.  What's your advice to Ben?


\end{problems}

\section*{Finite Automata}

\begin{problems}

\item
Draw finite automata that accept the following languages over the
alphabet $\{0,1\}$:
\begin{enumerate}
\item
the set of all strings ending $1011$

\item 
the set of all strings which are congruent to 0 modulo 3 (when
interpreted as integers written in binary notation).

\end{enumerate}

\item
Describe (in English) the languages accepted by the following finite
automata.

\centerline{\psfig{file=fsa1.eps,height=0.4in}}
\vspace{0.5in}
\centerline{\psfig{file=fsa2.eps,height=0.8in}}


\end{problems}



\end{document}

