%--------------------------------------------------------
% questions.tex
%
%--------------------------------------------------------
% \newcommand{\remove}[1]{}
\documentclass[12pt]{article}
\usepackage{fullpage}
\usepackage{graphicx}
\usepackage{theorem}
\usepackage{framed}
\usepackage{color}
%\usepackage{mcolors}
\usepackage{chngpage}
\usepackage{enumerate}
\usepackage{xspace}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{xspace}
\usepackage{fullpage}
\renewcommand{\th}{th\xspace}
\newlength{\savedparindentx}
\definecolor{shadecolor}{gray}{0.96}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{problem}[theorem]{Problem}
\providecommand{\SaveIndent}{\setlength{\savedparindentx}{\parindent}}
\providecommand{\RestoreIndent}{\setlength{\parindent}{\savedparindentx}}
\newcommand{\Solution}[1]{\medskip \noindent\textbf{\Large{Solution:}}\\
\noindent\begin{minipage}{0.99\linewidth}
\begin{shaded}%
\RestoreIndent %
#1
\end{shaded}
\end{minipage}
}
%\documentclass[11pt]{article}
%\usepackage{jeffe,handout,graphicx,hyperref}
%\usepackage[utf8]{inputenc}
%\usepackage{microtype}
%\usepackage{colortbl,arydshln} % color and dashed lines in arrays
%\usepackage[charter]{mathdesign}
%\usepackage[mathcal]{euscript}
%\usepackage[all]{xy}
\newcommand{\cardin}[1]{\left| {#1} \right|}
\newcommand{\poly}{\ensuremath{\text{poly}}\xspace}
\newcommand{\class}[1]{\ensuremath{\text{\bf{#1}}}\xspace}
\newcommand{\NC}[1]{\ensuremath{\class{NC}^0}\xspace}
\newcommand{\conjNC}[1]{\ensuremath{\class{NC}^0_{\text{\sc and}}}\xspace}
\newcommand{\NP}{\class{NP}}
\renewcommand{\P}{\class{P}}
\newcommand{\sharpR}{{\ensuremath{\sharp R}}\xspace}
\renewcommand{\H}{\ensuremath{{\mathcal H}}\xspace}
%\newcommand{\problem}[1]{\ensuremath{\text{\sf #1}}\xspace}
\newcommand{\SAT}{\textsc{SAT}}
\newcommand{\QProblem}[4]{%
\section{#1}
% \textbf{Problem by: } #2
#3
% \Solution{#4}
}
\newcommand{\QProblemNS}[3]{%
\section{#1}
% (\textbf{Problem by: } #2)
#3
\bigskip
\bigskip
}
\begin{document}
\title{Qual, Spring 2011\\
Algorithms}
\date{\today}
%\def\sfdefault{fvs}
%\def\ttdefault{fvm}
%\urlstyle{same}
% ======================================================================
%\begin{document}
%\headers{Theory Qual Problems}{}{Spring 2011}
\maketitle
\noindent Duration: 3 hours\\
Number of problems: 5
\bigskip
\bigskip
\QProblemNS{Weighted edge cover}{Sariel}{ Let $G =(V,E)$ be a
weighted undirected graph with $n$ vertices. A \emph{minimum weight
edge cover} is a subset of the edges of $G$, of minimum weight,
such that every vertex is covered by some edge in the set.
\begin{enumerate}[(A)]
\item Let $P$ be a set of $n$ points in the plane, and consider
the complete graph on $P$, where the weight of an edge is the
Euclidean distance between its endpoints. Prove that the
minimum weight edge cover of this graph form a planar graph.
\item Let $R$ and $B$ be sets of real numbers on the real line,
and consider the complete bipartite graph defined on these two
sets, where the weight of the edge $rb$, for $r \in R$ and $b
\in B$, is $\cardin{r-b}$. Provide a dynamic programming
algorithm that computes the minimum weight edge cover of this
graph in polynomial time. What is the running time of your
algorithm as a function of $n = \cardin{R} + \cardin{B}$?
\end{enumerate}%
}{}
% ----------------------------------------------------------------------
% Jeff
\QProblemNS{Rooted tree}{Jeff}{
Suppose your are given a rooted tree $T$, where every edge
$e$ has a non-negative \emph{length} $\ell(e)$. Your goal is to
assign a stretched length $s\ell(e) \ge \ell(e)$ to every edge $e$
in $T$, so that every root-to-leaf path in~$T$ has the same total
stretched length, and the stretched lengths are in some sense
optimal.
\begin{enumerate}[(A)]\itemsep2ex
\item Describe and analyze an algorithm to minimize the total
stretched length $\sum_e s\ell(e)$.
\item Now suppose every edge also has a \emph{value} $\$(e)$,
which may be positive, negative, or zero; the value of an edge
is equal to the cost of increasing its length by $1$.
Describe and analyze an algorithm to minimize the total
stretch \emph{cost} $\sum_e \$(e)\cdot s\ell(e)$.
\end{enumerate}
Faster algorithms are worth more points.
}{}
% Sheldon Jacobson
% Question 3 (1 Hour)
\QProblemNS{No such thing as a free lunch}{Sheldon}{%
Suppose that a group of $N$ people (where $N > 50$) are waiting in
line to eat at a restaurant. Suppose that the first person gets
to eat for free. The second person gets to eat for free if they
have the same birthday as the first person. Then everyone else
must pay to eat. The third person gets to eat for free if the
second person did not get to eat for free AND they have the same
birthday as either the first or the second person. Then everyone
else must pay to eat. The ``eat free'' rule proceeds in the
obvious manner. Determine the probability that the $n$\th person
gets to eat for free. Determine the value for $n$ such that their
probability of eating for free is larger than anyone else’s such
probability
}{}
%Chandra
\QProblemNS{Matchings from a black-box}{Chandra}{%
Let $G=(V,E)$ be an undirected graph and let $w : E\rightarrow
\mathbb{R}_+$ be a non-negative weight function on the edges.
Assume you have a black-box algorithm to compute the minimum-weight
perfect matching in a given graph (the algorithm works even when
weights are negative). Show how to use that algorithm to find a
maximum weight matching of a given size $k$ if one exists (your
algorithm should report that there is no matching of size $k$ if
that is the case).
}{}
\newpage
\QProblem{Attack of the Brussels Sprouts}{Lenny}{%
The game \emph{Brussels Sprouts} (a variant of \emph{Sprouts}),
starts with $n$ crosses drawn in the plane. Each cross is a spot
with four free ends. Each move involves joining two distinct free
ends with a curve (not crossing any existing curve) and then
putting a short stroke across the line to create two new free ends.
The game ends when no two free ends can be joined without crossing
an existing curve.\footnote{In the original game, two players
alternate in who is drawing the curves, and the last one to draw
the curve is the winner.}
So each move removes two free ends and introduces two more.
Despite this, the game is finite. To see that, consider the
following example:
\noindent\fbox{\includegraphics[page=1]{figs/sprouts}}
%
$\implies$ %
\fbox{\includegraphics[page=2]{figs/sprouts}}
%
$\implies$ %
\fbox{\includegraphics[page=3]{figs/sprouts}}
%
$\implies$ %
\bigskip
\fbox{\includegraphics[page=4]{figs/sprouts}}
%
$\implies$ %
\fbox{\includegraphics[page=5]{figs/sprouts}}
%
$\implies$ %
\fbox{\includegraphics[page=6]{figs/sprouts}}
$\implies$ %
\fbox{\includegraphics[page=7]{figs/sprouts}}
$\implies$ %
\fbox{\includegraphics[page=8]{figs/sprouts}}
$\implies$ %
\fbox{\includegraphics[page=9]{figs/sprouts}}
Provide a precise bound on the number of steps in the game, as a
function of $n$ (the number of crosses). Prove the bound you
provide. }%
{}
\end{document}
%--------------------------------------------------------
%
% questions.tex - end of file
%--------------------------------------------------------