\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: 
