Start report practical 1

1 files changed, 81 insertions, 0 deletions

diff --git a/Practical1/report/report.tex b/Practical1/report/report.tex
new file mode 100644
index 0000000..9ce7df9
--- /dev/null
+++ b/Practical1/report/report.tex
@@ -0,0 +1,81 @@
+\documentclass[10pt,a4paper]{article}
+
+% textcomp package is not available everywhere, and we only need the Copyright symbol
+% taken from http://tex.stackexchange.com/a/1677/23992
+\DeclareTextCommandDefault{\textregistered}{\textcircled{\check@mathfonts\fontsize\sf@size\z@\math@fontsfalse\selectfont R}}
+
+\usepackage{fancyhdr}
+\renewcommand{\headrulewidth}{0pt}
+\renewcommand{\footrulewidth}{0pt}
+\fancyhead{}
+%\fancyfoot[C]{Copyright {\textcopyright} 2015 Camil Staps}
+\pagestyle{fancy}
+
+\usepackage{amsmath}
+\usepackage{amsthm}
+\usepackage{amsfonts}
+\DeclareMathAlphabet{\pazocal}{OMS}{zplm}{m}{n}
+
+\usepackage[hidelinks]{hyperref}
+\usepackage{url}
+
+\newcommand*\iN{\bar{N}}
+\newcommand*\ex{-}
+\newcommand*\with{+}
+\DeclareMathOperator{\ms}{\alpha}
+
+\providecommand*{\lemmaautorefname}{Lemma}
+\newtheorem{lemma}{Lemma}
+
+\newenvironment{lemmaproof}[2][]{%
+    \begin{lemma}%
+        \def\temp{#1}\ifx\temp\empty\else\label{lem:#1}\fi%
+        #2%
+    \end{lemma}%
+    \begin{proof}%
+}{\end{proof}}
+
+\newcommand{\refeq}[2][]{\begin{equation}\label{eq:#1}#2\end{equation}}
+
+\numberwithin{lemma}{subsection}
+
+\usepackage{algorithm}
+\usepackage{algorithmic}
+\providecommand*{\algorithmautorefname}{Algorithm}
+
+\usepackage{minted}
+
+\title{Miss Algorithm}
+\author{Camil Staps\\\small{s4498062}}
+
+\begin{document}
+
+\maketitle
+\thispagestyle{fancy}
+
+\begin{abstract}
+    No, this report is not about a new beauty pageant. It is about the realisation and implementation of a maximum independent set size (miss) algorithm.
+
+    Garbage collectors and the local government of Nijmegen have agreed to place garbage bins on the at most 100 intersections of the at most 200 streets of the city, with the restriction that no two neighbouring intersections may both have a garbage bin. In this report we will discuss an algorithm that can check whether $k$ garbage bins can be placed following that rule.
+
+    This problem is of course a fancy formulation of the maximum independent set problem. So to answer the question, we implement an algorithm that computes the size of the maximum independent set, and verify if $k$ is small enough.
+\end{abstract}
+
+\section{Report organisation}
+%todo
+
+\input{notation}
+\input{algorithm}
+\input{implementation}
+\input{analysis}
+
+\section{Acknowledgements}
+\label{sec:acknowledgements}
+I'm grateful to Tom van der Zanden for pointing me to the term `maximum independent set', which eventually let me to Robson's algorithm \cite{robson}.
+
+\begin{thebibliography}{9}
+    \bibitem{robson}{Robson, J.M. (1985). \emph{Algorithms for Maximum Independent Sets}.}
+\end{thebibliography}
+
+\end{document}
+