\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{Fall 2009}
\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 November 20, 2009. \\Hardcopy due at the
beginning of class on December 2, 2009.}
\maketitle
\paragraph{Instructions:}
\begin{itemize}
\item \textbf{In this homework, we will continue with the policy of
working in teams of two students.} You can pair up with another
student to solve the homework. You are allowed to discuss possible
algorithms and bounce ideas with your team-mate. Do not discuss proofs
of correctness or running time in detail with your
team-mate. \emph{Each student must write his/her solution
individually, and write down the name of the other member in your
team.} 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.
\item Your team is not allowed to consult any sources other than your
textbook, the slides on the course web page, your own class notes, the
TA, 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
using \LaTeX\ or LyX can use the corresponding versions 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 Analyse your algorithm and state 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.
\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] (30 points) Solve exercise 6 in Chapter 7 (pages 416--417) of
your textbook.
% \solution{
% }
\item[Problem 4] (30 points) Solve exercise 7 in Chapter 7 (pages
417--418) of your textbook.
\item[Problem 5] (20 points) Solve exercise 12 in Chapter 7 (page 420)
of your textbook.
\end{description}
\end{document}