\documentclass[12pt]{article}
\usepackage{fullpage}
\begin{document}
\begin{center}
\bf
Algorithms\\
Computer Science 140 \& Mathematics 168\\
Instructor: B. Thom\\
Fall 2003\\
\rm
Homework 5a\\
Due on 10/3/03 (Friday at 2pm)\\
\end{center}
\begin{enumerate}

\item {\bf [30 Points] Optimizing Party Fun!}

After your success at Snapple, you've decided to accept a job as
senior algorithm designer at the well-known
My-I'm-Soft Corporation.  One day, the President of My-I'm-Soft, Gill
Bates, comes to you with the following problem.  ``I'm throwing
a company party,'' Gill says excitedly, ``And I need your help!
As you know, My-I'm-Soft has a hierarchical structure.  You can
think of it as a tree.  The president, that's me, is at the root 
of the tree.  Oh boy, I love being at the root!''  You take a sip
of your luke-warm diet coke (which My-I'm-Soft provides for free -
what a perk!) and listen patiently as Gill continues.
``Below the root are supervisors, below them are managers, below them
are team leaders, etc., etc., until you get down to the leaves -
the summer interns.  Anyhow, to make the party fun, I thought it best
that we don't invite an employee along with their immediate boss
(their parent in the tree).  Also, I've personally assigned every employee a
real number (actually it's a double precision floating point, but
never-mind that!) called their {\em coefficient of fun}.  My objective 
is
to invite employees so as to maximize the total sum of the
coefficients of fun of all invited guests, while not inviting an
employee with his or her immediate boss.''

\begin{enumerate}
\item The first algorithm that Gill thought up was to simply
enumerate all possible subsets of his employees, 
throw out those subsets that include an employee and his or
her boss, find the score for each remaining subset, and finally choose
the best one.  There are $1000$ employees at soft.  My-I'm-Soft has
also just purchased a Crayfish YMP that can process one trillion 
($10^{12}$) subsets per second.  How long will it take to find the
optimal solution using this brute force approach on the Crayfish?



\item Describe in detail an efficient dynamic programming
algorithm for this problem.  What is the asymptotic running time 
of your algorithm?



\item Develop a greedy algorithm for the case when all coefficients of fun equal 1 and 
argue its correctness.



\end{enumerate}

\end{enumerate}
\end{document}
