\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 2016}
\sethwnum{7}
\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 21, 2016. \\Submit PDF solutions on
Canvas by the \\
beginning of class on May 3, 2016.}
\maketitle
\paragraph{Instructions:}
\begin{itemize}
\item You can pair up with another student to solve the homework. You
are allowed to discuss possible algorithms and approaches and bounce ideas with your
team-mate. \textbf{Do not discuss proofs of correctness or running time in
detail with your team-mate. Do not send a written solution to your
team-mate for any reason whatsoever.} Please form teams yourselves. Of course,
you can ask me for help if you cannot find a team-mate. You may choose
to work alone. \emph{Each of you must write down your solution
individually, and write down the name of the other member in your
team. If you do not have a team-mate, please say so.} \textbf{If
your solution is largely identical to that of your team-mate or
another student, we will return it ungraded.}
\item Apart from your team-mate, you are not allowed to consult any
sources other than your textbook, the slides on the course web page,
your own class notes, the TAs, and the instructor. In particular, do
not use a search engine.
\item Do not forget to typeset your solutions. \emph{Every mathematical
expression must be typeset as a mathematical expression, e.g., the
square of $n$ must appear as $n^2$ and not as ``n\^{}2''.} Students
can use the \LaTeX\ version of the
homework problems to start entering their solutions.
\item Describe your algorithms as clearly as possible. The style used in
the book is fine, as long as your description is not
ambiguous. Explain your algorithm in words. A step-wise description is
fine. \emph{However, if you submit detailed pseudo-code without an
explanation, we will not grade your solutions.}
\item Do not make any assumptions not stated in the problem. If you do
make any assumptions, state them clearly, and explain why the
assumption does not decrease the generality of your solution.
\item Do not describe your algorithms only for a specific example you
may have worked out.
\item You must also provide a clear proof that your solution is correct
(or a counter-example, where applicable). Type out all the statements you
need to complete your proof. \emph{You must convince us that you can
write out the complete proof. You will lose points if you work out
some details of the proof in your head but do not type them out in
your solution.}
\item Describe an analysis of your algorithm and state and prove the
running time. You will only get partial credit if your analysis is not
tight, i.e., if the bound you prove for your algorithm is not the best
upper bound possible.
\item For the problems in Chapter 8, please describe the reduction as
clearly as you can and make you sure you prove the correctness of the
reduction in both directions, as we have discussed in class.
\end{itemize}
\begin{description}
\item[Problem 1] (20 points) Solve exercise 1 in Chapter 8 (page 505) of
your textbook.
% \solution{
% }
\item[Problem 2] (30 points) Solve exercise 3 in Chapter 8 (pages 505--506) of
your textbook.
% \solution{
% }
\item[Problem 3] (50 points = 25 + 25 points) Solve exercise 19 in Chapter 8 (pages
514--515) of your textbook. \emph{Hint:} You can reduce 3-colouring to
one problem (I am not saying which) and the other problem to network flow.
% \solution{
% }
\item[Problem 4] (\textbf{Extra credit}: 30 points) Solve exercise 6 in Chapter 8 (page 507) of
your textbook. \emph{Hint:} think of monotone satisfiability as a
covering problem: you have to find a small number of Boolean variables
that together satisfy or ``cover'' all the clauses.
% \solution{
% }
\end{description}
\end{document}
%%% Local Variables:
%%% mode: latex
%%% TeX-master: t
%%% End: