% ---------
% 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}