% ---------
%  Compile with “pdflatex hw0”.
% --------
%!TEX TS-program = pdflatex
%!TEX encoding = UTF-8 Unicode

\documentclass[11pt]{article}
\usepackage{jeffe,handout,graphicx,mathtools}
\usepackage[mathletters]{ucs}	% define text Greek letters; load BEFORE inputenc
\usepackage[utf8x]{inputenc}	% Allow some non-ASCII Unicode in source
\usepackage{fourier-orns}
\usepackage{eucal}

\usepackage{enumerate}
\usepackage{stmaryrd}

%\hidesolutions

% ======================================================
\begin{document}

\headers{CS 473}{Homework 7 (due March 29)}{Spring 2016}
\thispagestyle{empty}

\begin{center}
\Large\textbf{CS 473 \,\decosix\,  Spring 2016}%
\\
\LARGE \textbf{\decothreeleft~ Homework 7 ~\decothreeright}
\\[0.5ex]
\large Due Tuesday, March 29, 2016, at 8pm
\end{center}

\hrule
\begin{center}
\textbf{This is the last homework before Midterm 2.}
\end{center}
\hrule
\bigskip

\begin{enumerate}
\parindent 1.5em \itemsep 3ex plus 0.5fil

\item
Suppose we are given a two-dimensional array $A[1\,..\,m,1\,..\,n]$ of non-negative real numbers.  We would like to \emph{round} $A$ to an integer matrix, by replacing each entry $x$ in $A$ with either $\floor{x}$ or $\ceil{x}$, without changing the sum of entries in any row or column of $A$.  For example:
\[
	\def\arraystretch{1.2}
	\begin{bmatrix}
		1.2 & 3.4 & 2.4 \\
		3.9 & 4.0 & 2.1 \\
		7.9 & 1.6 & 0.5
	\end{bmatrix}
	\longmapsto
	\begin{bmatrix}
		1 & 4 & 2 \\
		4 & 4 & 2 \\
		8 & 1 & 1
	\end{bmatrix}
\]
Describe and analyze an efficient algorithm that either rounds $A$ in this fashion, or reports correctly that no such rounding exists.


\item
You're organizing the Third Annual UIUC Computer Science 72-Hour Dance Exchange, to be held all day Friday, Saturday, and Sunday in Siebel Center.\footnote{Efforts to secure overflow space in ECEB were sadly unsuccessful.}  Several 30-minute sets of music will be played during the event, and a large number of DJs have applied to perform.  You need to hire DJs according to the following constraints.
\begin{itemize}
\item
Exactly $k$ sets of music must be played each day, and thus $3k$ sets altogether.
\item
Each set must be played by a single DJ in a consistent musical genre (ambient, bubblegum, dancehall, horrorcore, trip-hop, Nashville country, Chicago blues, axé, laïkó, skiffle, shape note, Nitzhonot, J-pop, K-pop, C-pop, T-pop, 8-bit, Tesla coil, \dots).
\item
Each genre must be played at most once per day.
\item
Each DJ has given you a list of genres they are willing to play.
\item
No DJ can play more than five sets during the entire event.
\end{itemize}
Suppose there are $n$ candidate DJs and $g$ different musical genres available.  Describe and analyze an efficient algorithm that either assigns a DJ and a genre to each of the $3k$ sets, or correctly reports that no such assignment is possible.


\item 
Describe and analyze an algorithm to determine, given an undirected\footnote{This adjective is important; if the input graph were directed, this problem would be NP-hard.} graph $G = (V, E)$ and three vertices $u, v, w \in V$ as input, whether $G$ contains a simple path from $u$ to $w$ that passes through $v$.

\end{enumerate}



\end{document}
