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

\newif\ifanswer
\answertrue
\head{CS5800}{Algorithms}{Spring 2011}{25 April 2011}{29}

\begin{center}
\Large{\bf Final Exam}
\end{center}

{\bf Instructions.}
\begin{Itemize}
\item {\bf Problems and Points:} There are seven problems, for a total
  of 60 points.  Read all the problems through first and attack them
  in the order that allows you to make the most progress.

\item
{\bf Presentation of solutions:} While describing an algorithm, you
may use any of the algorithms covered in class or in the text as a
subroutine, without elaboration.  

\item {\bf Proofs:} You need to give proofs only in problems where
  they are explicitly required.

\item {\bf A note on grading:} Your grade on any problem will be
  determined on the basis of the correctness of your solution and the
  clarity of the description.  In case you are not able to present an
  algorithm that has the desired properties, give the best algorithm
  you have designed.  Show your work, as partial credit may be given.
  If you need extra space, use the blank facing page.

\item
Best of luck!
\end{Itemize}

\vfill

{\Large
\begin{center}
\begin{tabular}{||c|c|c||}\hline
Question & Score & Maximum \\ \hline
1 & & 7 \\ \hline
2 & & 8 \\ \hline
3 & & 10 \\ \hline
4 & & 10 \\ \hline
5 & & 10 \\ \hline
6 & & 10 \\ \hline
7 & & 5 \\ \hline
Total & & 60 \\ \hline
\end{tabular}
\end{center}
}

\vfill
\vfill

\begin{center}
{\bf Name:} {\vrule height0.4pt width3in}
\end{center}
\vfill
\vfill

\newpage

{\bf Problem~1. (7 points) Heavy-hitters: the top $k$ elements}

Given a list $L$ of $n$ elements, the {\em frequency}\/ of an element
$x$ in $L$ is the number of times $x$ occurs in $L$.  For instance, if
$L$ is the list $[A, B, B, A, C, C, C, A, B, A, D]$, then the
frequencies of $A$, $B$, $C$, and $D$ in $L$ are $4$, $3$, $3$, and
$1$, respectively.

Give an algorithm that takes as input a list $L$ of $n$ elements and
an integer $k$, and returns $k$ distinct elements of $L$ with the
highest frequencies in $L$.  If multiple elements have the same
frequency, you may break ties arbitrarily.  If there are fewer than
$k$ distinct elements in $L$, then your algorithm should return all of
the distinct elements in $L$.

For instance, if the input to your algorithm is the above list $L$ and
$k = 2$, then the output should be either $\{A, B\}$ or $\{A, C\}$.

Analyze the worst-case running time of your algorithm.  The more
efficient your algorithm is in terms of its worst-case running time,
the more credit you will get.

\newpage

{\bf Problem~2. (5 + 5 = 10 points total) Pairing in a dance class} 

A group of $n$ men and $n$ women are attending a dance class.  The
instructor wants to pair each man with a woman in such a way that the
sum of the absolute value of the height differences between partners
is minimized.
\begin{Itemize}
\item[{\bf (a)}] Let $A$ be a tallest woman in the class (there
  could be a tie), and let $B$ be a tallest man.  Prove that there is
  an optimal pairing in which $A$ is paired with $B$.

\newpage 

\item[{\bf (b)}] Based on the result of part~(a), give a
  polynomial-time greedy algorithm for computing an optimal pairing.
  Analyze the worst-case running time of your algorithm.
\end{Itemize}

\newpage

{\bf Problem~3 (5 + 5 = 10 points) Short-answer questions on minimum
  spanning trees and network flows}

\begin{itemize}
\item[{\bf (a)}] True or False: For any connected weighted undirected
  graph $G$, and any node $u$ of $G$, if $(u,v)$ is an edge that has
  minimum weight {\em among all edges incident on $u$}, then $(u,v)$
  belongs to some minimum spanning tree of $G$.

  If your claim is ``True'', then give a brief proof; if your claim is
  ``False'', then provide a counterexample.

\newpage

\item[{\bf (b)}] Let $G$ be a network flow graph with source $s$ and
  sink $t$, and let $P$ be any directed path in $G$ from $s$ to $t$.
  Suppose we increase the capacity of every edge in $P$ by one unit.
  Indicate which one of the following three statements is true.
  Briefly justify your answer.
\begin{itemize}
\item[(i)] It is always the case that (i.e., for every choice of $G$
  and $P$) the maximum flow from $s$ to $t$ increases by exactly one.
\item[(ii)] It may be the case that (i.e., there exist $G$ and $P$
  such that) the maximum flow from $s$ to $t$ does not increase.
\item[(iii)] It may be the case that (i.e., there exist $G$ and $P$
  such that) the maximum flow from $s$ to $t$ increases by more than
  one unit.
\end{itemize}

\end{itemize}

\newpage

{\bf Problem 4. (10 points) All-pairs cheap shortest routes}

You have been awarded a contract from the American Automobile
Association (AAA) to develop a software that determines shortest paths
between all pairs of major cities in the United States.  You have been
supplied a directed graph $G$ over the cities, in which each edge $(i,
j)$ represents a one-way highway from city $i$ to city $j$.  For each
highway $(i,j)$, you are given a nonnegative distance $d_{ij}$.
Furthermore, each highway is one of two categories: {\em freeway}\/ or
{\em tollway}.

AAA has determined that while its customers are interested in finding
shortest paths, they are particularly concerned about tolls too.
Design a polynomial-time algorithm that takes as input the above
directed graph $G$, and a nonnegative integer $k$, and determines for
each pair $(i,j)$ the length of the shortest path from $i$ to $j$ that
uses at most $k$ tollways.

Analyze the worst-case running time of your algorithm.  

\newpage

{\bf Problem 5. (10 points) Intercepting encoded communication}

You have intercepted some communication -- a sequence $\sigma$ of $m$
bits -- that you suspect is between your rivals Alice and Bob.  You
know that every communication between them is a sequence of codewords
drawn from a set $S$ of $n$ binary words that they share.  And you
know the set $S$.  You would like to determine whether $\sigma$ is
indeed a concatenation of words from $S$.  

Give an algorithm that takes $\sigma$ and $S$ as input and determines
whether $\sigma$ is a concatenation of words from $S$.  Your algorithm
must run in time polynomial in $m$ and $n$.  Analyze the worst-case
running time of your algorithm.

{\em Example:} Suppose $S$ is the set $\{1, 101, 111, 00, 100, 10,
110\}$.  If $\sigma$ is $10111100$, then your algorithm should return
``yes'' since $\sigma$ can be written as $101 + 111 + 00$.  Note that
there are multiple ways that $\sigma$ can be written as a
concatenation of words in $S$; for instance, $10 + 111 + 100$ and $10
+ 1 + 1 + 1 + 1 + 00$.  

If $\sigma$ is $00000$, then your algorithm should return ``no'' since
$\sigma$ cannot be written as any concatenation of the words in $S$.

\newpage

[Blank page, in case you need more space for Problem 5]

\newpage

{\bf Problem 6. (10 points) Scheduling doctors at a hospital}

A hospital is attempting to schedule their doctors for night shifts
over the next $n$ nights.  There are $d$ doctors.  Each doctor
specifies a set of nights they are available for the night shift; let
$S_i$ denote the set of nights that the $i$th doctor is available, $1
\le i \le d$.  The hospital has determined its exact need for each
night; for the $j$th night, $1 \le j \le n$, the hospital needs {\em
  exactly}\/ $p_j$ doctors to do the night shift.  There is one
further constraint.  To be fair, the hospital does not want any doctor
to do more than $k$ night shifts.

Give a polynomial time algorithm to determine an assignment of the $d$
doctors to the $n$ nights so that all relevant constraints are met:
every night that the $i$th doctor is assigned to is in $S_i$; exactly
$p_j$ doctors are assigned on night $j$; and no doctor is assigned to
more than $k$ nights.  If no such assignment is possible, then your
algorithm should indicate so.  (The running time of your algorithm
should be polynomial in $n$ and $d$.)

\newpage

[Blank page, in case you need more space for Problem 6]

\newpage

{\bf Problem 7. (5 points) Zero-weight directed cycle}

Given a directed graph $G = (V,E)$ with integer weights on edges that
could be zero, negative or positive, the zero-weight directed cycle
problem is to determine whether there exists a directed cycle with
weight exactly zero.  Show that this problem is NP-complete.

({\em Hint:} Use the Directed Hamiltonian Path Problem, or the
Directed Rudrata Path Problem for your reduction.)

\junk{
{\bf Problem 5. (15 points) \hs } An {\em arborescence}\/ of a
directed graph $G$ is a rooted tree in which there is a directed path
from the root to every vertex in $G$.  Design an efficient algorithm
to determine whether a given directed graph has an arborescence.
Analyze the worst-case running time of the algorithm.
}

\end{document}