\documentclass[11pt]{article}
\usepackage{handout2e}
\begin{document}
\input{macros}
\input{courseMacros}
\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}

\head{CS7800}{Advanced Algorithms}{Fall 2014}{24 November 2014}{22}

\begin{center}
\Large{\bf Problems of the Week -- 15 and 16}
\end{center}

{\bf 15. Sequencing jobs with deadlines}

Earlier in the semester, we used matroid theory to solve a job
scheduling problem optimally.  There are hundreds of useful job
scheduling formulations in the literature, and many of them happen to
be NP-complete.  Here is one.

Given a collection of $n$ jobs, labeled $1$ through $n$, with job $i$
released at time $r_i$ and requiring processing time $p_i$ units, we
would like to determine if all of the jobs can be executed
sequentially in such a way that they all complete within their
deadlines.  Using a reduction from the subset sum problem, show that
this scheduling problem is NP-complete.

{\bf 16. Luckiest sheep}

A wolf is located at node $0$ of a ring consisting of $n+1$ nodes $0$,
$1$, \ldots, $n$, with an (undirected) edge between node $i$ and node
$(i + 1) \bmod (n+1)$ for $0 \le i \le n$.  Each node $i$, $i > 0$, has
a sheep.  The wolf starts a random walk on the ring from $0$.  In each
step, it selects one of its two neighbors uniformly at random, moves
there and gobbles up the sheep present there, if not already eaten.
Which sheep is likely to be eaten the last?  That is, for which $i$ is
the probability that the sheep at $i$ is eaten last the maximum?

\end{document}