\documentstyle[11pt,fullpage]{article}
\begin{document}
\begin{center}
\titlepage
\vspace*{-.75in}
{\large University of Illinois at Urbana-Champaign}\\
{\large Department of Computer Science}\\ [0.5in]
{\LARGE\bf Qualifying Examination---Part I}\\ [0.2in]
{\large Theoretical Computer Science}\\ [0.1in]
9 a.m.--12 noon, Monday, September 29, 1997\\
2211 Digital Computer Laboratory
\end{center}
\vspace*{0.4in}
\makeatletter
\long\def\hint#1{({\em Hint\/}: #1)}
\def\@oddhead{\rm\makebox[0in][l]{Fall 1997 Theory Qualifying Exam, I}\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. 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.
\vfill
\centerline{
\Large
\begin{tabular}{|l|} \hline
ID Number: \hspace*{2in}\\
Pseudonym: \hspace*{2in}\\
\hline
\end{tabular}
}
\vfill
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.
\vfill
\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
\begin{enumerate}
\problem{Elementary data structures}
Let $F$ be a forest of $m$ trees with a total of $m \geq n$ leaves. Each node
has a pointer to its parent but there are no pointers to the children.
Consider the problem of determining for each leaf the root of its tree.
\begin{enumerate}
\item
What is the worst-case time-complexity if the algorithm traverses
all paths from the $n$ leaves to the $m$ roots?
%% ANSWER: $m = 1$ and O($n^2$).
\item
What is the best-case time-complexity of the algorithm in part (a)
given in terms of $n$ and $m$?
%% ANSWER: O($n \log_2 {n \over m}$).
\item
Give a different algorithm that does the same job in time O($n$)
without allocating any extra memory.
\end{enumerate}
%\extrapage
%\extrapage
\problem{Approximation algorithms}
In a simplified parallel scheduling problem, assume we have a parallel machine
which is a one-dimensional mesh machine of $n$ processors, that is, a machine
with $n$ processors $p_1, \ldots, p_n$ where $p_i$ is connected directly to
$p_{i-1}$ and $p_{i+1}$. Assume we have $m$ jobs, $J_1, \ldots, J_m$, where
$J_i$ requests $t_i$ time on $n_i$ adjacent processors. Only one job can be
scheduled on a processor at any time. The {\em make-span} of a schedule is
the time between the start to the finish of all jobs.
Given a 3-approximation algorithm for this scheduling problem.
%\extrapage
%\extrapage
\problem{Dynamic programming}
The (simplified) speech recoginition problem can be described as an
edge-weighted, directed graph $G=(V,E)$ in which each node corresponds to a
word. There is an edge from $u$ and $v$ if $v$ can follow $u$; the weight of
edge $W(u,v)$ is the transition probability of seeing the word $u$ immediately
after word $v$. We are given a sequence of probability vectors $T^i$, each of
length $|V|$, the number of words, such that $T_j^i$ is the probability that
we heard word $j$ at time $i$.
The speech recognition problem is:
\hspace*{0.4in} Input: $G$ and vectors $T^1, \ldots,T^k$.
\hspace*{0.4in} Output: A path $P=v_{t_1},
\ldots,v_{t_k}$ maximizing the product:
\[T_{t_1}^1 W(v_{t_1},v_{t_2}) \cdots T_{t_{k-1}}^{k-1}
W(v_{t_{k-1}},v_{t_k}) T_{t_{k}}^k\]
Devise an $O(|E|k)$-time dynamic programming algorithm to find the best
sentence.
%\extrapage
%\extrapage
\problem{Strings}
Let $\Sigma$ be a finite alphabet, and let $S_0$, $S_1$, \ldots be an infinite
sequence of (finite length) strings over $\Sigma^*$. Say that string $S_i$
{\em embeds} in string $S_j$ if and only if the characters of $S_i$ appear, in
order, as a not necessarily contiguous subsequence within $S_j$. For example,
$aba$ embeds in $aaabcda$, but not in $aab$. Prove that for some $i