\documentclass[fullpage,12pt]{article}
\usepackage{amssymb}
\usepackage{xspace}
\usepackage{euscript}
\usepackage{enumerate}
\usepackage{graphicx}
\usepackage{fullpage}
\usepackage{amsmath}
\newcommand{\brc}[1]{\left\{ {#1} \right\}}
%\setlength{\textwidth}{5.5in}
% Put the following line the top of the file, if you want the
% solutions to appear:
% \def\solutionMode{TRUE}
%\usepackage{color}
%\usepackage{mcolors}
%\usepackage{framed}
%\usepackage{chngpage}
\newcommand{\sep}[1]{\,\left|\, {#1} \MakeBig\right.}
\newcommand{\MakeBig}{\rule[-.2cm]{0cm}{0.4cm}}
\newcommand{\ProblemBy}[1]{(By #1.)
\medskip
}
\newcounter{prcnt}
\newenvironment{problem}{\stepcounter{prcnt}{\bigskip%
\hrule%
\hrule%
\hrule%
\bigskip\noindent{\underline{\bf {\large Problem \arabic{prcnt}}}} }\\}{}
\newenvironment{proof}{{\em Proof:}}{\hfill{\hfill\rule{2mm}{2mm}}}
\newcommand{\pth}[2][\!]{#1\left({#2}\right)}
\renewcommand{\P}{\mathbf{P}}
\newcommand{\NP}{\mathbf{NP}}
\newcommand{\coNP}{\mathbf{coNP}}
\newcommand{\pparnp}{\P_{||}^\NP}
\newcommand{\pnplog}{\P^{\NP[\log]}}
\newcommand{\pnp}{\P^\NP}
\newcommand{\Arr}{\EuScript{S}}
\newcommand{\KMed}{$k$-medians range\xspace}
\newcommand{\points}[1]{{\bf [{#1} Points]}}
\newcommand{\poly}{\mathrm{poly}}
\newcommand{\Algorithm}[1]{{\texttt{\bf{#1}}}}
\newcommand{\IsCovered}{\Algorithm{is{}Covered}\xspace}
\newcommand{\cR}{\mathcal{R}}
\author{}
\date{}
\begin{document}
\hrule
\begin{center}
{\Large\sc Qualifying Examination}\\[1ex]
{\sc Theoretical Computer Science}\\[1ex]
{\sc Friday, September 18, 2009}\\[1ex]
%\vspace*{0.5in}
{\sc Part I: Algorithms}\\
{September 18, 2009}
\end{center}
\hrule
%
%\newpage}
{\bf Instructions:}
\begin{enumerate}
\item This is a closed book exam.
\item The exam is for 3 hours and has four problems of 25 points
each. Read all the problems carefully to see the order in which
you want to tackle them.
\item Write clearly and concisely. You may appeal to some standard
algorithms/facts from text books unless the problem explicitly
asks for a proof of that fact or the details of that algorithm.
\item If you cannot solve a problem, to get partial credit write
down your main idea/approach in a clear and concise way. For
example you can obtain a solution assuming a clearly stated lemma
that you believe should be true but cannot prove during the
exam. However, please do not write down a laundry list of half
baked ideas just to get partial credit.
\item Each question is worth 25 points.
\end{enumerate}
~\\~\\
May the s{c}h{w}art{z} be with you (and it will, see problem 3).
%\SolVer{\hrule\hrule\hrule\hrule\hrule\hrule}
%\FullVer{\newpage}
\medskip
\begin{problem}
\ProblemBy{Chandra}
Let $G=(V,E)$ be an undirected simple graph. Let $T \subseteq V$ be
a set of terminals; we refer to $V \setminus T$ as
non-terminals. For $u,v \in T$ we define the {\em element}
connectivity $\kappa'(u,v)$ as the maximum number of $u-v$ paths
that are disjoint in the non-terminals and edges of $G$; note that
the paths can share terminals. See figure for an example.
\begin{enumerate}[(A)]
\item Given $G=(V,E)$, $T \subseteq V$ and $u,v \in T$, describe
an efficient algorithm to compute $\kappa'(u,v)$.
\item Prove that for $u,v,w \in T$, $\kappa'(u,v) \ge
\min\{\kappa'(u,w), \kappa'(v,w)\}$.
\end{enumerate}
\begin{figure}[htb]
\centering
\includegraphics[width=3in]{figs/elem-fig}
\caption{In the graph above $\kappa'(u,v) = 3$ and $\kappa'(u,w) =
\kappa'(v,w) = 2$.}
\label{fig:elem}
\end{figure}
\end{problem}
\begin{problem}
\ProblemBy{Chandra}
\begin{enumerate}[(A)]
\item For a $n \times n$ matrix $M$, its \emph{determinant} is
the quantity
\[
\det(M ) = \sum_{\sigma \in S_n} \mathrm{sgn}(\sigma)
\prod_{i=1}^n M_{i,\sigma(i)},
\]
where $S_n$ is the set of all permutations of $\brc{1, \ldots,
n}$, and $\mathrm{sgn}(\sigma)$ is $+1$ if $\sigma$ is
even and $-1$ otherwise.\footnote{A permutation is even if it
can be converted in a even number of switches to the
identity permutation.}
Let $M$ be such a matrix of integer numbers, that can be
represented using $U$ bits. Prove that the number of bits
required to represent $\det(M)$ is bounded by a polynomial in
$U$.
\item Let $M$ be a $n \times n$ matrix of \emph{rational}
numbers, that can be represented using $U$ bits. Prove that
the number of bits required to represent $\det(M)$ is bounded
by a polynomial in $U$. (You can assume (A) in proving this
part.)
\item The Linear-Programming problem is to solve a system
of the form
\begin{align*}
\max \;\;\; & c^tx, \\
& Ax \le b,
\end{align*}
where $A$ is a $m \times n$ rational matrix and $c$ and $b$ are $n
\times 1$ rational vectors.
In the decision version we are given an additional rational
number $K$ and the given instance $A,c,b, K$ is a YES instance
if there is a real-valued $n \times 1$ vector $x^*$ such that
$c^t x^* \ge K$ and $A x^* \le b$. It is NO instance otherwise
(either if there is no feasible solution for $Ax \le b$ or if
the maximum value is strictly less than $K$).
Prove that the decision version of Linear-Programming is in
NP. Claim any facts from linear algebra that you find useful
or need (in particular, you can assume (A) and (B) in your
solution). You cannot use the fact that there is a
polynomial-time algorithm for Linear-Programming. Note also
that numerical operations on integers require time that
depends on the length of their binary representation (for
example, adding two integers with $m$ and $n$ bits takes $O(m
+ n)$ time).
\end{enumerate}
\end{problem}
\begin{problem}
\ProblemBy{Sariel}
\begin{enumerate}[(A)]
\item \points{20}
Prove, \emph{by induction}, the Cauchy-Schwarz
inequality, that is, for any real numbers $x_1, x_2, \ldots,
x_n$, $y_1, y_2, \ldots, y_n$, we have that
\[
\sum_{i=1}^n x_i y_i \leq \sqrt{ \sum_{i=1}^n x_i^2 }
\sqrt{ \sum_{i=1}^n y_i^2 }.
\]
(Note, that you need to provide here a carefully written
formal proof.)
\item \points{5} Let $G=(V,E)$ be a graph over $n$ vertices,
with the property that $\sum_{v \in V} \binom{d(v)}{2} \leq
\binom{n}{2}$. Prove that $|E| =O(n^{3/2})$.
\end{enumerate}
\end{problem}
\newcommand{\Hint}[1]{(\textbf{Hint:} #1)}
\begin{problem}
\ProblemBy{Jeff.}
Let $A[1\,..\,n]$ be a fixed array of integers between $1$ and
$n$. For any other array $I[1\,..\,k]$ of integers between $1$ and
$n$, let $A(I)$ denote the $k$-element array whose $j${t}h entry is
$A[I[j]]$, for all $j$.
Recall that an array $I[1\,..\,k]$ is \emph{increasing} if $i