\documentclass[11pt]{article}
\usepackage{jeffe,handout,graphicx}
\newtheorem{theorem}{Theorem}
\newcommand{\Hint}[1]{\emph{[#1]}}
% ======================================================================
\begin{document}
\begin{center}
\LARGE
\textbf{Algorithms and Theoretical Computer Science}
\\
\textbf{Ph.D. Qualifying Examination}
\\
\textbf{Spring 2003}
\bigskip
\begin{tabular}{|p{2.5in}|p{2.5in}|}
\hline
\multicolumn{2}{|l|}{Name:}
\\\hline
Net ID: & Alias:
\\\hline
\end{tabular}
\vfil
\normalsize
\hrule
\begin{itemize}
\item
Please print your name, NetID, and an alias of your choice in the boxes above.
Write your alias, but \emph{not} your name or netID, on each page of your answers. Using an alias will allow us to grade your exam anonymously.
\item
The exam consists of eight written questions, four in the morning and four in the afternoon. You will have three hours for each group of four questions. Please start your answers to each numbered question on a new sheet of paper.
\item
All else being equal, it is better to solve some of the problems completely than to get partial credit on every problem.
\end{itemize}
\hrule
\vfil
\LARGE
\begin{tabular}{|c|c|c|}
\hline
\# & Score & Grader \\\hline\hline
1 & & \\\hline
2 & & \\\hline
3 & & \\\hline
4 & & \\\hline\hline
5 & & \\\hline
6 & & \\\hline
7 & & \\\hline
8 & & \\\hline\hline
$\Sum$ & & \\\hline
\end{tabular}
\end{center}
% ----------------------------------------------------------------------
\headers{Theory Qualifying Examination (Part One)}{}{Spring 2003}
\noindent
Please start your answers for each numbered question on a new sheet of paper. Write your alias, but \emph{not} your name or NetID, on each page of your answers.
\begin{enumerate}
\item
A sequence $\seq{a_1, a_2, \dots, a_k}$ of distinct real numbers is \emph{monotone} if either ${a_1 < a_2 < \cdots < a_k}$ or ${a_1 > a_2 > \cdots > a_k}$. Prove \emph{Dilworth's Theorem}: Any sequence of $n$ distinct real numbers contains a monotone subsequence of length at least $\sqrt{n}$. For example, the sequence $\seq{3,1,4,5,9,2,6,8,7}$ contains the monotone subsequence $\seq{3,5,6,8}$.
\item
This question asks you to to design and analyze a \emph{randomized incremental} algorithm to select the $k$th smallest element from a given set of $n$ elements (from a universe with a linear order).
In an \emph{incremental} algorithm, the input consists of a sequence of elements $x_1, x_2, \dots, x_n$. After any prefix $x_1, \dots, x_{i-1}$ has been considered, the algorithm has computed the $k$th smallest element in $x_1, \dots, x_{i-1}$ (which is undefined if $i\le k$), or if appropriate, some other invariant from which the $k$th smallest element could be determined. This invariant is updated as the next element $x_i$ is considered.
Any incremental algorithm can be \emph{randomized} by first randomly permuting the input sequence, with each permutation equally likely.
\begin{enumerate}
\item
Describe an incremental algorithm for computing the $k$th smallest element.
\item
How many comparisons does your algorithm perform in the worst case?
\item What is the expected number (over all permutations) of
comparisons performed by the randomized version of your
algorithm? \Hint{When considering $x_i$, what is the
probability that $x_i$ is smaller than the $k$th smallest
so far?} You should aim for a bound of at most
$n+O(k\log(n/k))$. Revise (a) if necessary in order to
achieve this.
\end{enumerate}
\item
A \emph{swap} transforms one permutation into another by exchanging one pair of adjacent elements. The \emph{swap distance} between two permutations is the minimum number of swaps required to transform one permutation into the other. For example, the swap distance between $\seq{1,4,3,2}$ and $\seq{1,2,3,4}$ is $3$; we can transform one permutation into the other with three swaps
\[
\seq{1,4,\underline{3,2}} \to
\seq{1,\underline{4,2},3} \to
\seq{1,2,\underline{4,3}} \to \seq{1,2,3,4}
\]
but not with two swaps.
\begin{enumerate}
\item
Describe an efficient algorithm to compute the swap distance between two given permutations of the set $\set{1,2,\dots,n}$.
\item
Prove that your algorithm is optimal in some appropriate model of computation.
\item
Prove that the expected swap distance between two random permutations of $\set{1,2,\dots,n}$ is $\Theta(n^2)$.
\end{enumerate}
\item Let $f: \set{0,1}^* \to \set{0,1}^*$ be a
polynomial-time reduction from $A$ to $B$. In addition, let
$f$ be one-to-one, $f^{-1}$ be computable in polynomial
time, and $f$ be length-increasing, that is, $|f(w)| > |w|$
for all $w$. Let $g$ be a polynomial-time reduction from
$B$ to $A$, such that $g$ is also one-to-one and
length-increasing, and $g^{-1}$ is computable in polynomial
time. Show that there is a reduction $h$ from $A$ to $B$
such that $h$ is a bijection and both $h$ and $h^{-1}$ are
computable in polynomial time. \Hint{Try to partition $A$
into sets $A_1$ and $A_2$ such that $B = f(A_1) \cup
g^{-1}(A_2)$, and membership of a string in $A_1$ is
decidable in polynomial time.}
\end{enumerate}
%----------------------------------------------------------------------
\headers{Theory Qualifying Examination (Part Two)}{}{Spring 2003}
\noindent
Please start your answers for each numbered question on a new sheet of paper. Write your alias, but \emph{not} your name or NetID, on each page of your answers.
\begin{enumerate}
\setcounter{enumi}{4}
\item
Every year, upon their arrival at Hogwarts School of Witchcraft and Wizardry, new students are sorted into one of four houses (Gryffindor, Hufflepuff, Ravenclaw, or Slytherin) by the Hogwarts Sorting Hat. The student puts the Hat on their head, and the Hat tells the student which house they will join. This year, a failed experiment by Fred and George Weasley filled almost all of Hogwarts with sticky brown goo, mere moments before the annual Sorting. As a result, the Sorting had to take place in the basement hallways, where there was so little room to move that the students had to stand in a long line.
After everyone learned what house they were in, the students tried to group together by house, but there was too little room in the hallway for more than one student to move at a time. Fortunately, the Sorting Hat took CS 373 many years ago, so it knew how to group the students as quickly as possible. What method did the Sorting Hat use?
\vspace{-2ex}
{\sf\small
\begin{gather*}
\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline
G & H & R & R & G &
G & R & G & H & H &
R & S & R & R & H &
G & S & H & G & G \\[-0.5ex]
\text{\tiny Harry} &
\text{\tiny Ann} &
\text{\tiny Bob} &
\text{\tiny Tina} &
\text{\tiny Chad} &
\text{\tiny Bill} &
\text{\tiny Lisa} &
\text{\tiny Ekta} &
\text{\tiny Bart} &
\text{\tiny Jim} &
\text{\tiny John} &
\text{\tiny Jeff} &
\text{\tiny Liz} &
\text{\tiny Mary} &
\text{\tiny Dawn} &
\text{\tiny Nick} &
\text{\tiny Kim} &
\text{\tiny Fox} &
\text{\tiny Dana} &
\text{\tiny Mel} \\
\hline
\end{array}
\\[-0.9ex]
\Big\Downarrow
\\[-0.9ex]
\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline
G & G & G & G & G &
G & G & H & H & H &
H & H & R & R & R &
R & R & R & S & S \\[-0.5ex]
\text{\tiny Harry} &
\text{\tiny Ekta} &
\text{\tiny Bill} &
\text{\tiny Chad} &
\text{\tiny Nick} &
\text{\tiny Mel} &
\text{\tiny Dana} &
%
\text{\tiny Fox} &
\text{\tiny Ann} &
\text{\tiny Jim} &
\text{\tiny Dawn} &
\text{\tiny Bart} &
%
\text{\tiny Lisa} &
\text{\tiny Tina} &
\text{\tiny John} &
\text{\tiny Bob} &
\text{\tiny Liz} &
\text{\tiny Mary} &
%
\text{\tiny Kim} &
\text{\tiny Jeff} \\
\hline
\end{array}
\end{gather*}
}
\begin{enumerate}
\item
More formally, you are given an array of $n$ items, where each item has one of four possible values, possibly with a pointer to some additional data. Describe an algorithm that rearranges the items into four clusters in $O(n)$ time using only $O(1)$ extra space.
\item
Now suppose there are $k$ possible values instead of four. Describe and analyze an efficient algorithm that rearranges the items using only $O(\log{k})$ extra space.
\item
Describe and analyze a faster algorithm (if possible) that uses $O(k)$ extra space.
\item
Describe and analyze an efficient algorithm that uses $O(1)$ extra space.
\end{enumerate}
\item
Let $f$ be a polynomial time computable (partial) function. We say that $f$ is \emph{honest} if it doesn't map very long inputs to very short ones, that is, if and only if there is a polynomial~$p$ such that for all $y \in$ range$(f)$, there exists $x$ such that $f(x) = y$ and $\abs{x} \le p(\abs{y})$.
Prove that P = NP if and only if every honest partial polynomial time
computable function has a polynomial-time computable inverse.
\item
The NP-hard \textsc{Subset Sum} problem asks, given a multiset $X$ of $n$ integers and an integer~$k$, whether $X$ contains a submultiset whose elements sum to $k$. For example, given the multiset $\set{\underline{3}, 1, 4, 1, 5, \underline{9}, 2, \underline{6}, \underline{5}, 3, \underline{5}, 8, \underline{9}, 7, 9, \underline{3}, 2, 3, 8, 4, 6, \underline{2}, 7}$ and the integer $42$, the algorithm would return \textsc{True}, since
\[
3 + 9 + 6 + 5 + 5 + 9 + 3 + 2 = 42.
\]
Describe an algorithm that solves the \textsc{Subset Sum} problem in time $O(n + f(k))$, where the function $f(k)$ is independent of $n$ and as small as possible.
\item
Show that there exists an infinite set $A \subseteq \{0,1\}^*$ having no infinite recursively enumerable subset. \Hint{Think of defining $\overline{A}$ such that every infinite r.e.\ set has a non-empty intersection with $\overline{A}$; but ensure that $A$ is infinite.}
\end{enumerate}
\end{document}