Include the answer to second question

2 files changed, 38 insertions, 0 deletions

diff --git a/answer_sheet/main.pdf b/answer_sheet/main.pdf
index 26316cd..7e9b4c4 100644
--- a/answer_sheet/main.pdf
+++ b/answer_sheet/main.pdf
diff --git a/answer_sheet/main.tex b/answer_sheet/main.tex
index f9cd5d4..002a755 100644
--- a/answer_sheet/main.tex
+++ b/answer_sheet/main.tex
@@ -60,5 +60,43 @@ Formally, the algorithm we propose simply sorts the $f_i \in f$ in $\mathcal{O}(
     \label{fig:1_cases}
 \end{figure}
 
+\section{Spanning Tree}%
+\label{sec:spanning_tree}
+
+In this question, leveraging the discussion on the \href{https://odtuclass.metu.edu.tr/mod/forum/discuss.php?d=14248}{lecture forum}, we know that there are $n = |E|$ edges in $G = (V, E)$ in which $k + \delta$ edges are red and the rest are white.
+$k$ is not given as an input in the question text but we will assume so to continue with the discussion, otherwise the algorithm cannot be properly stated.
+
+Given $G = (V, E)$ where $ r \le |E|$ edges are red, can we find $k$ such edges that form a spanning tree.
+
+We will start by running Kruskal's algorithm on $G$ with a modification; we will assign a positive weight $\gamma$ on every \emph{white} edge and $0$ on every \emph{red} edge.
+Kruskal's algorithm will pick only red edges as a result.
+This will either;
+
+\begin{itemize}
+    \item yield a MST with less than $k$ edges. In this case, we can state no such tree with $k$ red edges exists and report this per case (ii) in the question text.
+    \item yield a MST with \emph{exactly} $k$ edges, which we can return immediately per case (i) in the question text.
+    \item yield a MST with more than $k$ edges, which we will have to continue operating with.
+\end{itemize}
+
+Since we are continuing with the algorithm, we can name the minimum spanning tree we got from the steps above $T_{r}$.
+
+At this point, we should prepare another MST using only white edges. Since the MST we are aiming to return at the end of the algorithm does not have to consists of only red edges, we can substitute white edges with respect to either Cut Property or Cycle Property as given in the Greedy Algorithms II lecture notes.
+
+We will prepare a MST with only white edges by setting the weights of white edges on $G$ to 0 and red edges on $G$ to $\beta$ and running Kruskal's algorithm on $G$.
+Kruskal's algorithm will pick only white edges as a result and we will call this tree $T_{w}$.
+If $T_{w}$ does not contain at least $k - E'$ for $T_{r} = (V, E')$ edges we will conclude that no such tree exists and report per case (ii).
+
+Now, with $T_{r}$ and $T_{w}$, we are aiming to reduce the number of red edges in $T_{r}$ to $k$ by removing a red edge from it and connecting the tree back using a white edge from $T_{w}$.
+Since both $T_{r}$ and $T_{w}$ are MST, they have $V-1$ edges, removing any edge will disconnect the tree and adding any edge will introduce a cycle, per the definition of trees.
+
+Our algorithm is then as follows;
+\begin{enumerate}
+    \item Remove an edge $e \in E(T_{r})$ that is not in $T_{w}$.
+    \item We can add $e$ to $T_{w}$ but this will introduce a cycle (per above). However, we can pick an edge in the newly introduced cycle in $T_{w}$ that is not in $T_{r}$ and add that edge $e'$ to $T_{w}$. We are able to do this since trees cannot contain cycles hence at least one of the edges in the newly introduced cycle has to be missing from $T_{r}$.
+    \item When we have $k$ red edges (and $V - k - 1$ white edges) in $T_{r}$, then we can report it per case (i).
+\end{enumerate}
+
+The cycle checking step, step 2 in the algorithm above uses the Union Find. Since we did not go into the detail of Union Find in the lectures we will use the naive approach which uses $\mathcal{O}(n^{2})$ operations. On top of that, we have to run Kruskal's algorithm twice for $T_{r}$ and $T_{w}$ which runs in order $\mathcal{O}(k\log(n))$ ($k$ can be substituted with the number of white edges, if higher). Overall, the runtime of the algorithm is $\mathcal{O}(n^{2} k\log(n))$.
+
 
 \end{document}