%---------change this every homework
% place your email id between the braces so that your homework has a name
\def\yourname{}
% -----------------------------------------------------
\def\homework{1} % 0 for solution, 1 for problem-set only
\def\duedate{mon nov 14, 2016 at 11.59p}
\def\duelocation{via \href{https://gradescope.com/courses/4095}{gradescope}}
\def\hnumber{5}
\def\course{\href{https://shelat.ccis.neu.edu/16f-4800}{cs4800 - algorithms - f'16}}
%-------------------------------------

\documentclass[10pt]{article}
\usepackage[colorlinks,urlcolor=blue]{hyperref}
\usepackage[osf]{mathpazo}
\usepackage{amsmath,amsfonts,graphicx}
\usepackage{latexsym}
\usepackage[top=1in,bottom=1.4in,left=1.5in,right=1.5in,centering]{geometry}
\usepackage{color}
\definecolor{mdb}{rgb}{0.3,0.02,0.02} 
\definecolor{cit}{rgb}{0.05,0.2,0.45} 
%\pagestyle{myheadings}
\markboth{\yourname}{\yourname}

\thispagestyle{empty}

\newenvironment{proof}{\par\noindent{\it Proof.}\hspace*{1em}}{$\Box$\bigskip}
\newcommand{\qed}{$\Box$}
\newcommand{\alg}[1]{\mathsf{#1}}
\newcommand{\handout}{
   \renewcommand{\thepage}{H\hnumber-\arabic{page}}
   \noindent
   \begin{center}
      \vbox{
    \hbox to \columnwidth {\sc{\course} --- shelat/nguy{\~{\^{e}}}n \hfill}
    \vspace{-2mm}
    \hbox to \columnwidth {\sc due \MakeLowercase{\duedate} \duelocation\hfill {\Huge\color{mdb}H\hnumber.\yourname}}
      }
   \end{center}
   \vspace*{2mm}
}
\newcommand{\solution}[1]{\medskip\noindent\textbf{Solution:}#1}
\newcommand{\bit}[1]{\{0,1\}^{ #1 }}
%\dontprintsemicolon
%\linesnumbered
\newtheorem{problem}{\sc\color{cit}problem}
\newtheorem{lemma}{Lemma}
\newtheorem{definition}{Definition}
\usepackage{clrscode}
\usepackage[T1]{fontenc}

\begin{document}
\handout
\begin{itemize}
\item The assignment is due at Gradescope on Monday, November 14 at 11:59pm. Late assignments will not be accepted. Submit early and often.

\item You are permitted to study with friends and
      discuss the problems; however, {\em you must write up you own
        solutions, in your own words}. Do not submit anything you
        cannot explain. 
     If you do collaborate with any of the other students on any
      problem, please do list all your collaborators in your
      submission for each problem. 
      
      \item Finding solutions to homework problems on the web, or by asking
 students not enrolled in the class is strictly prohibited. 

\item We require that all homework submissions are prepared in Latex. If you need to draw any diagrams,
however, you may draw them with your hand.  Please use \emph{a new page to begin each answer.} 
\end{itemize}



\begin{problem}Another All-pairs 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  $d(i,j,k)$ used in the Floyd-Warshall 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 non-negative.

 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}Gold Bullion face\end{problem}
In the ruins of Pompeii, I remember seeing the \href{http://en.wikipedia.org/wiki/House_of_the_Tragic_Poet}{House of the Tragic Poet} with a  famous mosaic floor proclaiming visitors to ``Beware of the Dog."   In  Boston,  a  less tragic and  wealthier poet has commissioned a mosaic using 1kg bars of solid gold, specifically the type CreditSuisse mints  in the dimension 80mmx40mm.

Design an algorithm that takes as input a grid of 40mmx40mm squares that are either colored or white. The algorithm determines if the colored squares in the design can be {\em entirely covered} with gold bullion bars.  Note that gold bars can never be split in half!  Each gold bar covers exactly two of the squares.  As an example, consider the gold bars on the left, and the pixel art on the right.  Can the leaf be covered in gold? 

\begin{center}
\includegraphics[height=0.8in]{gold2.jpeg}
\includegraphics[height=1.6in]{aa.png}
\end{center}

(Hint: formulate the question as a type of bipartite matching problem.)

\begin{problem} Matrix rounding
\end{problem}

Suppose we are given a large matrix $A[1 \ldots m][1 \ldots n]$ of population data (each entry is a non-negative real number). We want to publish matrix $A$, but need to simplify it for the public by making the entries integers by replacing  each entry $x$ in $A$ with either $\lceil x \rceil$ or $\lfloor x \rfloor$. However, the matrix represents important population data, and we do not want to change the sums of entries in any row or column.  For example:

$$ \left[ \begin{array}{ccc}
	1.2 & 3.4 & 2.4 \\
	3.9 & 4.0 & 2.1 \\
	7.9 & 1.6 & 0.5
	\end{array}
	\right]
	\rightarrow
 \left[ \begin{array}{ccc}
	1 &  4 & 2 \\
	4 &  4 & 2 \\
	8 & 1 & 1
	\end{array}
	\right]
$$

Using max flow, describe and analyze an efficient algorithm that either rounds $A$ in this fashion, or
reports correctly that no such rounding is possible.



\end{document}
