\documentclass{article}
\usepackage{fullpage}
\begin{document}
\begin{center}
\thispagestyle{empty}
\vspace*{-.75in}
{\large University of Illinois at Urbana-Champaign}\\
{\large Department of Computer Science}\\ [0.5in]
{\LARGE\bf Qualifying Examination---Part II}\\ [0.2in]
{\large Theoretical Computer Science}\\ [0.1in]
1--4pm, Monday, February 15, 1999\\
2263 Digital Computer Laboratory
\end{center}
\vspace*{0.4in}
\makeatletter
\long\def\hint#1{({\em Hint\/}: #1)}
\def\@oddhead{\rm\makebox[0in][l]{Theory Qualifying Exam---Spring,
1999}\hfil\thepage\hfil\makebox[0in][r]{ID Number:\rule[-0.1in]{2in}{.5pt}}}
\let\@evenhead\@oddhead
\def\@oddfoot{}
\let\@evenfoot\@oddfoot
\def\problem#1{\def\problemheading{#1}\clearpage\item{\bf #1.}}
\let\part\item
\renewcommand{\theenumii}{\alph{enumii}}
\def\extrapage{\addtocounter{enumi}{-1}\clearpage\item{\bf \problemheading, continued.}}
\makeatother
\parindent 0pt
\vfill
Do not write your name anywhere on this examination, so that
the exam can be graded without knowledge of your identity.
Write your ID number legibly in the box below and at the
upper right corner of every page.
\vfill
\centerline{
\Large
\begin{tabular}{|l|} \hline
ID Number: \hspace*{2in}\\
Pseudonym: \hspace*{2in}\\
\hline
\end{tabular}
}
\vfill
Do all three problems in this booklet. All of this morning's and this
afternoon's problems are equally weighted, so do not spend too much time on
any one question. Blank pages follow each problem for extra workspace.
\vfill
\begin{enumerate}
\setcounter{enumi}{3}
\problem{Complexity}
Let $G=(V,E)$ be a graph with $|V|=n$.
It is known that the problem of counting the number of independent sets
in $G$ is \#P complete. Show that the problem of counting the number
of maximum cardinality independent sets in $G$ is also \#P complete.
%\extrapage
\problem{Computability}
Consider a Turing Machine that before {\em each} transition, flips a coin.
The coin has probability $h$ of landing heads, and $1-h$ of landing tails.
The transition function of the TM is now also a function of the current state,
the currently scanned symbol, and the result of the coin flip.
For each triple of real numbers $h, p_1, p_2$ in the closed interval [0,1], we
can define the following class of languages:
$C(h, p_1, p_2) = \{L:$ there exists a polynomial $p$ and a coin-flipping TM
$M$ using a coin with probability of heads $h$ such that on any input $x$, $M$
halts within $p(|x|)$ steps and outputs ``accept'' or ``reject''.
Furthermore, if $x \in L$, then Pr($M$ accepts $x$) $> p_1$, and if $x \notin
L$ then Pr($M$ accepts $x$) $< p_2.\}$
Compare the classes of languages
$C(.5, .5, .5),$ $C(.5, .75, .25),$ $C(.01, .75, .25),$ $C(.5, .25, .75),$
and $C(.01, .5, 0)$ with each other and with known complexity classes.
Briefly argue any containments or equalities.
Note that as written, the last class $C(.01, .5, 0)$ is in fact trivial,
because the definition requires that if $x \notin L,$ then Pr($M$ accepts $x$)
$< 0$, an impossibility. For this last class only, replace this condition
with Pr($M$ accepts $x$) $= 0$.
%\extrapage
% \problem{Decision Trees}
% \def\?={\stackrel{?}{=}}
% A {\em decision-tree} on variable set $X = \{x_1, \ldots, x_n\}$ is a labeled
% rooted binary tree, where the label of each interior node is a {\em condition}
% of the form ``$x_i \?= b$'', where $x_i$ is a variable, and $b \in \{0,1\}.$
% The label of each leaf is either ``0'' or ``1''. Further, each interior node
% has exactly two children.
% A decision tree $T$ represents a Boolean function $f_T : \{0,1\}^n \rightarrow
% \{0,1\}$, whose value is given by the following recursive rule.
% \begin{itemize}
% \item If the tree $T$ is just a single node (a leaf) $v$, then for any
% assignment $a$, $f_T (a) = \mbox{\em label}(v).$
% \item If the tree $T$ is not a single node, but is rooted at node $v$ labeled
% with condition ``$x_i \?= b$'', then $f_T (a) = f_{T'} (a)$, where $T'$ is the
% right subtree of $T$ if $a$ assigns variable $x_i$ the value $b$, and $T'$ is
% the left subtree of $T$ if $a$ does not assign $x_i$ the value $b$.
% \end{itemize}
% \begin{enumerate}
% \item If $f$ is an arbitrary Boolean function, is there a
% decision-tree $T$ equivalent to $f$? Prove or give a counterexample.
% \item A {\em decision-list} is a decision-tree with the property
% that for every interior vertex $v$, the right-child of $v$ is a leaf. If $f$
% is an arbitrary Boolean function, is there a decision-list $L$ equivalent to
% $f?$ Prove or give a counterexample.
% \item Describe a polynomial-time algorithm that on input of
% disjoint sets $S_0 \subset \{0,1\}^n$, and $S_1 \subset \{0,1\}^n$, outputs in
% time polynomial in $|S_0| + |S_1|$, a decision-list $L$ such that $L(a) = 0$
% for each assignment $a \in S_0$, and $L(a) = 1$ for each assignment $a \in
% S_1$. If no such $L$ exists, your algorithm should detect this.
% \end{enumerate}
% \extrapage
\problem{Trees}
Consider a complete ternary tree of height $h$ in which each leaf has a
boolean value associated with it. Each internal node represents the
``majority operator'' which gives the value returned by the majority of its
children. The evaluation problem consists of determining the value at the
root of the tree.
\begin{enumerate}
\item Show that for any deterministic algorithm, there is an instance (a set
of Boolean values for the leaves) that forces the algorithm to examine all $n
= 3^h$ leaves.
\item Consider the recursive randomized algorithm that evaluates two subtrees
of the root chosen at random. If the values returned disagree, it proceeds to
evaluate the third subtree. What is the expected number of leaves read by
this algorithm on a random tree?
\end{enumerate}
%\extrapage
\end{enumerate}
\end{document}