\documentclass{article}
\usepackage[top=1in,bottom=1in,left=1in,right=1in]{geometry}
\usepackage{fancyheadings,enumerate,xspace}
\pagestyle{fancy}
\chead{CS 4104 (Fall 2009): Homework 3}
\newcommand{\solution}[1]{\textbf{Solution:} #1}
\newcommand{\cut}[1]{\ensuremath{\mathnormal{}{cut}(#1)}}
\newcommand{\calg}{\ensuremath{{\cal G}}\xspace}
\newcommand{\calo}{\ensuremath{{\cal O}}\xspace}
\begin{document}
\title{\vspace{-0.5in}\textbf{Homework 3}}
\author{CS 4104 (Fall 2009)}
\date{Assigned on Wednesday, September 16,
2009. \\Hardcopy due at the beginning of class on Wednesday, September
23, 2009.}
\maketitle
\begin{description}
\item[Problem 1] (10 points) Solve exercise 2 in Chapter 4 (page 189)
of of ``Algorithm Design'' by Kleinberg and Tardos.
% \solution{
% }
\item[Problem 2] (35 points) Solve exercise 5 in Chapter 4 (pages
190-191) of ``Algorithm Design'' by Kleinberg and Tardos. Just in case
the problem statement is not completely clear, you can assume that the
road is the $x$-axis, that each house lies directly on the
road, and that the position of each house is specified by its
$x$-coordinate.
% \solution{
% }
\item[Problem 3] (45 points) Solve exercise 13 in Chapter 4 (pages
194-195) of of ``Algorithm Design'' by Kleinberg and
Tardos. \emph{Hint:} One of the key issues in solving this problem is
figuring out what measure to sort all the jobs by. For each job $i$,
define this unknown quantity to be $q_i$. Now try to use one of the
techniques we have seen for proving the correctness of greedy
algorithms. Working ``backwards'' from what you need to prove might
help you to discover what $q_i$ should be and thereby define the
algorithm.
% \solution{
% }
\end{description}
\end{document}