\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}{6 October 2006}{9}

\begin{center}
\Large{\bf Problem Set 3 (due Friday, October 13)}
\end{center}

{\bf 1. (10 points) DAGs and cycles}

Chapter 3, Exercise 3, page 107.

{\bf 2. (10 points) Number of shortest paths in social networks}

Chapter 3, Exercise 10, page 110.  ({\em Hint:} Use breadth-first
search.)

{\bf 3. (10 points) Scheduling daily jobs} 

Chapter 4, Exercise 17, page 197.  

{\bf 4. (15 points) Project management}

Suppose you are a high-level manager in a software firm and you are
managing $n$ software projects.  You are asked to assign $m$ of the
programmers in your firm among these $n$ projects.  Assume that all of
the programmers are equally competent.

After some careful thought, you have figured out how much benefit $i$
programmers will bring to project $j$.  View this benefit as a number.
Formally put, for each project $j$, you have computed an array $A_j[0..m]$
where $A_j[i]$ is the benefit obtained by assigning $i$ programmers to project
$j$.  Assume that $A_j[i]$ is nondecreasing with increasing $i$.  Further make
the economically sound assumption that the marginal benefit obtained by
assigning an $i$th programmer to a project is nonincreasing as $i$ increases.
Thus, for all $j$ and $i \ge 1$, $A_j[i+1] - A_j[i] \le A_j[i] - A_j[i-1]$.

Design a greedy algorithm to determine how many programmers you will assign to
each project such that the total benefit obtained over all projects is
maximized.  Justify the correctness of your algorithm and analyze its running
time.

{\bf 5. (15 points) Planning an expedition}

Chapter 4, Exercise 18, page 197.

\end{document}