\documentclass[12pt]{article}
\usepackage{sariel}
\newcommand{\cC} {{\cal C}}
\newcommand{\np} {{\bf NP}}
\newcommand{\p} {{\bf P}}
\newcommand{\cnp} {{\bf co-NP}}
\newcommand{\spc}[1] {{\bf SPACE}$(#1)$}
\newcommand{\tm}[1] {{\bf TIME}$(#1)$}
\begin{document}
\pagestyle{empty}
%\pagestyle{empty}
\begin{center}
\pagestyle{empty}
%\titlepage
\vspace*{-.75in}
{\large University of Illinois at Urbana-Champaign}\\
{\large Department of Computer Science}\\ [0.5in]
{\LARGE\bf Qualifying Examination}\\ [0.2in]
{\large Theoretical Computer Science}\\ [0.1in]
Monday, February 18, 2002\\
\end{center}
\vspace*{0.4in}
\makeatletter
\long\def\hint#1{({\em Hint\/}: #1)}
\def\@oddhead{\rm\makebox[0in][l]{Theory Qualifying Exam---Fall,
2001}\hfil\thepage}
\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
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.
Also, in the box below, write a pseudonym of your choice (not your name
or ID) to be used in posting the results of this exam.
\centerline{
\Large
\begin{tabular}{|l|} \hline
ID Number: \hspace*{2in}\\
Pseudonym: \hspace*{2in}\\
\hline
\end{tabular}
}
Do all four problems in this booklet. The remaining four
problems will be in Part II this afternoon. All eight
problems are equally weighted, so do not spend too much time
on any one question. Blank pages follow each problem for
extra workspace.
\centerline{
\Large
\begin{tabular}{|c|c|c|c|} \hline
Question & Points & Score & Grader \\ \hline\hline
1 & 50 & & \\ \hline
2 & 50 & & \\ \hline
3 & 50 & & \\ \hline
4 & 50 & & \\ \hline
5 & 50 & & \\ \hline
6 & 50 & & \\ \hline
7 & 50 & & \\ \hline
8 & 50 & & \\ \hline\hline
Total & 400 & & \\ \hline
\end{tabular}
}
%\vfill
\pagestyle{empty}
\newpage
\pagestyle{plain}
\begin{enumerate}
\problem{Kleene Star} Recall that the {\em Kleene Star} of a
language $L$ is $L^* = \{x_1x_2\ldots x_k\: |\: k \geq 0
\mbox{ and } x_1,x_2,\ldots x_k \in L\}$. Are the
following complexity classes closed under Kleene Star?
Please provide arguments to support your answer.
\begin{enumerate}
\item \np
\item \p
\item \cnp
\item \np$\cap$\cnp
\end{enumerate}
\newpage
\problem{Linear space}
Recall that \space{n} is the
class of languages recognized by deterministic Turing
machines in $O(n)$ space. Show that \np$\neq$\spc{n}.
{\bf Warning:} Solving either possible containment would
be a major result. The easy solution involves
exhibiting a property that one class has and the other
does not.
\newpage
\problem{Matrix Search}
You are given a matrix $M$ of size $n \times k$. The
matrix is monotonically increasing sorted in both rows
and columns.
\begin{itemize}
\item Describe an algorithm, as fast as possible,
that given a number $x$, outputs whether or not $x$
is in the matrix. Your algorithm should be as fast
as possible, as a function of $n$ and $k$.
\item Prove a lower bound, as tight as possible, for
this searching problem in an appropriate computing
model. The lower bound should be a function of both
$n$ and $k$.
\end{itemize}
\newpage \problem{Security} The existence of secure
cryptographic primitives relies crucially on the
existence a special class of functions called {\em
one-way functions}. Informally, these are functions
that are ``easy to compute but hard to invert''. The
formal definition is as follows:
\begin{itemize}
\item[] A one-way function is a length preserving
function $f$ (i.e., $\forall w.\: |f(w)| = |w|$)
with the following two properties:
\begin{enumerate}
\item $f$ is computable in polynomial time.
\item There is no polynomial time algorithm
which given $y$ computes an $x$ such that $f(x)
= y$ or returns ``no'', if such an $x$ does not
exist.
\end{enumerate}
\end{itemize}
[{\bf Note:} The above definition is slightly different
from what is conventionally used in cryptography, where
a function is one-way if no {\em probabilistic
polynomial time algorithm} can invert the function
{\em on average}.]
Assume that $f$, $f_1$ and $f_2$ are one-way functions
from $\{0,1\}^*$ to $\{0,1\}^*$. For a string $x \in
\{0,1\}^*$ let $\overline{x}$ denote the bitwise
negation of $x$. For example $\overline{01101} = 10010$.
Are the following functions one-way? Give proofs for
your answer.
\begin{enumerate}
\item $g(x) = f(\overline{x})$
\item $g(x) = f_1(f_2(x))$
\item $g(x_1\cdot x_2) = f(x_1)\cdot \overline{f(x_2)}$, where $|x_1|
= |x_2|$ and $u\cdot v$ is the concatenation of strings $u$ and $v$.
\end{enumerate}
\newpage
~
\newpage
~
\newpage
~
\newpage
~
\newpage
~
\newpage
~
\begin{center}
{\large University of Illinois at Urbana-Champaign}\\
{\large Department of Computer Science}\\ [0.5in]
{\LARGE\bf Qualifying Examination}\\ [0.2in]
{\large Theoretical Computer Science}\\ [0.1in]
Monday, February 18, 2002\\
~
{\LARGE {\bf PART II}}
\end{center}
\vspace*{0.4in}
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.
Also, in the box below, write a pseudonym of your choice (not your name
or ID) to be used in posting the results of this exam.
~
~
\centerline{
\Large
\begin{tabular}{|l|} \hline
ID Number: \hspace*{2in}\\
Pseudonym: \hspace*{2in}\\
\hline
\end{tabular}
}
\newpage
\problem{Optimal worst-case algorithm}
\begin{enumerate}
\item Solve the following recurrence.
\[
T(n) = O(n) + O(n/\log n)\cdot T(\log n)
\]
\item Suppose we have an algorithm whose running
time obeys the recurrence in part (a). Our
algorithm may or may not be optimal; the strongest
lower bound we have for the problem is $\Omega(n)$.
Design and analyze an algorithm that is guaranteed
to have optimal worst-case running time, \emph{even
though you don't know what the optimal worst-case
running time is}. For example, if \emph{any}
algorithm runs in linear time, then \emph{your}
algorithm must run in linear time. In order to make
this optimality statement precise, you may need to
choose a particular model of computation (RAM,
Turing machine, algebraic decision tree, etc.).
\end{enumerate}
\newpage
\problem{Coloring planar graphs.} It is well known that
for a planar graph $G =(V,E)$ with $n$ vertices, there
is always a subset $S$ of $O(\sqrt{n})$ vertices of $G$,
such that $G \setminus S$ is disconnected, and each
connected component has at most $(2/3)n$ vertices.
Furthermore, one can find this set $S$ in $O(n)$ time.
The set $S$ is called a {\em separating set} for $G$.
\begin{enumerate}
\item Prove {\em directly} that any planar graph can
be vertex colored by $6$ colors.
\item Describe an algorithm that computes the
minimum coloring of a planar graph in
$n^{O(\sqrt{n})}$ time, where $n$ is the number of
vertices of the graph.
\end{enumerate}
\newpage \problem{Some recurrences.} Solve the following
recurrences:
\begin{enumerate}
\item $A(n) = A(n/2) + 1/n$
\item $B(n) = 2(\log( B(n-1) ) + 1)$
\item $\displaystyle C(n) = \sum_{i=1}^{n/2} C(n_i)
+ C(n/2) + O(n\log{n})$, where $\sum_{i=1}^{n/2} n_i
= n$, and $n_1, \ldots, n_{n/2} \leq n/2$.
\item $\displaystyle D(n) = \sum_{i=1}^{n-1} \frac{D(i)}{i} + 5$
\item $\displaystyle E(n) = E\pth{ \floor{\frac{n}{\log \log{n}}
}} + \log{n}$
\end{enumerate}
\newpage
\problem{Fixed Parameter Complexity}
Recall vertex cover is the problem of determining given
a graph $G$ and number $k$ whether or not there is a
subset of vertices of cardinality $k$ or less such that
each edge is incident to at least one of the vertices.
Give an algorithm for vertex cover that runs in time
$f(k)p(|G|)$, where $p$ is a polynomial, and $f$ is any
function. How does this compare with the obvious
$O(|G|^{k})$ algorithm?
\end{enumerate}
\newpage
~
\newpage
~
\newpage
~
\newpage
~
\newpage
~
\end{document}
\documentclass[12pt]{article}
\usepackage{sariel,wide}
\begin{document}
\begin{enumerate}