\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}
% for \sout
\usepackage[normalem]{ulem}
% 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 2017}
\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 1, 2017.\\
Due: submit PDF file containing your solutions on Canvas by 11:59pm on May 8, 2017.
\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. \textbf{Do not
submit code as a solution. Use pseudo-code in the style of the
slides, the textbook, and the official homework solutions.}
\item If you prove that a problem is \npc, remember to state the size of
the certificate, 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] (15 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{$B$}{$A$}, then $A \in \calp$.
% \solution{
%
% }
\item In a directed graph, every edge has a positive integer weight that is bounded by the quantity $w$. The graph has $n$ nodes and $m$ edges. We can compute the shortest path between any two nodes in this graph in $O(w(n+m))$ time.
% \solution{
%
% }
\item In a directed graph, let $d(x,y)$ denote the length of the shortest path between nodes $x$ and $y$. If $e = (u,v)$ is an edge on a shortest path from $s$ to
$t$, then $d(s, t) = d(s, u) + l_e + d(v, t)$, where $l_e$ is the length of the edge $e$.
% \solution{
%
% }
\item An algorithm takes an input of size $n$, performs some
computation in $O(n)$ time, and then recurses on one sub-problem of size
$n/2$ to compute the solution. The running time of this algorithm is
$O(n)$.
% \solution{
%
% }
\item If $P = NP$ and problem $X$ is \npc, then there is a polynomial time algorithm to solve $X$.
\item \_\_\_\_\_\_\_\_ \_\_\_\_\_\_ is a real-life person who appears as an unseen character in the first Harry Potter book and movie.
% \solution{
%
% }
\end{enumerate}
\item[Problem 2] (20 points) Gasp! Your best friend Will Byers is trapped in The Upside Down yet again!! You have to rescue him from the Demogorgon!!! Fortunately, due to his repeated forays into The Upside Down in previous \sout{seasons} years, you have a very good map of this dimension. Will has figured out several hiding spots where the Demogorgon cannot see him; he is currently secreted in one of these spots. Moreover, due to Eleven's (Yes, she is alive!) deep sensory perception, you have very good estimates of how safe it is to travel from one hiding spot to another without being devoured by the Demogorgon. Finally, you also know the locations of several interdimensional portals between our world and The Upside Down.
Using your CS 4104 prowess, you represent The Upside Down as an undirected graph $G = (V,E)$, where each node in $V$ is either a hiding place or an interdimensional portal. Every edge $(u,v)$ connects two nodes in $V$. The weight $w_{u,v}$ of this edge is the probability that as you go from $u$ to $v$ (or $v$ to $u$, since the edge is undirected), the Demogorgon will not devour you. Clearly, this weight is between $0$ and $1$ since it is a probability. The weight of a path in $G$ is the product of the weights of its edges. This weight denotes the probability that the Demogorgon will not eat you as you traverse this path. With this set up, you formulate the \texttt{OperationSaveWillByers} problem:
\begin{quote}
Given an undirected graph $G=(V,E)$, where every edge $(u,v)$ is associated with a weight $w_{u,v}$ that lies between $0$ and $1$, a subset $S \subset V$ of nodes, a node $t$, and a parameter $r$ that also lies between $0$ and $1$, is there any node in $S$ such that the weight of the path from this node to $t$ is at least $r$?
\end{quote}
In this dimension (alas, we are back to the real world), you have one of two options:
\begin{enumerate}
\item Find a problem $X$ that is NP-complete and prove that \reducible{X}{\texttt{OperationSaveWillByers}}, thereby proving that \texttt{OperationSaveWillByers} is also NP-complete.
\item Find a problem $X$ that is in \calp and prove that \reducible{\texttt{OperationSaveWillByers}}{X}, thereby proving that \texttt{OperationSaveWillByers} can also be solved in polynomial time. In this case, state the running time of your algorithm.
\end{enumerate}
\emph{Note:} You must use only the strategy described in one of these options. The Demogorgon will devour all your points if you deviate from these instructions.
% \solution{
%
% }
\item[Problem 3] (10 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 backward edges $(u, v)$ in $G_f$, 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_{\substack{(u, v) \text{ is a backward edge in $G_f$,} \\ u \in B^*, v \in A^*}} rc(e)?$$ Provide a
brief explanation.
% \solution{
%
% }
\item[Problem 4] (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+1$ 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 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 n$, 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] (15 points) In a directed graph, let $P$ be the second shortest
path between two nodes $s$ and $t$ in the graph. To be precise, the
length of $P$ 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 notation
$P(s,v)$ to denote the sub-path of $P$ from $s$ to $v$ and $P(v,
t)$ to denote the sub-path of $P$ from $v$ to $t$.
\begin{enumerate}[(a)]
\item (10 points) Prove that at least one of the following statements is true: (a) $P(s,v)$ is the shortest path from $s$
to $v$ or (b) $P(v,t)$ is the shortest path from $v$ to $t$.
\item (5 points) Suppose that $v$ is a node such that $P(v,t)$ is
the shortest path from $v$ to $t$. What can you say about
$P(s,v)$? I just want a single sentence answer.
\end{enumerate}
\end{description}
\end{document}
%%% Local Variables:
%%% mode: latex
%%% TeX-master: t
%%% End: