\documentclass[12pt,oneside]{article}

\usepackage{amsmath}
\usepackage{booktabs}
%\usepackage[onlytext]{MinionPro}
\usepackage[letterpaper, margin=1in]{geometry}
\usepackage{enumitem}
\usepackage{graphicx}
\usepackage{hyperref}
\usepackage{fancyvrb}

\def\compare{ {\mathrm{compare}} }
\def\swap{ {\mathrm{swap}} }
\def\sort{ {\mathrm{sort}} }
\def\true{ {\mathrm{true}} }
\def\false{ {\mathrm{false}} }
\def\MergeSort{\mathrm{MergeSort}}
\def\QuickSort{\mathrm{QuickSort}}
\def\InsertionSort{\mathrm{InsertionSort}}
\def\RadixSort{\mathrm{RadixSort}}


%% \setlength{\topmargin}{-0.75in}
%% \addtolength{\textheight}{2.00in}
%% \setlength{\parindent}{0in}
\pagestyle{empty}

\begin{document}

\begin{center}
  {\Large Homework 04}\hfill\emph{COSC 311: Algorithms}, Fall 2022\\
  \hrule
\end{center}

\vspace{0.5em}

\noindent\textbf{Due:} Friday, 10/28/2022 at 11:59 pm

\vspace{2em}

\noindent\textbf{Exercise 1.} Imagine you are working on a long-term building project that lasts $N$ consecutive days. Each day, the project must be staffed by a contractor. You receive a large number of bids from contractors to staff the project, where each bid consists of:
\begin{itemize}
\item a start date $s $ satisfying $1 \leq s \leq N$ when the contractor is available to start working,
\item a termination date $t $ satisfying $s \leq t \leq N$ which is the last date the contractor is available to work, and
\item a cost $w $ for the contractor to work all days in the range $[s, t]$.
\end{itemize}
That is, a contractor's bid consists of an interval $[s, t]$ and the associated cost $w $ to hire the contractor for that interval. If a contractor is hired at all, they \emph{must} work for the entire bid interval $[s, t]$. Your goal is to choose a set of contractors to hire according to the following criteria:

\begin{enumerate}
\item Every day $i = 1, 2, \ldots, N$ must be staffed by some contractor.
\item No day can be staffed by more than one contractor.
\item You wish to minimize the total cost to hire the contractors subject to satisfying constraints 1 and 2.
\end{enumerate}

For example, suppose $N = 10$ and you receive the following bids:

\begin{enumerate}
\item cover days $[1, 2]$ for a cost of $240$
\item cover days $[9, 10]$ for a cost of $320$
\item cover days $[3, 8]$ for a cost of $600$
\item cover days $[3, 5]$ for a cost $300$
\item cover days $[6, 8]$ for a cost of $280$
\end{enumerate}
Then there are two ways of satisfying the constraints above:
\begin{itemize}
\item hire contractors $1, 3, 2$ for a total cost of $1160$, or
\item hire contractors $1, 4, 5, 2$ for a total cost of $1140$.
\end{itemize}
The second option is cheaper, so you should hire those contractors.

Given $N $ and a set $B $ of bids, define a (directed) graph $G = (B, E)$ with vertex set $B $ as follows: given two bids $u, v \in B$ there is an edge from $u $ to $v $ if $u $'s termination date is the day before $v $'s start date.

\begin{enumerate}
\item Draw the graph $G $ corresponding to the example above with $5 $ bids.
\item Given a graph $G $ constructed as above, how could you determine if there is \emph{any} feasible assignment of contractors that satisfy constraints 1 and 2 above. (You do not need to devise an explicit algorithm. It is enough to describe what features of $G $ determine whether or not a feasible assignment exists.)
\item Suppose you receive $n $ bids so that $G $ has $n $ vertices. Devise an algorithm that finds a minimum cost assignment of contractors, or reports that no feasible assignment exists. The running time of your algorithm should be at most $n^3 \log n$. You may use any algorithm described so far in class as subroutines, so long as you accurately state its running time.
\end{enumerate}

\vspace{1em}

\noindent\textbf{Exercise 2.} The bucolic town of Tashmer consists of one long highway dotted with farmhouses, a few storefronts, and civic buildings. A single water main stretches the length the highway, and provides water to the entire town. The county fire code requires that a fire hydrant be placed along the water main within 150 meters of every occupied building. Installing fire hydrants is expensive, so the town would like to minimize the number of hydrants installed. Devise an algorithm that determines the placement of fire hydrants that minimizes the total number of hydrants subject to the constraint that every occupied building is within 150 meters of a hydrant. 

Specifically, your algorithm should take as input an array $a $ of locations of occupied buildings.  That is, $a[i]$ is the distance (in meters) of the $i $th occupied building from the town line along the highway. Your algorithm should output a list of locations $h_1 < h_2 < \cdots < h_k$ of fire hydrants such that for every building location $a[i]$ there is a fire hydrant location $h_j$ satisfying $\vert a[i] - h_j\vert \leq 150$. In addition to a precise description of your procedure (i.e., through pseudocode), you should include an argument as to why your algorithm produces the minumum number of hydrants. Be sure to include the running time of your procedure as well.

\end{document}
