\documentstyle[11pt,handout]{article}
\begin{document}
\input{macros}
\input{/home/rraj/Courses/1390/Syllabus/localmacros}
\newcommand{\hs}{\hspace{1em}}
\newcommand{\Hspace}{\hspace{1em}}

\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}

\head{1390}{Algorithms}{Winter 1999}{16 February 1999}{18}

\begin{center}
\Large{\bf Problem Set 4 (due February 25)}
\end{center}

\bigskip
{\bf 1. (15 points)} Exercise 16.3--5.  

{\bf 2.} Consider a weighted version of the activity selection problem, in
which each activity has a {\em weight}, in addition to the start and finish
times.  (For example, the weight may signify the importance of the activity.)
The goal is to select a maximum-weight set of mutually compatible activities,
where the weight of a set of activities is the sum of the weights of the
activities in the set.
\begin{Itemize}
\item[{\bf (a) (5 points)}]
Give a counterexample to show that the greedy choice made for the activity
selection problem will not work for the weighed activity selection problem.

\item[{\bf (b) (20 points)}]
Use dynamic programming to solve the weighted activity selection problem.
Analyze the running time of your algorithm.
\end{Itemize}

{\bf 3. (20 points)} 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 (10 bonus points)} Now {\em remove}\/ the assumption made above that the
marginal benefit obtained by assigning an $i$th programmer to a project is
nonincreasing as $i$ increases.  Design a dynamic programming algorithm to
determine how many programmers you will assign to each project such that the
total benefit obtained over all projects is maximized.  Analyze its running
time.

{\bf 4. (10 points)} Exercise 17.3--2.
\end{document}