\documentclass{article}
\usepackage{epsfig,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 I}\\ [0.2in]
{\large Theoretical Computer Science}\\ [0.1in]
9am--12 noon, 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.
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 three problems in this booklet. The remaining three problems will be
in Part II this afternoon. All six 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\hline
Total & 300 & & \\ \hline
\end{tabular}
}
\vfill
\begin{enumerate}
\problem{Algorithm Design and Analysis}
\def\set#1{\{ #1 \}}
Describe and analyze algorithms to solve the following problems, given an
array of $n$ integers as input.
\begin{enumerate}
\item Find a nontrivial three-term arithmetic progression of array elements,
or report that no such sequence exists. In other words, if possible, report
three distinct indices $1\le i,j,k\le n $ such that $A[j] - A[i] = A[k] -
A[j]$.
% O(n^2) is easy (and optimal in some models of computation).
\item Find an arithmetic progression with more than $\lceil 2n/3 \rceil$ array
elements, or report that none exists. \hint{Show that there can be at most
one such sequence and use divide and conquer.}
\item Find the longest nontrivial arithmetic progression of array elements.
In other words, report a largest set of distinct indices $\set{i_1,\dots,i_k}$
such that $A[i_{j+1}] - A[i_j]$ has the same value for all $1\le j< k$.
% O(n^2 log n) by a bizarre dynamic programming algorithm.
% Is O(n^2) possible???
\end{enumerate}
%\extrapage
% \problem{Computational Geometry}
% Consider the following point clustering problem:
% Given a set of $n$ points $P$ in 3-dimensional Euclidean spaces and
% a positive integer $k$, decompose the point set $P$ into
% $k$ disjoint subsets $P_1$, ..., $P_k$, so that the largest
% diameter among these subsets is minimized, where the diameter
% of a point set is the maximum Euclidean distance between two points
% in the set.
% An algorithm has an approximation ratio $\alpha \geq 1$ if
% the solution it generates has the maximum diameter no more
% than $\alpha$ times that of the optimal solution.
% Design a $2$-approximation polynomial time algorithm and prove
% that it achieves the approximation ratio $2$.
% \extrapage
\problem{Algorithm Design and Analysis} \def\seq#1{\langle #1 \rangle}
Almost all computer graphics systems, at some level, represent objects
as collections of triangles. In order to minimize storage space and
rendering time, many systems allow objects to be stored as a set of
\emph{triangle strips}. A triangle strip is a sequence of vertices
$\seq{v_1, v_2, \dots, v_k}$, where each contiguous triple of vertices
$v_i, v_{i+1}, v_{i+2}$ represents a triangle.
As the rendering system reads the sequence of vertices and draws the
triangles, it keeps the two most recent vertices in a cache. Some
systems allow triangle strips to contain \emph{swaps}: special flags
indicating that the order of the two cached vertices should be
reversed. For example, the triangle strip $\seq{a, b, c, d,
\mathsf{swap}, e, f, \mathsf{swap}, g, h, i}$ represents the sequence
of triangles $(a,b,c)$, $(b,c,d)$, $(d,c,e)$, $(c,e,f)$, $(f,e,g)$, $(e,g,h)$,
$(g,h,i)$.
%\centerline{\epsfig{file=tristrip.ps,height=1.25in}}
Two triangle strips are \emph{disjoint} if they share no triangles (although
they may share vertices). The adjacency graph of a triangle strip is a
simple path; if this path alternates between left and right turns no swaps
are needed.
You are given a set $S$ of interior-disjoint triangles whose
adjacency graph is a tree. (In other words, $S$ is a triangulation of
a simple polygon.)
\begin{enumerate}
\item Let the \emph{length} of a triangle strip be the length
of its vertex sequence, {\em excluding swaps} (for example, the length of the
example strip above is 9). Describe a linear-time algorithm to decompose $S$
into a set of disjoint triangle strips of minimum total length.
\hint{Consider the dual tree.}
\item Repeat part (a) when the length of a triangle strip is the length
of its vertex sequence, {\em including swaps} (for example, the length of the
example strip above is 11).
% Dynamic programming over the dual tree.
% ----------------------------------------------------------------------
\end{enumerate}
%\extrapage
\problem{Satisfiability}
Consider the Boolean function $f:\{0,1\}^n \rightarrow \{0,1\}$
represented in DNF. That is, $f$ is given as
$$f = \bigvee_{i=1}^m d_i$$
where each $d_k$ is a conjunction of literals.
\begin{enumerate}
\item Denote by $S$ the set of all satisfying assignments of $f$.
Given the DNF representation of $f$ as input,
suggest a {\em polynomial time} algorithm (in $m$ and $n$) that outputs an
element in $S$ uniformly at random. \\
Hint: Think about generating a satisfying assignment of $f$ that satisfies $d_i$.
Generalize this to a sample from $\vee_i d_i$, maintaining the uniformity.
%% select a conjunction $i$ with probability $|d_i|/\sum_i |d_i|$
\item Use your procedure to give a polynomial time
algorithm to estimate the number of satisfying assignments of $f$.
Be explicit about the type of estimation you can get.
%% for $\epsilon, \delta$; If $Y$ is the estimator, with probability
%% at least $1-\delta$ P[|y-|S|/|R||]\>\epsilon] < \delta$
%% Using Chrnoff bounds (or other variations)
%% the number of samples required is
%% $> |S|/|R|1/\epsion^2 log{1/\delta}$ 1/\epsion^2
\item Can you write a polynomial time algorithm that outputs the {\em
exact} number of satisfying assignment of $f$? Explain why.
\end{enumerate}
%\extrapage
\end{enumerate}
\end{document}