\documentclass[11pt]{article}
\usepackage{handout2e}
\begin{document}
\input{macros}
\input{courseMacros}
\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}

\newif\ifanswer
\answertrue
\head{CS5800}{Algorithms}{Spring 2011}{28 March 2011}{19}

\begin{center}
\Large{\bf Quiz 4}
\end{center}

\noindent {\Large Name:~}\leaders\hrule\hfill\ 

\smallskip

{\bf (2 + 8 = 10 points) Maximum weight independent set on path graphs}

A path graph $G$ is simply an undirected graph consisting of the
vertex set $V = \{v_1, v_2, \ldots, v_n\}$ and the edge set 
\[
E = \{(v_i, v_{i+1}): 1 \le i \le n- 1\}.
\]

An {\em independent set}\/ of $G$ is a subset $I$ of $V$ such that
there is no edge in $E$ between any pair of vertices of $I$.  We also
associate a positive weight $w_i$ with vertex $v_i$.  The weight of
any subset $S$ of vertices is simply the sum of the weights of the
vertices in $S$.

For example, consider a path graph $G$ with five vertices $v_1$,
$v_2$, $v_3$, $v_4$, $v_5$, with weights $1$, $9$, $6$, $3$, and $7$,
respectively and four edges $(v_1, v_2), (v_2, v_3), (v_3, v_4),
(v_4, v_5)$.  The set $\{v_1, v_4\}$ is an independent set with weight
$4$, while the set $\{v_1, v_3, v_4\}$ is not an independent set.

This exercise concerns an algorithm for finding a maximum-weight
independent set of a given path graph $G$.

\begin{itemize}
\item[{\bf (a)}] Consider the following greedy algorithm.
\begin{enumerate}
\item Initialize the independent set $I$ to be empty.

\item While some node remains in $G$, add a node $v$ in $G$ of highest
  weight to $I$, and remove $v$ and its neighbors from $G$.

\item
Return $I$.
\end{enumerate}
Give a counterexample that shows that the above greedy algorithm does
not return a maximum-weight independent set.

{\bf Answer:} An counterexample is the following: Consider a path
graph $G$ with three vertices $v_1$, $v_2$, $v_3$, with weights 3, 5,
4 respectively, and two edges $(v_1,v_2)$, $(v_2,v_3)$.

According to the greedy algorithm, it will first pick up $v_2$ into
$I$, and remove $v_1$ and $v_3$ which are connected to $v_2$. Then
return $I$, and its weight is 5.

Obviously this $I$ is not the maximum-weight independent set, since
we have ${v_1,v_3}$ whose weight is 7, bigger than the $I$ returned
by the greedy algorithm.

\newpage

\item[{\bf (b)}] Give a polynomial-time dynamic programming algorithm
  to solve the problem.  It is sufficient to give a recurrence, and
  describe your algorithm briefly in words.  State the running time of
  your algorithm.

  {\bf Answer:} We denote $m(k)$ as the subproblem of the original
  problem, which represents finding the maximum-weight independent set
  from the first $k$ vertices and the subgraph consisted by them.

Initially we have:
\begin{eqnarray*}
m(0) &=& 0 \\
m(1) &=& \max \{ w_1, 0 \}
\end{eqnarray*}
Note, we need to consider if $w_1$ is positive.

Recursively, when we consider $m(k)$, we have two possibilities:
\begin{itemize}
\item
If we choose $v_k$, then we have ${m(k) = m(k-2) + w_k}$(if $w_k$ is
negative, we have ${m(k)=m(k-2)}$)
\item
If we don't choose $v_k$, then we have ${m(k) = m(k-1)}$
\end{itemize}

So we have the following equations:
\begin{eqnarray*}
m(k) = \max \{ m(k-1), m(k-2) + w_k \}
\end{eqnarray*}

Thus we need only one-pass to traverse all the $m(k)$, and got the
solution in $O(n)$ time.

\end{itemize}

\end{document}