%---------change this every homework
\def\yourname{as4bd}
% -----------------------------------------------------
\def\homework{1} % 0 for solution, 1 for problem-set only
\def\duedate{wed may 11 1159p, 2016}
\def\duelocation{}
\def\hnumber{fin}
\def\prof{abhi shelat}
\def\course{\href{https://www.cs.virginia.edu/~shelat/16s-4102}{cs4102 - algorithms - s'16}}
%-------------------------------------
%-------------------------------------
\documentclass[11pt]{article}
\usepackage[colorlinks,urlcolor=blue,linkcolor=black]{hyperref}
\usepackage{fancyhdr}
\usepackage{tikz}
\usepackage[osf]{mathpazo}
%\usepackage{lastpage}
\usepackage{amsmath,amsfonts,graphicx}
\usepackage{latexsym}
\usepackage[top=1in,bottom=1.4in,left=1.5in,right=1.5in,centering]{geometry}
\usepackage{color}
\usepackage{clrscode}
\usepackage{tikz}
\usepackage{pgfplots}
\definecolor{mdb}{rgb}{0.3,0.02,0.02}
\definecolor{cit}{rgb}{0.05,0.2,0.45}
\pagestyle{fancy}
\renewcommand\headrulewidth{0pt} % Removes funny header line
\rhead{\sc{\course\ - \duedate}\hfill{\Huge\sc \yourname \ fin}\hfill\thepage}
\cfoot{}
\fancyfootoffset{.95in}
\newenvironment{proof}{\par\noindent{\it Proof.}\hspace*{1em}}{$\Box$\bigskip}
\newcommand{\qed}{$\Box$}
\newcommand{\alg}[1]{\mathsf{#1}}
\newcommand{\solution}[1]{\medskip\noindent{\color{mdb}\textbf{Solution: }#1}}
\newcommand{\bit}[1]{\{0,1\}^{ #1 }}
\newtheorem{problem}{\sc\color{cit}problem}
\newtheorem{mproblem}{\sc\color{cit}midproblem}
\newtheorem{lemma}{Lemma}
\newtheorem{definition}{Definition}
\begin{document}
\begin{enumerate}
\item[---] This is a pledged take-home final. Do not discuss the final
with anyone except the course staff. You can consult your personal course notes and the course website, but no other resources are allowed. All other forms of assistance are prohibited.
In case of doubt, ask me.
\item[---] The exam is due \textbf{\sc \duedate}. Submit early/often. {\em No late submissions will be accepted!} Every problem must take exactly 2 pages. Your submission should be exactly 8 pages.
\item[---] Submit PDF solutions
to \url{https://church.cs.virginia.edu/16s-4102/}.
\item[---] Prove answers. You will be
graded on {\em clarity}, {\em correctness}, and {\em precision}.
\end{enumerate}
\renewcommand{\labelenumi}{{\bf (\alph{enumi})}}
\begin{problem} Search Reduces to Decision\end{problem}
Let language $L=\{$ pairs $(G,k)$ where $G=(V,E)$ is a graph that has an independent set of size $\geq k$ nodes$\}$. Suppose you are given an algorithm $D_L$ that decides the language $L$. That is, when given an instance $(G,k)$, algorithm ${D}_L(G,k)$ returns ``yes" when graph $G$ has an independent set of size at least $k$, and ``no" otherwise. Design and analyze an efficient polynomial time algorithm that uses $D_L$ to find the largest independent set for any graph $G$. Your new algorthm $F_L(G)$ should output $S$ which is the largest independent set of $G$.
\begin{problem} Dispatch \end{problem}
As the 911 dispatcher, you receive the positions $(p_1,p_2,\ldots,p_n)$ of $n$ injured people as well as a measure of the severity of each person's injuries $(s_1,\ldots,s_n)$. This severity measure $s_i$ tells you that you must deliver patient $i$ to one of the $k$ hospitals in your region within $s_i$ minutes. You can use a good traffic model $d_j(p_i)$ to compute how many minutes it takes to deliver someone from position $p_i$ to hospital $j$.
You would like to distribute the $n$ patients across the $k$ hospitals so that each hospital gets $\lceil n/k \rceil$ patients. Write an efficient algorithm that determines when this is possible or not. Analyze the running time.
\begin{problem}Short paths \end{problem}
\noindent Let $G=(V,E)$ be a directed graph with edge weights $w(e)$ and no negative cycles.
\begin{enumerate}
\item Write one sentence that explains the variable $\proc{ashort}_{i,j,k}$ used in the All-pairs shortest path algorithm discussed in class.
\item State the run time of the All-pairs shortest path algorithm discussed in class.
\item Consider the following algorithm.
\begin{codebox}
\Procname{$\proc{NewAllPairs}(G,w)$}
\li Add a new node $s'$ to $G$. Add edges of weight $0$ from $s'$ to every vertex $v\in V$.\\
Call this new graph $G'$.
\li Run $\proc{BellmanFord}(G',s')$ to produce shortest path lengths $\delta(s',v)$.
\li For each $e=(x,y)\in E$, set $w'(e) \gets w(e) + \delta(s',x) - \delta(s',y)$
\li For each $v\in V$, run $\proc{Dijkstra}(G,v,w')$ to compute $\delta(v,w)$ for all $w\in V$.
\li Set $d_{v,w} \gets \delta(v,w) - \delta(s',v) + \delta(s',w)$
\end{codebox}
\noindent We aim to analyze why this algorithm works. The first step is to argue that the new edge weights
$w'$ that are defined in step (3) are all positive.
Prove that for all $e\in E$, $w'(e) \geq 0$.
\item This explains why we can use the fast $\proc{Dijkstra}$ algorithm with weight $w'$ in step (4) to compute shortest paths from node $v\in V$ to all other nodes in the graph. However, we must argue that the shortest paths under $w'$ and under $w$ will be the same shortest path.
Prove that for any pairs of nodes $u,v\in V$, if $p$ is a shortest path from $u$ to $v$
with respect to weight function $w'$, then $p$ is also a shortest path from $u$ to $v$ with respect to
weight function $w$.
\item What is the running time of $\proc{NewAllPairs}$ in terms of $V$ and $E$? When
does this algorithm run faster than the All-pairs algorithm discussed in class?
\end{enumerate}
\begin{problem}2-pass shortest tours\end{problem}
There are $n$ cities that I want to visit on my private jet. City $i$ is located at $(x_i,y_i)$.
The traveling salesman problem would ask you to visit all $n$ cities with the shortest tour as possible; but alas, that problem is NP-complete, and our private jet pilot also objects to arbitrary paths. To make filing our flight plan easier, our pilot has instead asked us to start from city $1$, fly only eastward until we hit city $n$, and then turn around and fly back to city $1$. However, as we fly east, we can fly as far North or far South as we like; and similarly, as we return west, we can fly as far North or South as we like. Hence, we call it the \emph{2-pass tour}. Since we pay for private jet travel by the hour, we want to find the shortest route subject to this constraint. Devise and analyze an efficient algorithm to compute our 2-pass shortest tour.
\begin{figure}[h]
\pgfplotsset{width=\columnwidth,height=2.4in}
\begin{tikzpicture}[,mark options={scale=.8}]
\begin{axis}[
ymin=0,ymax=100,
xmin=0,xmax=100,
xtick={5,40,90},
ytick={12,40,50,94},
]
\addplot[red,only marks,mark=*] coordinates {
(5,50)
(90, 40)
};
\addplot[blue,only marks,mark=*] coordinates {
(10,75)
(20,55)
(30,42)
(40,12)
(60,94)
(70,22)
(80,65)
};
\addplot[gray,mark=none] coordinates {
(5,50)
(10,75)
(20,55)
(30,42)
(40,12)
(60,94)
(70,22)
(80,65)
(90, 40)
(5,50)
};
\addplot[gray,mark=none,dashed] coordinates {
(5,50)
(20,55)
(30,42)
(40,12)
(70,22)
(90, 40)
(80,65)
(60,94)
(10,75)
(5,50)
};
\end{axis}
\end{tikzpicture}
\caption{In this example, the start and end city are shown in red, and two possible 2-pass tours are shown in gray.}
\end{figure}
\end{document}