\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 4104 (Fall 2009): 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 4104 (Fall 2009)}
\date{}
\maketitle

\begin{center}
  Assigned: December 2, 2009.\\
  Due: at Torgerson 2160B by 5pm on December 14, 2009.\\  \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 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. 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, except for the last one, say whether it is true or
  false. You do not need to provide a rationale for your solution.

  \begin{enumerate}

  \item For the problem of computing the largest matching in a bipartite
    graph, the Ford-Fulkerson algorithm runs asymptotically faster than
    the scaling algorithm.
    % \solution{
    %   
    % }

  \item $\sum_{i=1}^{n} i = \Theta(n^2)$.

%      \solution{
%
%      }


  \item In a directed graph, $G = (V, E)$ let $\pi(u, v)$ denote the
    length of the shortest path that starts at $u$ and ends at $v$. If
    there is no such path, you can assume that $\pi(u, v) =
    \infty$. Since $G$ is directed, $\pi(u, v) \not= \pi(v, u)$, in
    general. Then, for any three nodes $u, v, w \in V$, $\pi(u, v) + \pi(v, w)
    \geq \pi(u, w)$.

    % \solution{
    %   
    % }

  \item Suppose we have an algorithm that when given a graph $G$ with
    $n$ nodes and an integer $k$, checks if $G$ has a vertex cover of
    size $k$ or less in $O(2^kn)$ time. Note that this time is
    polynomial in $n$ (but exponential in $k$). Since we reduced
    \textsc{Independent Set} to \textsc{Vertex Cover} in class, we have
    an algorithm that can check if a graph $G$ has an independent size
    of size at least $l$ (for some integer $l > 0$) in time polynomial
    in $n$.

    % \solution{
    %   
    % }
    

  \item Estimate the probability that Homer Simpson will resolve the
    ${\cal P} = \cal{NP}$ conundrum in the series finale of the
    \emph{The Simpsons}. Please provide a probability. Do not answer
    ``True'' or ``False''.

%     \solution{
%
%     }

  \end{enumerate}

\item[Problem 2] (30 points) Many object-oriented programming languages
  implement a class for manipulating strings. A primitive operation
  supported by such languages is to split a string into two pieces. This
  operation usually involves copying the original string. Hence, a split
  operation takes $n$ units of time for a string of length $n$,
  \emph{regardless of the location of the split}. However, if we want to
  split a string into many pieces, the order in which we make the breaks
  can affect the total running time of all the splits.

  For example, suppose we want to split a 20-character string at
  positions 3 and 8.  If we make the first cut at position 3, the cost
  of the first cut is the length of the string, which is 20. Now the cut
  at position 8 falls within the second string, whose length is 17, so
  the cost of the second cut is 17. Therefore, the total cost is 20 + 17
  = 37.  Instead, if we make the first cut at position 8, the cost of
  this cut is still 20. However, the second cut at position 3 falls
  within the first string, which has length 8. Therefore, the cost of
  the second cut is 8, implying a total cost of 20 + 8 = 28. Since $28
  < 37$, it is better to make the first cut at position 8 and the
  second cut at position 3. However, if we want to split the same string
  at positions 3 and 18, you can convince yourself that the smallest
  total cost is achieved by first making the cut at position 3 and then
  at position 18.

  Design an algorithm that, given the locations of $m$ cuts in a string
  of length $n$, finds the minimum cost of breaking the string into $m +
  1$ pieces at the given locations. Your algorithm must minimise the
  total cost of breaking the string at all the cut locations. You can
  assume that the cut locations are distinct and that no cut is at
  position 1 or at position $n$. \emph{Hint:} A greedy approach will not
  work. Neither will divide and conquer.

% \solution{
%
% }


\item[Problem 3] (40 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$.  A \emph{labelling} of $V_0$ is an
  assignment of $1$ or $-1$ as the label of every node in $V_0$.  Note
  that there are $2^{|V_0|}$ possible labellings of $V_0$.  Your goal is
  to compute a labelling that takes 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 may want to change $v$'s label to
  $1$. Therefore, you decide to compute a labelling that maximises the
  \emph{consistency} $c(G)$ of $G$, defined as
  
  $$c(G) = \sum_{e = (u, v) \in E} w_{e}l_ul_v.$$
  Devise a polynomial time algorithm to maximise $c(G)$. Note that your
  algorithm must produce a label of $1$ or $-1$ for \emph{every} node in
  $V_0$. Therefore, when your algorithm completes, every node in $V$
  should have a label of either $1$ or $-1$. \emph{Hint:} A greedy approach
  will not work. Neither will divide and conquer.

 
% \solution{
%
% }



\item[Problem 4] (20 points) This problem deals with cost-effective
  purchase of candy, a resource-allocation problem of particular
  importance. You enter a candy store. In front of you are glass jars,
  each filled with a different mouth-watering type of candy. You are on
  a strict budget: you have at most $\$b$ with you. There are $n$ types
  of candy, each in a unique jar. For each $1 \leq i \leq n$, the entire
  jar containing the $i$th type of candy costs $\$c_i$ and weighs $w_i$
  kilogrammes. You are allowed to purchase as much candy as you want
  from each jar. You can purchase as tiny a portion of any piece of
  candy as you want. Put another way, you can think of the candy as
  being powdered\footnote{I am not suggesting that anyone will actually
    want to \emph{eat} powdered candy.} and you can scoop up whatever
  weight you want from each jar. Devise an algorithm that maximises the
  total weight of the candy you purchase, as long as the total cost of
  the candy you buy is at most $\$b$.


\centerline{\includegraphics[width=0.4\textwidth]{Gumballs}}

% \solution{
%
% }





\end{description}

\end{document}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 
