\documentclass[12pt]{article}

\begin{document}
\begin{center}
	\bf
	Algorithms \\
	Computer Science 140 \& Mathematics 168 \\
	Spring 2009 \\
	\rm
	Homework 4a\\
	Due Thursday, February 12
\end{center}

You are encouraged, but no longer required, to use \LaTeX\ to typeset your solutions to assignments in this course.
\begin{enumerate}

\item \textbf{[20 Points]  The Millisoft Party Problem Revisited!}
On the last homework assignment, Gill Bates challenged you to find a dynamic programming algorithm to solve the Millisoft Party Problem.  Now, Gill tells you:  ``Assigning a coefficient of fun to each employee is too subjective.   I just want to find the largest number of people that I can invite such that we never invite an employee and their immediate boss.  This is analogous to every employee having the same coefficient of fun.''   

In other words, your task is to take as input a tree representing the company hierarchy.  The tree need not be binary.  Non-leaf nodes may have 1 child, 2 children, 3 children, or more!  Your objective is to find an algorithm that computes the largest number of employees (nodes) that can be selected such that no two adjacent nodes (i.e. a node and its child) are chosen.

Describe a \emph{greedy algorithm} for this problem (in either pseudo-code or clear English), carefully prove its correctness, and analyze its running time.

\end{enumerate}

\end{document}