\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:
