\documentclass[12pt]{article}
\usepackage{fullpage}
\addtolength{\topmargin}{-0.2in}
\addtolength{\textheight}{0.3in}
\newcommand{\Header}[1]{\begin{center} {\Large\bf #1} \end{center}}
\newcommand{\header}[1]{\begin{center} {\large\bf #1} \end{center}}
\newcommand{\orr}{\vee}
\setlength{\parindent}{0.0in}
\setlength{\parskip}{1ex}
\newcommand{\andd}{\wedge}
\newcommand{\ep}{\varepsilon}
\newcommand{\de}{\delta}
\newcommand{\half}{\frac{1}{2}}
\newcommand{\inv}[1]{\frac{1}{#1}}
\newcommand{\prob}{{\bf Prob}}
\newtheorem{theorem}{Theorem}
\newtheorem{definition}{Definition}
\newtheorem{claim}{Claim}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{corollary}[theorem]{Corollary}
\newcommand{\qed}{\mbox{\ \ \ }\rule{6pt}{7pt} \bigskip}
\newcommand{\mathqed}{\mbox{\ \ \ \rule{6pt}{7pt}}}
\newcommand{\D}{{\cal D}}
\renewcommand{\Pr}{{\bf Pr}}
\newcommand{\pair}[1]{\langle #1 \rangle}
\newcommand{\mod}{\bmod}
\newcommand{\proj}{{\em proj}}
\newcommand{\proof}{{\em Proof. }}
\newcommand{\R}{{\bf R}}
\newcommand{\E}{{\bf E}}
\newcommand{\var}{{\bf var}}
\newcommand{\lesso}{<^o}
\newcommand{\eqtheta}{=^{\Theta}}
\newcommand{\comment}[1]{}
\newcommand{\bigcenter}[1]{\begin{center} {\large\bf #1} \end{center}}
\newcommand{\ceiling}[1]{\left\lceil #1 \right\rceil }
\newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor }

\newcommand{\answer}[1]{\sf #1} %%%

\newcommand{\ins}{{\sf insertion-sort}}
\newcommand{\qs}{{\sf quicksort}}
\addtolength{\textheight}{0.3in}
\begin{document}
\header{15-451 Algorithms, Fall 2011}
{\bf Homework \# 5} \hfill {\bf due: Tuesday November 8, 2011}

\thispagestyle{empty}


\medskip

\hrule

\medskip
Please hand in each problem on a separate sheet and put
your {\bf name} and {\bf recitation} (time or letter) at the top of
each sheet.  You will be handing each problem into a separate box,
and we will then give homeworks back in recitation.

Remember: written homeworks are to be done {\bf individually}.  Group
work is only for the oral-presentation assignments.

\medskip

\hrule

\medskip
{\bf Problems:}
\begin{enumerate}
\item[(35 pts) 1.]  {[Fair carpooling]}
The $n$ employees of the Algo Rhythms music downloading service sometimes
carpool to work together.\footnote{Any relation to actual companies or
bands of this name is purely coincidental.}
Say there are $m$ days, and $S_i$ is the
set of people that carpool together on day $i$.  For each set, one of
the people in the set must be chosen to be the driver that day.
Since people would rather not drive, they want the work of driving to be
divided as fairly as possible.  Your task in this problem is to give
an algorithm to do this efficiently.

The fairness criterion is the following: Say that person $p$ is in
some $k$ of the sets, which have sizes $n_1, n_2, \ldots,
n_k$, respectively.  Person $p$ should really have to drive ${1 \over
n_1} + {1 \over 
n_2} + \cdots + {1 \over n_k}$ times, because this is the amount of
resource that this person effectively uses.  Of course this number may
not be an integer, so let's round it up to an integer.  The fairness
criterion is simply that she should drive no more than this many
times.

For example, say that on day 1, Alice and Bob carpool together, and on
day 2, Alice, Carl, and Dilbert carpool together.  Alice's fair cost would be 
$\ceiling{1/2 + 1/3} = 1$.  So Alice driving both days would not be fair.  Any
solution except that one is fair.

\begin{enumerate}
\item Prove that there always exists a fair solution.
\item Give a polynomial-time algorithm for computing a fair solution
from the sets $S_i$.

\end{enumerate}

Hint: Try to model the problem using network flow in such a way that
part (a) falls out directly from the integrality theorem for network
flow, and part (b) just follows from the fact that we can solve max
flow in polynomial time.   So, it all boils down to coming up with the
right flow graph to model the problem. 

\item[{(30 pts) } 2.]{[Graduation]}
Cranberry-Melon University has $n$ courses.\footnote{Any relation to
actual universities of similar name is purely coincidental. OK, that's
a lie - it's not.}  In order
to graduate, a student must satisfy several requirements.  Each
requirement is of the form ``you must take at least $k_i$ 
courses from subset $S_i$''.  The problem is to determine whether or not
a given student can graduate.  The tricky part is that any given
course cannot be used towards satisfying multiple requirements.  For
example if one requirement states that you must take at least two
courses from $\{A,B,C\}$, and a second requirement states that you
must take at least two courses from $\{C,D,E\}$, then a student
who had taken just $\{B,C,D\}$ would not yet be able to graduate.

Your job is to give a polynomial-time algorithm for the following
problem.  Given a list of requirements $r_1, r_2, \ldots, r_m$ (where
each requirement $r_i$ is of the form: ``you must take at least $k_i$
courses from set $S_i$''), and given a list $L$ of courses taken by
some student, determine if that student can graduate.  In particular,
show how you can solve this using network flow.


\item[{(30 pts) } 3.]{[Realizing degree sequences]}
You are the chief engineer for Graphs-R-Us, a company that makes
graphs to meet all sorts of specifications.
\begin{enumerate}
\item A client comes in and says he needs a 4-node directed graph in
which the nodes have the following in-degrees and out-degrees:
$$\begin{array}{rrrr}
d_{1,in} = 0, & d_{2,in}=1, & d_{3,in}=2, & d_{4,in}=3\\
d_{1,out} = 2,&  d_{2,out}=2,&  d_{3,out}=1, & d_{4,out}=1\\
\end{array}$$


Is there a directed graph, with no multi-edges or self loops, that
meets this specification?  If so, what is it?

\item What about a 3-node graph (again with no multi-edges or self
loops) with these in-degrees and out-degrees?
$$\begin{array}{rrr}
d_{1,in} = 2, & d_{2,in}=2, & d_{3,in}=1 \\
d_{1,out} = 2, & d_{2,out}=2, & d_{3,out}=1\\
\end{array}$$


\item  This type of specification, in which the in-degrees and
out-degrees of each node are given, is called a {\em degree
sequence}.  The question above is asking whether a given degree
sequence is {\em realizable} --- that is, whether there exists a
directed graph having those degrees. 

Find an efficient algorithm that, given a degree sequence, will
determine whether this sequence is realizable, and if so will produce
a directed graph with those degrees.  The graph should not have any
self-loops, and should not have any multi-edges (i.e., for each
directed pair $(i,j)$ there can be at most one edge from $i$ to $j$,
though it is fine if there is also an edge from $j$ to $i$).  Hint:
as if you couldn't have guessed - think network flow!
\end{enumerate}
\item[{(5 pts)} 4.]{[Elevators and Stairs]}
In preparation for the discussion in one of the upcoming classes,
identify a place in your daily or weekly routine where you could
reasonably choose to take the elevator or the stairs.  Time the
following three quantities:
\begin{enumerate}
\item How long does it take if you choose to take the stairs?
\item How long does it take, from the time the elevator arrives, if
you choose to take the elevator?  (If you want, try 3 times and take
the average).
\item How long do you typically have to wait for the elevator to
arrive? (If you want, try 3 times and take the average).
\end{enumerate}
Note: if you don't want to try 3 times and take the average, you can
just do it once.  Actually, we're not going to check up on you, so if you don't
do it at all and just write in plausible numbers above you will still
get full credit, but where's the fun in that?
\end{enumerate}
\end{document}