\documentclass{article}
\usepackage[top=1in,bottom=1in,left=1in,right=1in]{geometry}
\usepackage{fancyheadings,enumerate,xspace,graphicx}
\pagestyle{fancy}
% macros useful for handouts and homeworks.
\newcommand{\setcourse}[1]{\newcommand{\course}{#1\xspace}}
\newcommand{\setsem}[1]{\newcommand{\sem}{#1\xspace}}
\newcommand{\sethwnum}[1]{\newcommand{\hwnum}{#1\xspace}}
\newcommand{\solution}[1]{\textbf{Solution:} #1}
\setcourse{CS 4104}
\setsem{Spring 2017}
\sethwnum{6}
\newcommand{\cut}[1]{\ensuremath{\mathnormal{}{cut}(#1)}}
\newcommand{\calg}{\ensuremath{{\cal G}}\xspace}
\newcommand{\calo}{\ensuremath{{\cal O}}\xspace}
\chead{\course (\sem): Homework \hwnum}
\begin{document}
\title{\vspace{-0.5in}\textbf{Homework \hwnum}}
\author{\course (\sem)}
\date{Assigned on April 17, 2017. \\Submit PDF solutions on Canvas by the
\\ beginning of class on April 24, 2017.}
\maketitle
\input{instructions}
\noindent \textbf{Additional notes.}
\begin{itemize}
\item For many of the problems in Chapter 7, you will reduce
the given problem to one of the flow-related problems we solved in
class. Make sure you describe the reduction completely. For example,
if you reduce a problem to the maximum network flow problem itself, specify
clearly how will convert an input to the original problem into a flow
network (nodes, source and sink, edges, directions, and edge
capacities). Do not forget to the prove the correctness of your
solution in both directions, as we did in class (lest you transmogrify
Calvin-sized Hobbes into a dinosaur).
\item For some of the problems in Chapter 7, you do not have to reduce
the problem ``all the way'' to computing the maximum flow in a
network. A reduction to maximum bipartite matching or to minimum cut
may suffice. You can then use the polynomial time algorithms we have
developed for these problems to solve the original problem. In other
words, you do not have to also describe how to reduce maximum
bipartite match matching or minimum cut to the maximum flow problem.
\end{itemize}
\begin{description}
\item[Problem 1] (10 points) Solve exercise 4 in Chapter 7 (page 416) of
your textbook.
% \solution{
% }
\item[Problem 2] (10 points) Solve exercise 5 in Chapter 7 (page 416) of
your textbook.
% \solution{
% }
\item[Problem 3] (35 points) Solve exercise 6 in Chapter 7 (pages 416--417) of
your textbook.
% \solution{
% }
\item[Problem 4] (45 points, 30 points for part(a) and 15 points for
part (b))\footnote{For part(b), you need to modify the solution for
part (a), so the 15 points are for this modification.} Solve
exercise 19 in Chapter 7 (pages 425--426) of your textbook.
% \solution{
% }
\end{description}
\end{document}
%%% Local Variables:
%%% mode: latex
%%% TeX-master: t
%%% End: