\documentclass[fullpage,12pt]{article}
\usepackage{amssymb,latexsym,amsmath}
\usepackage{xspace}
\usepackage{euscript}
\usepackage{enumerate}
\usepackage{graphicx}
\usepackage{fullpage}
\newcommand{\brc}[1]{\left\{ {#1} \right\}}
\newcommand{\ceil}[1]{\left\lceil {#1} \right\rceil}
\newcommand{\hint}[1]{\noindent{\em (Hint: #1)}}
%\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]{}
\newcounter{prcnt}
\newcommand{\eat}[1]{}
\newenvironment{problem}{\stepcounter{prcnt}{\bigskip%
\hrule%
\hrule%
\hrule%
\bigskip\noindent{\underline{\bf {\large Problem \arabic{prcnt}}}} }\\}{}
%\newenvironment{solution} {\color{red} \small {\bf Solution:}}{\hfill{\hfill\rule{2mm}{2mm}}}
\newcommand{\pth}[2][\!]{#1\left({#2}\right)}
\def\EMPH#1{\textbf{\emph{\boldmath #1}}}
\makeatletter
\def\begin@lgo{\begin{minipage}{1in}\begin{tabbing}
\quad\=\qquad\=\qquad\=\qquad\=\qquad\=\qquad\=\qquad\=\qquad\=\qquad\=\qquad\=\qquad\=\qquad\=\qquad\=\kill}
\def\end@lgo{\end{tabbing}\end{minipage}}
\newenvironment{algorithm}
{\begin{tabular}{|l|}\hline\begin@lgo}
{\end@lgo\\\hline\end{tabular}}
\makeatother
\newenvironment{algo}
{\begin{center}\small\begin{algorithm}}
{\end{algorithm}\end{center}}
\def\Comment#1{\textsf{\textsl{$\langle\!\langle$#1\/$\rangle\!\rangle$}}}
\def\x#1{\textbf{\texttt{\boldmath #1}}}
\def\textul#1{\underline{\smash{#1}\vphantom{.}}}
\def\set#1{\{ #1 \}}
\def\fp#1{^{\underline{#1}}} % falling powers: $n\fp{d}$
\newcommand{\Hard}{}
\author{}
\date{}
\begin{document}
\hrule
\begin{center}
{\Large\sc Qualifying Examination}\\[1ex]
{\sc Theoretical Computer Science}\\[1ex]
\vspace*{0.5em}
{\sc Part I: Algorithms}\\
{\sc Monday, February 22, 2010}\\[1ex]
\end{center}
\hrule
\begin{problem}
\ProblemBy{Chandra}
Let $G=(V,E)$ be an undirected bipartite graph
with bipartition $A,B$.
\begin{itemize}
\item Prove that $G$ has $k$ edged-disjoint perfect matchings
if it is $k$-regular.
\item Give an example to show that having minimum degree $k$
is not sufficient for the existence of $k$ edge-disjoint
perfect matchings.
\item Let $|A| = |B| = n$. Show that $G$ has $k$ edge disjoint
perfect matchings if and only if for each $A'\subseteq A$ and
$B' \subseteq B$, there are at least $k(|A'|+|B'| - n)$ edges
between $A'$ and $B'$.
\end{itemize}
\end{problem}
\begin{problem}
\ProblemBy{Chandra} Consider the following random process that is
done in rounds. It starts with $m$ balls and $n$ bins. In each
round, each ball is placed independently into a bin chosen
uniformly at random from the $n$ bins. Any ball that lands in a
bin by itself is discarded forever. The process continues with the
remaining balls until there are no balls left. Show that the
expected number of rounds for the process to terminate is $O(\log
\log n)$ if we start with $m=n$.
\end{problem}
\begin{problem}
\ProblemBy{Jeff} \emph{Substring compression} is a compression
scheme reminiscent of Lempel-Ziv encoding. Let $T$ be a string of
length $n$ over some fixed alphabet $\Sigma$. To compress $T$, we
can replace the second (or later) occurrence of any substring of
$T$ with a pair of indices describing its first occurrence.
For example, in the string \x{HOCUSPOCUS}, we can replace the
second occurrence of the repeated substring \x{OCUS} with the pair
\x{$[2, 5]$} to get the compressed representation \x{HOCUSP$[2,
5]$}. More subtly, we can also compress overlapping
occurrences of the same substring; for example, \x{HA$[1, 16]$} is
a valid substring compression of the 18-character string
\x{HAHAHAHAHAHAHAHAHA}.
The \EMPH{length} of a compressed string is the number of raw
characters plus the number of indices. For example, the
compressed strings \x{HOCUSP$[2, 5]$} and \x{HA$[1, 16]$} have
lengths $8$ and $4$, respectively. (The brackets and commas are
syntactic sugar.)
Here is the algorithm to decompress a compressed string of length
$m$:
\begin{algo}
\textul{$\textsc{RSDecompress}(C[1\,..\,m])$:}\+ \\ $n\gets 1$
\\ $i\gets 1$
\\[0.5ex]
while $i\le m$\+ \\ if $C[i] \in \Sigma$\>\>\>\>
\Comment{character}\+ \\ $T[n] \gets C[i]$ \\ $n\gets n+1$ \\
$i\gets i+1$\-
\\[0.5ex]
else \>\>\>\> \Comment{substring indices}\+ \\ for $j\gets
C[i]$ to $C[i+1]$\+ \\ $T[n] \gets T[j]$ \\ $n\gets n+1$\- \\
$i\gets i+2$ \-\-
\\[0.5ex]
return $T[1\,..\,n]$
\end{algo}
\begin{enumerate}
\item Describe and analyze an efficient algorithm to compute
the minimum-cost substring compression of a given string.
\item Prove that every $n$-character string has a repeated
substring compression of length $O(n/\log n)$. (The hidden
constant may depend on the size of the alphabet $\Sigma$.)
\item Prove that for all $n$, there is an $n$-character string
$X_n$ such that \emph{every} repeated substring compression
of~$X_n$ has length $\Omega(n/\log n)$. (Again, the hidden
constant may depend on the size of the alphabet $\Sigma$.)
\Hard
\item Give a constructive proof for part (c). That is, for
each integer $n$, describe a string $X_n \in \set{0,1}^n$ such
that \emph{every} repeated substring compression of~$X_n$ has
length $\Omega(n/\log n)$.
\end{enumerate}
\end{problem}
\begin{problem}
\ProblemBy{Sariel} Consider a graph $G$ with minimum degree
$\delta$, and girth $2k+1$, where $k$ is some integer. The
\emph{girth} of a graph is the minimum length cycle in this graph.
\begin{enumerate}
\item Prove that $G$ has at least $(\delta - 1)^k$ vertices.
\item Prove that a graph with girth $\geq 2k+1$ has at most
$O\pth{n^{1+1/k}}$ edges.
\item A graph $H \subseteq G$ is a $t$-spanner for $G$, if for
any two vertices $u,v \in V(G)$ we have that $d_G(u,v) \le
d_H(u,v) \le t\cdot d_G(u,v)$, here $d_G(u,v)$ denotes the
(unweighted) shortest path between $u$ and $v$ in $G$.
Consider the algorithm that constructs the spanner by starting
from the empty graph $H =(V(G), \emptyset)$, and considering
the edges of $G$ in arbitrary order $e_1, \ldots, e_m$. In the
$i$th iteration, the algorithm computes the distance between
the two endpoints of $e_i$ in $G$ and in the current graph
$H$, and add $e_i$ to $H$ if $d_H(u,v) > t$.
It is not too hard to argue that $G$ is a $t$-spanner for
$H$. Prove that if $t>2$ is odd then $G$ has at most
$O\pth{n^{1+2/(t-1)}}$ edges.
\item Construct a bipartite graph with $2n$ vertices such that
it does not contain any cycle of length $4$, and it contains
at least (say) $n^{3/2} /8$ edges (but any constant instead of
$8$ is good enough). Prove that any such graph has at most
$O\pth{n^{3/2}}$ edges.
\hint{For the construction, use the probabilistic
method. (There is also a direct algebraic construction.)}
\end{enumerate}
\end{problem}
\end{document}