\documentclass[12pt]{article}
\usepackage[margin=1in]{geometry} 
\usepackage{amsmath,amsthm,amssymb,amsfonts}
\usepackage{graphicx,fancyhdr,algorithm,algorithmic}
\usepackage[space]{grffile}
\usepackage{titlesec}
\usepackage{multicol}
\usepackage{enumitem} 


\cfoot{\thepage}
\renewcommand{\headrulewidth}{0.4pt}
\renewcommand{\headwidth}{\textwidth}
\renewcommand{\footrulewidth}{0.4pt}


\theoremstyle{definition}
\newtheorem{problem}{Problem}
\newtheorem{claim}{Claim}
\newtheorem{definition}{Definition}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{observation}{Observation}
\newtheorem{question}{Problem}

\newenvironment{solution}{\bigskip\noindent{\it Solution.}  \ignorespaces}{\hfill\qed}

\usepackage{hyperref}
\hypersetup{
    colorlinks=true,
    linkcolor=blue,
    filecolor=magenta,      
    urlcolor=cyan,
}
\urlstyle{same}
\PassOptionsToPackage{hyphens}{url}
\newcommand{\homework}[6]{
   \pagestyle{myheadings}
   \thispagestyle{plain}
   \newpage
   \setcounter{page}{1}
   \noindent
   \begin{center}
   \framebox{
      \vbox{\vspace{2mm}
    \hbox to 6.28in { {\bf CS 256:~Algorithm Design and Analysis \hfill} }
       \vspace{6mm}
       \hbox to 6.28in { {\Large \hfill #1 \normalsize{(#2)}  \hfill} }
       \vspace{6mm}
     \hbox to 6.28in { {\it Instructor: #3 \hfill } }
   }
   }
   \end{center}
   \markboth{#1}{#1}
   \vspace*{4mm}
}



\begin{document}
%\homework{Assignment 3}{due 10/07/20}{Sam McCauley}{}{}{}
\homework{Greedy Algorithms Practice}{\textcolor{red}{Optional!}}{Sam McCauley}{}{}{}

\noindent
%All problems are worth 10 points.  Latex typsetting is worth 5 points.

\smallskip

\subsection*{Greedy Stays Ahead and Exchange Argument}

\begin{question}
Let $X$ be a set of $n$ intervals on the real line. We say that a set $P$ of points
stabs $X$ (or is \emph{the stabbing set}) if every interval in $X$ contains at least one point in $P$. See Figure~\ref{fig:stabbing}. In this and the next question, we will design and analyze an efficient algorithm to compute minimum set of points that
stabs $X$. Assume that your input consists of pairs ($\ell_i$, $r_i$), representing the left and right endpoints of $i$th interval in $X$, for $1\leq i \leq n$. 

\begin{figure}[h]\label{fig:stabbing}
\centering
\includegraphics[scale=0.15]{stabbing.png}\caption{A set of intervals stabbed by four points. From Jeff Erickson's \href{www.algorithms.wtf}{Algorithms book}.}
\end{figure}
\vspace{-10pt}



\begin{enumerate}[noitemsep, label = (\alph*), leftmargin=*]
 

 

    \item\label{parta} \emph{Structure of optimal.} If we were to choose stabbing points anywhere on the intervals, the possibilities would be endless.  So first, we prove a structural property about any optimal solution to the problem, as this will guide our algorithm design.  Show that for any set of intervals, there exists an optimal solution (a stabbing set of minimum size) where every stabbing point is the right endpoint $r_i$ of some interval. This means that without loss of generality (WLOG), we can restrict ourselves to stabbing sets that satisfy this property. 
 
\end{enumerate}
\noindent
Consider the following greedy strategy: sort the intervals in increasing order of their right endpoints. Take the first interval from this list, and add its right endpoint to the stabbing set. Remove all intervals that contain this point. Repeat until no intervals remain. Clearly, this produces a valid stabbing set, but is it optimal?

\begin{itemize}[noitemsep, leftmargin=*]

         
     \item[(b)]  \emph{Greedy is optimal.} Prove that the above greedy strategy is optimal, i.e., it produces a stabbing set of minimum size. (\emph{Hint.} Use~\ref{parta} and compare to an optimal solution where every stabbing point is a right endpoint of some interval.)
 

   \item[(c)] \emph{Running time of greedy.} Analyze the running time of the greedy strategy and show that it can be implemented in $O(n \log n)$ time.


\end{itemize} 
\end{question}
\begin{solution}
\end{solution}

\newpage
\begin{question}[K-T 4.9]
	One of the basic motivations behind the Minimum Spanning Tree problem is the goal of designing a spanning network for a set of nodes with minimum \emph{total} cost.  Here we explore another type of objective: designing a spanning network for which the \emph{most expensive} edge is as cheap as possible.

	Specifically, let $G=(V,E)$ be a connected graph with $n$ vertices, $m$ edges, and positive edge costs that you may assume are all distinct.  Let $T = (V,E')$ be a spanning tree of $G$; we define the \emph{bottleneck edge} of $T$ to be the edge of $T$ with the greatest cost.

	A spanning tree $T$ of $G$ is a \emph{minimum-bottleneck spanning tree} if there is no spanning tree $T'$ of $G$ with a cheaper bottleneck edge.
	\begin{itemize}
		\item Is every minimum-bottleneck tree of $G$ a minimum spanning tree of $G$?  Prove or give a counterexample.

\begin{solution}
\end{solution}
		\item Is every minimum spanning tree of $G$ a minimum-bottleneck tree of $G$?  Prove or give a counterexample.

\begin{solution}
\end{solution}
	\end{itemize}
\end{question}

\end{document}

