\documentclass{article}
\pagestyle{empty}

\begin{document}
\begin{center}
{\LARGE CS140: Algorithms }\\
\vspace{.1 in}
{\Large Fall 2001}\\
\vspace{.3 in}
{\large Assignment 6}
\end{center}

\noindent
This assignment is due by the start of class on Monday, Oct 8.  You may collaborate
with your classmates to complete this assignment but you must reference your collaborators.  In addition,
you must do your own write-up.  This assignment is worth 100 points (65 points if handwritten).  


\vspace{.2 in}
\begin{enumerate}

\item
An {\em independent set} of a graph $G$ is a subset $W$ of the vertices of $G$ such that
no two vertices in $W$ are connected by an edge in $G$.
Finding a largest independent set of an arbitrary graph is NP-hard.  The problem is
solvable in polynomial time, however, if the input is restricted to be a forest.
\begin{enumerate}
\item
Let $F$ be a forest and let $v$ be a leaf in $F$.  Prove that $v$ is in some 
largest set of $F$.
\item
Suppose I give you a black box that will find a largest independent set of a forest with
$n-1$ or fewer nodes.  Explain how to use this box to build an algorithm for finding 
 independent
sets in forests with $n$ or fewer nodes.
Be sure to describe any base cases.  (How do you handle isolated nodes?)
\item
How would you implement this algorithm?  Carefully describe the data structures you'll use.
You may specify the data structure used to represent the input.  Analyze the running time of
the algorithm implemented with your data structures.
\end{enumerate}

\item
In the {\em weighted independent set} problem, the input is a graph $G$ in which each vertex
is assigned a positive weight.  The {\em weight} of an independent set $W$ is the sum
of the weights of the vertices in $W$.  The objective is to find an independent
set with largest weight.  This problem is NP-hard but can be solved in polynomial time if
we restrict the input to be a weighted tree.
\begin{enumerate}
\item
Give an example of a weighted tree $T$ for which your algorithm from problem 2
fails to find a maximum weight independent set.
\item
Give an example of a tree $T$ rooted at some node $r$ such that the union of the maximum
weight independent sets of the children of $r$ is a maximum weight independent set 
$T$.   
\item
Give an example of a tree $T$ rooted at some node $r$ such that the union of the maximum
weight independent sets of the children of $r$ is {\em not} a maximum weight independent set 
$T$.   Give a maximum weight independent set of this tree.
\item
What information would you like about the subtrees of a rooted tree in order to determine
the weight of a maximum weight independent set of the tree?  (You should be able to do this with two
functions on the nodes of the tree.)
\item
Design an algorithm that computes the functions you defined in the previous part.
\item
Show how to use this algorithm to determine the weight of a maximum weight independent set
of a tree.
\item
Show how to modify your algorithms to compute a maximum weight independent set of an input
tree.
\item
Briefly describe implementation details.  Note that an $\Theta(n)$ algorithm is possible.

\end{enumerate}






\end{enumerate}
\end{document}

