\documentclass{article}
\usepackage{amsthm, amssymb, amsmath,verbatim}
\usepackage[margin=1in]{geometry}
\usepackage{enumerate}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\F}{\mathbb{F}}
\newcommand{\N}{\mathbb{N}}
\newtheorem*{claim}{Claim}
\newtheorem{ques}{Question}
\title{CSE 101 Homework 5}
\date{Winter 2021}
\begin{document}
\maketitle
This homework is due on gradescope Friday February 26th at 11:59pm pacific time. Remember to justify your work even if the problem does not explicitly say so. Writing your solutions in \LaTeX is recommend though not required.
\begin{ques}[Minimum Spanning Subgraph, 30 points]
When introducing the Minimum Spanning Tree problem, we considered the problem of finding the least costly set of edges that connects a graph $G$. We showed that if the edge weights are all non-negative that these edges would necessarily form a tree. However, if negative edge weights are allowed, this no longer needs to be the case. Give an algorithm that given a weighted, undirected graph $G$, provides a subset $S$ of edges so that any vertex in $G$ can be reached from any other using only edges in $S$ and so that subject to this, the total weight of $S$ is as small as possible. For full credit, your algorithm should run in time $O(|V|\log(|V|)+|E|)$ or better.
\end{ques}
\begin{ques}[Multiple MSTs, 40 points]
\begin{enumerate}[(a)]
\item Give an example of a graph that has more than one minimum spanning tree. [5 points]
\item Show that for any graph $G$ with minimum spanning trees $T$ and $T'$ that for each weight $w$, $T$ and $T'$ contain the same number of edges of weight $w$. Hint: Run an exchange-like argument to slowly turn $T$ into $T'$ without changing the number of edges of any weight. [35 points]
\end{enumerate}
\end{ques}
\begin{ques}[LCSS without Double Letters, 30 points]
Say that a string has a double letter if two consecutive letters in the string are the same. Give an algorithm that given two strings of length $n$, $A=a_1a_2\ldots a_n$ and $B=b_1b_2 \ldots b_n$, finds the longest sequence $C=c_1c_2\ldots c_m$ so that $C$ is a subsequence of both $A$ and $B$ and has no double letters. For full credit, your algorithm should run in time $O(n^3)$ or better.
\end{ques}
\begin{ques}[Extra credit, 1 point]
Approximately how much time did you spend working on this homework?
\end{ques}
\end{document}