\documentclass[11pt]{article}\pagestyle{empty}
\usepackage{amsmath,amssymb,amsthm,color,graphicx}
\usepackage{euscript}
\usepackage{mathpazo}

\usepackage[top=1.5in,bottom=1.5in,left=1.25in,right=1.25in]{geometry}
%improve trypography

\usepackage{microtype}
\usepackage{fixltx2e}
\usepackage{fullpage}
\usepackage{xspace}
\usepackage{tikz}
\usepackage{enumitem}


{\catcode`\@=11
\gdef\setft#1#2#3{%
\def\@oddfoot{%
{\setbox0=\hbox{#1}%
\setbox1=\hbox{#3}%
\ifdim\wd0>\wd1%
\dimen0=\wd0%
\box0\hfil#2\hfil\hbox to\dimen0{\hfil\hfil\box1}%
\else \dimen0=\wd1%
\hbox to\dimen0{\box0\hfil}\hfil#2\hfil\box1\fi%
}}}}

{\catcode`\@=11
\gdef\sethd#1#2#3{%
\def\@oddhead{\vbox{\hbox to\hsize{{#1}\hfil{#2}\hfil{#3}}%
\vspace{0.06in}%
\hbox to \hsize{\hrulefill}\vspace*{-0.09in}}}
\def\@evenhead{\@oddhead}
	}
}

\def\reals{\mathbb{R}}
\def\sphere{\mathbb{S}}
\def\xx{\mathbf{x}}
\def\norm#1{\Vert #1 \Vert}
\def\hint#1{(\textbf{Hint:} #1)}
\def\floor#1{\lfloor #1 \rfloor}
\def\ceiling#1{\lceil #1 \rceil}

\DeclareMathOperator*{\argmin}{arg\,min}



\marginparsep=1pt
\oddsidemargin=0.25in
%
%%%%%% A few macros %%%%%%%%%%%%%%%%
\newtheorem{probm}{Problem}
\newenvironment{prob}{\noindent{\bf Problem \addtocounter{probm}{1}
\hspace{-1mm}\theprobm:\hspace{2mm}}}{\vspace{2mm}}

\def\hint#1{\noindent ({\bf Hint:} {\it #1})}
\def\eps{\varepsilon}
\def\conv{\mathop{\mathrm{conv}}}

\parskip=2mm
\sethd{{\sc Assignment 5}}{}{{\sc Course: COMPSCI531D}}
\setft{{\sc Fall 2021}}{{\sc Introduction to Algorithms}}{{\sc Page \thepage}}

\begin{document}
\vspace*{2mm}

\noindent\textbf{Due Date: October 21, 11:59pm}

\noindent In all problems, prove the correctness of your algorithm and analyze its running time.

\begin{prob}[10pts]
Consider a simplified phone network, with $n$ base stations specified as points $b_1, \dots, b_n$ and $n$ cellular phones specified as points $p_1, \dots, p_n$ in the plane, as well as a range parameter $r > 0$. A set of cell phones are \emph{fully connected} if there is an assignment of phones to stations such that 
\begin{itemize}
	\item Each phone is assigned to a different base station, and
	\item If $(p_i, b_j)$ is in the assignment, then the Euclidean distance between $p_i$ and $b_j$ is at most $r$.
\end{itemize}
Suppose that the owner of the phone located at $p_1$ travels continuously for a total of $z$ units of distance due east. Give an $O(n^3)$-time algorithm to decide whether it is possible to keep the set of phones fully connected at all times during the travel. 

\end{prob}

\begin{prob}[10pts]
	Suppose we are given an array $A[1..m][1..n]$ of non-negative real numbers. We want to round $A$ to an integer matrix, by replacing each entry $x$ in $A$
	with either $\floor x$ or $\ceiling x$, without changing the sum of entries in any row or column of A. For example,
	\[\begin{bmatrix} 
		1.2 & 3.4 & 2.4 \\ 
		3.9 & 4.0 & 2.1 \\
		7.9 & 1.6 & 0.5	
	\end{bmatrix} \mapsto 
	\begin{bmatrix} 
		1 & 4 & 2 \\ 
		4 & 4 & 2 \\
		8 & 1 & 1	
	\end{bmatrix}\]

	\begin{enumerate}[label=(\alph*)]
		\item {[5pts]} Describe an efficient algorithm that either rounds $A$ in this fashion, or reports that no such rounding exists. 
		\item {[5pts]} Prove that a legal rounding is possible \emph{if and only if} the sum of entries in each row is an integer, and the sum of entries in each column is an integer. In other words, prove that either your algorithm from part (a) returns a legal rounding, or a legal rounding is \emph{obviously} impossible.
	\end{enumerate}
\end{prob}

\begin{prob}[10pts]
	A \emph{cycle cover} of a given directed graph $G=(V,E)$ is a set of vertex-disjoint cycles that cover every vertex in $G$. Describe an efficient algorithm to find a cycle cover for a given graph, or correctly report that no cycle cover exists. \hint{Use bipartite matching.}
\end{prob}



\end{document}
