\documentstyle[11pt,handout]{article}
\begin{document}
\input{macros}

\newcommand{\name}{\mbox{{\em name}}}
\newcommand{\myyear}{\mbox{{\em year}}}
\newcommand{\salary}{\mbox{{\em salary}}}

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

\head{3390}{Analysis of Algorithms}{10 November 1998}{17}

\begin{center}
\Large{\bf Problem Set 3 (due November 25)}
\end{center}

\bigskip
{\bf 1. (12 points)} Suppose you are maintaining a database that relates the
salaries of the employees in your firm to their ages.  Design a data structure
that efficiently supports the following three operations:
\begin{itemize}
\item
{\sc Insert}$(\name, \myyear, \salary)$, where $\name$ is the name of an
employee, $\myyear$ is the year of birth of the employee and $\salary$ is the
annual salary of the employee.  You should assume that the names of all of the
employees are distinct.

\item
{\sc Delete}$(\name, \myyear)$, where $\name$ is the name of an employee in the
database and $\myyear$ is the year of birth of the employee.

\item
{\sc Average}$(y_1, y_2)$, where $y_1$ and $y_2$ are two years and $y_1 \le
y_2$.  This operation returns the average salary of the employees born between
$y_1$ and $y_2$, both years included.
\end{itemize}
({\em Hint:}\/ Make use of an appropriately-augmented balanced binary search
tree.)

{\bf 2. (15 points)} Problem~16--3.

{\bf 3. (15 points)} Consider a set of $n$ rectangular paving stones where the
$i$th stone is $l_i$ units long and $w_i$ units wide, $l_i\geq w_i\geq 1$.
Assume that paving stone $i$ can be stacked on top of paving stone $j$ iff
$l_i\leq l_j$ and $w_i\leq w_j$.  Give an efficient algorithm for computing
the maximum number of paving stones that can be stacked together, and analyze
the asymptotic running time of your algorithm.  ({\em Hint:}\/ Use dynamic
programming.)

{\bf 4. (8 + 8 + 4 = 20 points)} Problem~17--1.

{\bf 5. (16 points total)} 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) (4 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) (12 points)}]
Use dynamic programming to solve the weighted activity selection problem.
Analyze the running time of your algorithm.
\end{Itemize}

{\bf 6. (10 points)} Exercise~17.3--4.

{\bf 7. (6 + 6 = 12 points)} Exercise~7.5--3.

\end{document}


