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

\head{CSU690}{Algorithms and Data}{Fall 2006}{1 November 2006}{16}

\begin{center}
\Large{\bf Problem Set 5 (due Friday, November 10)}
\end{center}

{\bf 1. (12 points) Planning a company party}

You are consulting for a corporation that is planning a company party.
The company has a hierarchical structure that can be captured as a
tree rooted at the president.  Thus, every node of the tree represents
a person and the parent of any node (except the root) represents the
immediate supervisor of the person.  The personnel office has ranked
each employee with a convivialty rating, which is a real number.  In
order to make the party fun for all attendees, the president does not
want both an employee and his or her immediate supervisor to attend.

Given the tree structure of the company hierarchy and the conviviality
ratings of each person, describe an algorithm to make up a guest list
that maximizes the sum of the conviviality ratings of the guest.

{\bf 2. (12 points)} Chapter 6, Exercise 17, page 327.

{\bf 3. (12 points)} Chapter 7, Exercise 7, page 417.

{\bf 4. (12 points)} Chapter 7, Exercise 8, page 418.

{\bf 5. (12 points) Updating the maximum flow in a network}

You are given a directed network $G$ with $n$ nodes and $m$ edges, a
source $s$, a sink $t$ and a maximum flow $f$ from $s$ to $t$.  Assume
that the capacity of every edge is a positive integer.  Describe an
$O(m + n)$ time algorithm for updating the flow $f$ in each of the
following two cases.
\begin{itemize}
\item[{\bf (a)}]
The capacity of an edge $e$ increases by 1.
\item[{\bf (b)}]
The capacity of an edge $e$ decreases by 1.
\end{itemize}

\end{document}