\documentclass[10pt,letterpaper,unboxed,cm]{hmcpset}
\usepackage[margin=1in]{geometry}
\usepackage{graphicx}
\usepackage{enumerate}
\newcommand{\st}{~\mid~}
\newcommand{\ind}{$~~~$}
\name{}
\class{CSE 101 Fall 2018}
\assignment{Homework 4}
\duedate{Due: Tuesday, October 30, 2018 at 11:59pm}
\begin{document}
\begin{center}
\begin{minipage}[t]{5.7in}
\rule{\linewidth}{2pt}
{\sc Instructions}\newline
This homework assignment may be completed in groups of size 1-4. The solutions must be {\bf typed} (using a computer.) Figures and graphs can be hand drawn. For algorithm descriptions we require a high-level English description AND an implementation description. If you find it necessary to also include a pseudo code to help understand your description then feel free to include it.
\newline\newline
Please refer to the course page for requirements in writing up answers for algorithm questions.
\rule{\linewidth}{2pt}
\end{minipage} \hfill
\end{center}
\begin{enumerate}
%FIRST PROBLEM
\item
Consider the problem where you are finding a spanning tree of a graph, but instead of minimizing the
total weight, you want an MST that minimizes the maximum weight of an edge in the graph. Show
that Kruskal's algorithm also is optimal for this objective function.(25 points)
\bigskip
%SECOND PROBLEM
\item
You are given an undirected connected graph $G = (V,E)$ with positive edge weights, and a minimum spanning tree $T = (V,E'$) with respect to these weights; you may assume $G$ and $T$ are given as adjacency lists. Now suppose the weight of a particular edge $e\in E$ is modiﬁed from $w(e)$ to a new value $\hat{w}(e)$. You wish to quickly update the minimum spanning tree $T$ to reﬂect reflect this change, without recomputing the entire tree from scratch. There are four cases. In each case give a linear-time algorithm for updating the tree. (no correctness proof necessary. Please justify the runtime.)(25 points)
\begin{enumerate}
\item
$e\notin E'$ and $\hat{w}(e)>w(e)$
\item
$e\notin E'$ and $\hat{w}(e)w(e)$
\end{enumerate}
%THIRD PROBLEM
\item
In this problem, we will develop a new algorithm for finding minimum spanning trees. It is based upon the following property:
\begin{quote}
Let $G$ be an undirected connected graph with at least one cycle.\\
Pick a cycle in $G$, and let $e$ be the heaviest edge in that cycle. Then there is a minimum spanning tree that does not contain $e$.
\begin{enumerate}
\item (8 points)
Prove this property.
\item (7 points)
Here is the new MST algorithm.
\begin{quote}
\texttt{\underline{procedure new\_MST}}$(G=(V,E)$; an undirected connected graph with positive edge weights $\{w_e\}$.)\\
\texttt{sort the edges according to their weights}\\
\texttt{for each edge }$e\in E$\texttt{ in decreasing order of weights:}\\
\ind\texttt{if }$e$\texttt{ is part of a cycle of }$G$:\\
\ind\ind $G=G-e$\texttt{ (that is, remove }$e$\texttt{ from }$G$)\\
\texttt{return }$G$
\end{quote}
Prove the correctness of this algorithm.
\item (5 points)
On each iteration, the algorithm must check if $e$ is part of a cycle of $G$. Give a linear time algorithm to do this.
\item (5 points)
Calculate the runtime of this algorithm in terms of $|E|$.
\end{enumerate}
\end{quote}
\bigskip
% FOURTH PROBLEM
\item
Spectrum:
You want to create a scientific laboratory capable of monitoring
any frequency in the electromagnetic spectrum between $L$ and
$H$. You have a list of possible monitoring technologies, $T_i$,
$i=1,..n$,
each with an interval
$[l_i,h_i]$ of frequencies that it can
be used to monitor. You want to pick as few as possible technologies
that together cover the interval $[L,H]$.
\par
Candidate Greedy Strategy I:
First, buy the technology that covers the longest sub-interval
within $(L,H)$. (i.e.,The longest interval $(l,h)$, but not including
the sub-intervals $(l,L)$ and $(H,h)$ outside the interval we
need covering.)
At each subsequent step, buy the technology that covers the largest total
length that is still uncovered.
\par
Candidate Greedy Strategy II:
Look at all the technologies with $l \le L$. Of these, buy the one
$T_i=(l_i,h_i)$ with the largest value of $h_i$. Repeat the
process to cover the remaining interval, $(h_i,H)$. \\
(8 points for arguing the optimal algorithm, 9 points for proof of correctness, 8 points for time analysis, space analysis and efficiency.)
\end{enumerate}
\end{document}