\documentclass{article}
\usepackage{geometry}
\geometry{verbose,letterpaper,tmargin=1in,bmargin=1in,lmargin=1in,rmargin=1in}
\usepackage{fancyhdr,enumerate,xspace,amsmath,graphicx}
\pagestyle{fancy}
\chead{CS 5114 (Spring 2008): Final Examination}
%\usepackage{cs5114}
\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{\npc}{\calnp-Complete\xspace}
% 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{CS 5114 (Spring 2008)}
\date{}
\maketitle
\begin{center}
Assigned: April 30, 2008.\\
Due: at Torgerson 2160B by 5pm on May 7, 2008.\\ \textbf{DO NOT EMAIL
YOUR SOLUTIONS TO ME!}
\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 For every algorithm you describe, prove its correctness and
analyse its running time and space used. I am looking for clear
descriptions of algorithms and for the most efficient algorithms you
can come up with.
\item If you prove that a problem is \npc, remember to state how long
the proof, how long it takes to check the proof, and what the running
time of the transformation is.
\item You may consult the textbook, your notes, or the course web site
to solve the problems in the examination. 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.
\item You must prepare your solutions digitally and submit a hard-copy.
\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.
\item Do not forget to staple the hard copy you hand in.
\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.
\begin{enumerate}
\item A graph is 2-colourable if and only if it has no cycles of odd
length.
% \solution{
%
% }
\item The harmonic function $H(n) = \Theta(\log n)$.
% \solution{
%
% }
\item In a directed graph, $G = (V, E)$ let $\pi(u, v)$ denote the
length of the shortest path between nodes $u$ and $v$. Then, for any
three nodes $u, v, w$, $\pi(u, v) + \pi(v, w) \geq \pi(u, w)$.
% \solution{
%
% }
\item In class, we reduced \textsc{Independent Set} to \textsc{Vertex
Cover}. Suppose we have an algorithm that runs in polynomial time
and computes a vertex cover that has size at most twice the smallest
vertex cover. Then this algorithm yields an independent set of size
at least half the largest independent set.
% \solution{
%
% }
\item Superman gets his powers from the rays of our sun.
% \solution{
%
% }
\end{enumerate}
\item[Problem 2] (30 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 is \npc.
\centerline{\includegraphics[width=0.4\textwidth]{wikipedia-Ashoka-Chakra}}
% \solution{
%
% }
\item[Problem 3] (30 points) You are given an undirected graph $G = (V,
E)$. Each vertex $v \in V$ has a label $l_v \in \set{-1, 0,
1}$. Each edge $e \in E$ has a weight $w_e > 0$. Consider the set
$V_0$ of nodes in $V$ whose label is $0$. Your goal is to change the
label of every node in $V_0$ to $1$ or $-1$, while taking the
edge structure of $G$ into account. For example, if a node $v$ in $V_0$
has many more neighbours with label $1$ than $-1$, you would like to
change $v$'s label to $1$. Therefore, you decide to maximise the
\emph{consistency} of $G$
$$c(G) = \sum_{e = (u, v) \in E} w_{e}l_ul_v.$$
Either devise a polynomial time algorithm to maximise $c(G)$ or prove
that the decision version of the problem (i.e., given a parameter
$\kappa$, goes $G$ have a labelling of the nodes in $V_0$ such that
$c(G) \geq \kappa$) is \npc.
% \solution{
%
% }
\item[Problem 4] (30 points) A \emph{Hamiltonian path} in an undirected
graph is a simple path that visits every vertex exactly once. Deciding
whether a graph has a Hamiltonian path is \npc. Some special graphs
(e.g., complete graphs) have simple solutions to the problem. Let $G$
be an undirected graph with nodes $V = \set{v_1, v_2, \ldots v_n}, n
\geq 4$. Every node in $V$ has an edge connecting it to $n - 2$ other
nodes in $V$. You are given the node set $V$ but not the edges of
$G$. The following two functions $S$ and $R$ return information about
the edges of $G$:
\begin{description}
\item[$S$] takes two vertices in $V$ as argument and returns
\texttt{true} if the two vertices are connected by an edge and
\texttt{false} otherwise.
\item[$R$] takes one vertex $v$ in $V$ as argument and returns the
unique node in $V$ (other than $v$, of course) that is not connected to $v$.
\end{description}
You may assume that each functions runs in $O(1)$ time. You have two
tasks.
\begin{enumerate}
\item Prove that $G$ has a Hamiltonian path.
\item Compute the Hamiltonian path in $G$ as a sequence of vertices by
using one (but not both) of the following options:
\begin{description}
\item[Option 1] You are allowed to call $S$ but not $R$. Your
algorithm must use $O(1)$ space, $O(n)$ time and at most $n -
1$ calls to $S$.
\item[Option 2] You are allowed to call $R$ but not $S$. Your
algorithm must use $O(n)$ space, $O(n)$ time and at most $\lceil n/4
\rceil$ calls to $R$.
\end{description}
\end{enumerate}
% \solution{
%
% }
\end{description}
\end{document}
%%% Local Variables:
%%% mode: latex
%%% TeX-master: t
%%% End: