Start report practical 1

1 files changed, 54 insertions, 0 deletions

diff --git a/Practical1/report/analysis.tex b/Practical1/report/analysis.tex
new file mode 100644
index 0000000..32c3f8e
--- /dev/null
+++ b/Practical1/report/analysis.tex
@@ -0,0 +1,54 @@
+\section{Complexity analysis}
+\label{sec:analysis}
+
+Robson provides us with a very detailed analysis proving that the $\ms$ algorithm runs in $\pazocal O(\mathrm{polynomial}(n)\cdot2^{cn})$, where $c<0.296$ and with $n$ the number of vertices of the input graph \cite{robson}. However, the argument is over my head, so I will provide my own, simpler, less exact analysis here.
+
+We write $T_{\ms}(n)$ for the running time of $\ms$ on a graph $G$ with $|G|=n$. For $\ms^n$ we write $T_{\ms^n}(p,q)$ for the appliance of $\ms^n$ on a graph $G$ with $|G|=p$ and a set $S$ to pick $n$ vertices from with $|S|=q$. In the case of $n=1$, we write $T_{\ms^1}(p)$ instead of $T_{\ms^1}(p,2)$, because we only use the case of $q=2$.
+
+\subsection{$\ms^1$: \autoref{alg:ms1}}
+\label{sec:analysis:ms1}
+
+This function is a simple case distinction. Let's therefore consider the complexities of all the cases one by one. The results, along with their line numbers in \autoref{alg:ms1}, may be found in \autoref{tab:analysis-ms1}.
+
+\begin{table}[h]
+    \centering
+    \renewcommand{\arraystretch}{1.3}
+    \begin{tabular}{l | p{29mm} | p{19mm} | p{50mm}}
+        Ln. & Case & Complexity & Argumentation \\\hline\hline
+        \ref{alg:ms1:case-d1}       & $d(s_1)\leq 1$
+            & $T_{\ms}(n-1)$
+            & Simple recurrence \\\hline
+        \ref{alg:ms1:case-edge-d4} & $e(s_1,s_2), d(s_1)>3$
+            & $2T_{\ms}(n-5)$
+            & Both vertices have degree four, so we run $\ms$ twice on a graph with five vertices less\\\hline
+        \ref{alg:ms1:case-edge-d3} & $e(s_1,s_2), d(s_1)\leq3$
+            & $T_{\ms}(n)$
+            & Simple recurrence \\\hline
+        \ref{alg:ms1:intersection} & $N(s_1)\cap N(s_2)\neq\emptyset$
+            & $T_{\ms^1}(n-1)$ 
+            & At least one vertex removed \\\hline
+        \ref{alg:ms1:case-2-2-edge} & $d(s_1)=d(s_2)=2$, $e(w_1,w_2)$
+            & $T_{\ms}(n-3)$
+            & Simple recurrence \\\hline
+        \ref{alg:ms1:case-2-2-dominance} & $d(s_1)=d(s_2)=2$, $N^2(s_1)\subset N(s_2)$
+            & $T_{\ms}(n-6)$
+            & Exactly six vertices removed \\\hline
+        \ref{alg:ms1:case-2-2-else} & $d(s_1)=d(s_2)=2$, otherwise
+            & $T_{\ms}(n-3) + T_{\ms}(n-7)$ 
+            & In the first case three vertices removed, in the second case seven \\\hline
+        \ref{alg:ms1:case-general} & Otherwise
+            & $T_{\ms}(n-3) + T_{\ms^2}(n-4,4)$
+            & In the first case at least three vertices removed, in the second case four, and at most four to choose two from
+    \end{tabular}
+    \caption{Worst-case complexity analysis of the different cases of $\ms^1$}
+    \label{tab:analysis-ms1}
+\end{table}
+
+\subsection{$\ms^2$: \autoref{alg:ms2}}
+\label{sec:analysis:ms2}
+%todo
+
+\subsection{$\ms$: \autoref{alg:ms}}
+\label{sec:analysis:ms}
+%todo
+