\documentclass{article}
\usepackage{geometry}
\geometry{verbose,letterpaper,tmargin=1in,bmargin=1in,lmargin=1in,rmargin=1in}
\usepackage{fancyhdr,enumerate,xspace,amsmath,graphicx,algorithmic,algorithm,enumerate}
\pagestyle{fancy}
% macros useful for handouts and homeworks.
\newcommand{\setcourse}[1]{\newcommand{\course}{#1\xspace}}
\newcommand{\setsem}[1]{\newcommand{\sem}{#1\xspace}}
\newcommand{\sethwnum}[1]{\newcommand{\hwnum}{#1\xspace}}
\setcourse{CS 4104}
\setsem{Spring 2014}
\chead{\course (\sem): Final Examination}
\newcommand{\solution}[1]{\textbf{Solution:} #1}
\newcommand{\cut}[1]{\ensuremath{\mathnormal{}{cut}(#1)}}
\newcommand{\calg}{\ensuremath{{\cal G}}\xspace}
\newcommand{\calo}{\ensuremath{{\cal O}}\xspace}
\newcommand{\opt}[1]{\ensuremath{\text{OPT}(#1)}}
\newcommand{\length}[1]{\ensuremath{\overline{#1}}}
\newcommand{\calnp}{\ensuremath{{\cal NP}}\xspace}
\newcommand{\calp}{\ensuremath{{\cal P}}\xspace}
\newcommand{\npc}{\calnp-Complete\xspace}
\newcommand{\reducible}[2]{\ensuremath{\textsc{#1} \leq_P \textsc{#2}}}
% macro for a set. extra pair of braces inside \ensuremath to ensure
% the set is typseset in one line.
\newcommand{\set}[1]{\ensuremath{{\{#1\}}}}
\begin{document}
\title{\vspace{-0.5in}\textbf{Final Examination}}
\author{\course (\sem)}
\date{}
\maketitle
\begin{center}
Assigned: May 5, 2014.\\
Due: on Scholar by 5pm on May 13, 2014.
\end{center}
\begin{center}
\begin{tabular}[c]{rr}
Name: & \underline{\phantom{--------------------------------}}\\
\\
9-digit PID: & \underline{\phantom{--------------------------------}}
\end{tabular}
\end{center}
\section*{Instructions}
\label{sec:instructions}
\begin{enumerate}
\item \textbf{You must work on your own for this examination, i.e., you are
not allowed to have a partner.}
\item For every algorithm you describe, prove its correctness, and state
and prove the running time of the algorithm. I am looking for clear
descriptions of algorithms and for the most efficient algorithms and
analysis that you can come up with. I am not specifying the desired
running time for each algorithm. I will give partial credit to
non-optimal algorithms, as long as they are correct.
\item If you prove that a problem is \npc, remember to state how long
the certificate is, how long it takes to check that the certificate
is correct, and what the running time of the transformation is. All
you need to show is that the transformation can be performed in
polynomial time. Your transformation need not be the most efficient
possible.
\item You may consult the textbook, your notes, or the course web site
to solve the problems in the examination. Of course, the TAs and I are
available to answer your questions. You \textbf{may not} work on the
exam with anyone else, ask anyone questions, or consult other
textbooks or sites on the Web for answers. \textbf{Do not use}
concepts from chapters in the textbook that we have not covered, i.e.,
Chapters 12 and 13.
\item You must prepare your solutions digitally, i.e., do not hand-write
your solutions.
\item I prefer that you use \LaTeX\ to prepare your solutions. However,
I will not penalise you if you use a different system. To use \LaTeX,
you may find it convenient to download the \LaTeX\ source file for
this document from the link on the course web site. At the end of each
problem are three commented lines that look like this:
\begin{verbatim}
% \solution{
%
% }
\end{verbatim}
You can uncomment these lines and type in your solution within the curly
braces.
\end{enumerate}
Good luck!
\newpage
\begin{description}
\item[Problem 1] (10 points) Let us start with some quickies. For each
statement below, say whether it is true or false or fill in the
blank. You do not need to provide a rationale for your solution.
\begin{enumerate}
\item If $A$ and $B$ are problems such that $B \in \calp$ and
\reducible{A}{B}, then $A \in \calp$.
% \solution{
%
% }
\item The costliest edge in a directed graph can never be an edge in a
minimum spanning tree of the graph.
% \solution{
%
% }
\item An algorithm takes an input of size $n$, performs some
computation in $O(n)$ time, and then recurses on an input of size
$n/2$ to compute the solution. The running time of this algorithm is
$O(n)$.
% \solution{
%
% }
\item \_\_\_\_\_\_'\_ celebrates its 20-year anniversary on May 7,
2014. \emph{Hint:} A Blacksburg insitution.
% \solution{
%
% }
\item In the original comics, Spiderman (or The \emph{Amazing}
Spiderman, as he is called these days) got his powers after being
bitten by a \_\_\_\_\_\_\_\_\_\_\_ spider.
% \solution{
%
% }
\end{enumerate}
\item[Problem 2] (15 points) Consider the residual graph $G_{f}$ when
the Ford-Fulkerson algorithm terminates; we have used the notation
$\nu(f)$ to denote the value of this flow. Let $rc(e)$ denote the
residual capacity of an edge $e$ in $G_f$. Let $A^*$ be the set of all
nodes reachable from $s$ in $G_f$ (by a directed path of one or more
edges) and $B^* = V - A^*$. Consider the set of edges $(u, v)$ where
$u$ is a node in $B^*$ and $v$ is a node in $A^*$. What is the total
residual capacity of these edges, i.e., what is the value
of $$\sum_{(u, v) \in G_f, u \in B^*, v \in A*} rc(e)?$$ Provide a
brief explanation.
% \solution{
%
% }
\item[Problem 3] (20 points) The flag of a certain populous country
contains a symbol called the ``Ashoka Chakra'' (see the image
below). This symbol has a central hub and 24 spokes. Naturally, this
reminds us of a graph with 25 nodes and 48 edges, of which 24 nodes
are connected by a cycle, and the 25th node is connected to each of
the other 24 nodes. A \emph{generalised $k$-chakra} is a graph with
$k+1$ nodes and $2k$ edges such that $k$ nodes lie on a cycle and the
$k+1$st node is connected to each of the other $k$ nodes. Given an
undirected graph $G$ and an integer $k$, prove that the problem of
determining if $G$ contains a generalised $k$-chakra as a subgraph is
\npc. (We say that a graph $H$ is a \emph{subgraph} of a graph $G$ if
every node in $H$ is also a node in $G$ and every edge in $H$ is also
an edge in $G$.)
\centerline{\includegraphics[width=0.4\textwidth]{wikipedia-Ashoka-Chakra}}
I will get you started on the solution. Proving that $k$-chakra is in
\calnp is easy. A certificate is just a candidate $k$-chakra. The
certifier checks that this chakra contains $k+1$ nodes and $2k$ nodes
in the right configuration. The certificate takes $O(k)$ time to run.
Let us move on to proving that some \npc problem is reducible to the
$k$-chakra problem. Suppose $G$ has $n$ nodes. Let us consider the
special case that $k = n$. An $n$-chakra looks suspiciously like a
Hamiltonian cycle, except that the chakra has more edges. Let us
reduce Hamiltonian cycle in undirected graphs (which we know to be
\npc) to the $k$-chakra problem. Suppose $H$ is an undirected graph
that is an input to the Hamiltonian cycle problem. We want to convert
it to a graph $G$ that will be input to the $k$-chakra problem such
that $H$ contains a Hamiltonian cycle iff $G$ contains a $n$-chakra.
To complete the reduction, answer the following three questions:
\begin{enumerate}[(a)]
\item (5 points) Describe how you will convert an arbitrary undirected graph $H$
that is input to the Hamiltonian cycle problem into an
undirected graph $G$ that is an input for the chakra problem.
\item (5 points) If $H$ contains a Hamiltonian cycle, prove that $G$ contains
a $n$-chakra.
\item (10 points) If $G$ contains a $n$-chakra, prove that $H$
contains a Hamiltonian cycle. \emph{Note:} there is a subtlety here
that you have to be careful about.
\end{enumerate}
% \solution{
%
% }
\item[Problem 4] (10 points) Prove the following statement. In a flow
network where the maximum flow has value $f$, there must exist a path
from $s$-$t$ with capacity at least $f/m$, where $m$ is the number of
edges in the graph. By the \emph{capacity} of an $s$-$t$ path, we mean
the smallest capacity of an edge in that path. \emph{Hint:} Use a
proof by contradiction. Suppose every $s$-$t$ path has at least one
edge with capacity less than $f/m$. What can you say about the set of all these
edges?
% \solution{
%
% }
\item[Problem 5] (20 points) After graduation, you start a job at a
company that is building a space elevator! People travelling to space in
the elevator need to eat. Therefore, your company is planning to open a
series of restaurants along the elevator. There are $n$ potential
locations for these restaurants. Starting from the beginning of the
space elevator, these locations are, in miles and in increasing order,
$m_1, m_2, m_3, \ldots m_{n-1}, m_n$. Your company wants to minimize the
costs of constructing and maintaining these restaurants as well as
maximising its profits. It devises the following rules:
\begin{enumerate}[(i)]
\item At each location, it can open at most one restaurant.
\item For each $1 \leq i \leq m$, the expected profit from opening a
restaurant at location $i$ is $p_i > 0$.
\item Any two restaurants your company builds should be at least $k$ miles apart, where $k$ is a positive integer.
\end{enumerate}
Since the company hired you because you have taken CS 4104, it asks you
to devise an efficient algorithm to decide where to build the
restaurants so as to compute the maximum total
profit subject to the given rules. Use your advanced knowledge of
algorithms to impress your bosses and peers and collect a hefty
Christmas bonus!
% \solution{
%
% }
\item[Problem 6] (10 points) The Department of Computer Science at
Virginia Tech needs to teach a set $C$ of $n$ courses in Fall
2014. There are $m$ professors in the department. Each course can be
taught by exactly two professors. A single professor can teach
anywhere from $1$ to all $n$ courses. By ``can teach'', I mean that
the professor has the ability and expertise to teach the course. The
Department has a budget to pay at most $k$ professors in Fall 2014,
where $k$ is an integer between $1$ and $m$. It seeks to
determine if there are at most $k$ professors who can teach all $n$
courses among themselves. Prove that this problem is
\npc. \emph{Hint:} This problem is easier than it looks.
% \solution{
%
% }
\item[Problem 7] (15 points) In a directed graph, let $\pi$ be the second shortest
path between two nodes $s$ and $t$ in the graph. To be precise, the
length of $\pi$ is larger than the the shortest path length from $s$
to $t$ but less than or equal to the length of all other $s$-$t$
paths. Let $v$ be a node on this path. We will use the
$\pi(s,v)$ to denote the sub-path of $\pi$ from $s$ to $v$ and $\pi(v,
t)$ to denote the sub-path of $\pi$ from $v$ to $t$.
\begin{enumerate}[(a)]
\item (10 points) Prove that either $\pi(s,v)$ is the shortest path from $s$
to $v$ or $\pi(v,t)$ is the shortest path from $v$ to $t$.
\item (5 points) Suppose that $v$ is a node such that $\pi(v,t)$ is
the shortest path from $v$ to $t$. What can you say about
$\pi(s,v)$? I just want a single sentence answer.
\end{enumerate}
\end{description}
\end{document}
%%% Local Variables:
%%% mode: latex
%%% TeX-master: t
%%% End: