From 08be3e96a32d95c277905ca7fa015d88195b257e Mon Sep 17 00:00:00 2001
From: Camil Staps
Date: Tue, 27 Oct 2015 18:08:50 +0100
Subject: Start report practical 1

---
 Practical1/report/report.tex | 81 ++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 81 insertions(+)
 create mode 100644 Practical1/report/report.tex

(limited to 'Practical1/report/report.tex')

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}
+
-- 
cgit v1.2.3

