From 7d53703da35a3549805deda36b1c9a2eb7267fde Mon Sep 17 00:00:00 2001
From: Camil Staps
Date: Sun, 29 Nov 2015 15:27:15 +0100
Subject: finish assignment 11

---
 assignment11.tex | 18 +++++++++++++++++-
 1 file changed, 17 insertions(+), 1 deletion(-)

diff --git a/assignment11.tex b/assignment11.tex
index eec7ccb..ac824df 100644
--- a/assignment11.tex
+++ b/assignment11.tex
@@ -103,7 +103,23 @@
 
         \end{enumerate}
 
-    \item %todo
+    \item \begin{enumerate}
+            \item Start with the set of intervals $I=\emptyset$. While $S$ is non-empty:
+                \begin{enumerate}[ref=\roman*]
+                    \item Extract the smallest $x_i$ from $S$.
+                    \item Add $[x_i,x_i+1]$ to $I$. \label{11-5-a-choice}
+                    \item Remove all $x_j$ with $x_j \in [x_i,x_i+1]$ from $S$.
+                \end{enumerate}
+                Return $I$.
+
+            \item \begin{proof}
+                    Suppose the algorithm was not correct. Then in step \ref{11-5-a-choice} we could have chosen a different interval containing $x_i$, all the $x_j$ from the next step \emph{and} at least one other $x_j'$. However, any other option for an interval would have a lower lower bound and a lower upper bound. Therefore, $x_j'<x_i$. However, since $x_i$ is minimal, this $x_j'$ cannot exist. Therefore, our choice of $[x_i,x_i+1]$ is optimal.
+                \end{proof}
+
+                The greedy choice is to take the interval which contains $x_i$ and as many as possible other values.
+
+                I don't get the question about the optimal substructure, it's a term I only know from dynamic programming which doesn't apply here.
+        \end{enumerate}
 
 \end{enumerate}
 
-- 
cgit v1.2.3