Skeleton for report, small solver changes

[co1314.git] / LubbersReport.tex

diff --git a/LubbersReport.tex b/LubbersReport.tex
index b2a9422..abda695 100644 (file)
--- a/LubbersReport.tex
+++ b/LubbersReport.tex
@@ -1,11 +1,20 @@
 \documentclass{article}
 
+\usepackage{listings}
 \usepackage[dvipdfm]{hyperref}
 
+\lstset{
+       basicstyle=\footnotesize,
+       breaklines=true,
+       numbers=left,
+       numberstyle=\tiny,
+       tabsize=2
+}
+
 \author{
        Mart Lubbers\\
        s4109503\\
-       \url{mailto:mart@martlubbers.net}
+       \href{mailto:mart@martlubbers.net}{mart@martlubbers.net}
 }
 \title{Complexity Assignment}
 \date{\today}
@@ -13,9 +22,46 @@
 \begin{document}
 \maketitle
 \tableofcontents
-\section{Introduction}
+\newpage
+
+\section{Problem description}
+\begin{center}
+       \textit{
+               Every day children come to the zoo to take care of the pets. After an
+               introductory meeting with all the pets, the kids are given one pet to
+               exclusively take care of for the rest of the visit. However, certain pets
+               do not go on well with certain kids, and vice-versa. Pets are also not
+               immortal; and the groups vary in size from time to time. Because these pets
+               require very special attention, exactly one child can take care of a single
+               pet. This implies that sometimes a child does not have a pet to take care
+               for and sometimes a pet is left without a caretaker.
+       }
+\end{center}
+
+The assignment is to implement a \textit{\href{http://www.java.com}{Java}}
+program that optimizes the assignment of pets to children so that the sum of
+all the compatibility values between pets and children is the maximum possible.
 
 \section{Implementation}
+\subsection{Brute Force}
+The first approach was to implement a brute force algorithm which calculates
+every possible combination of pets and children and then takes the one with the
+highest value. This corresponds with the pseudocode specified in
+Listing~\ref{lst:brute_force}. The algorithm, due to calculating all the values
+has a minimal complexity of $n!$. This is because there are $n!$ permutations
+possible for $n$ children.
+\begin{lstlisting}[
+       caption={Brute Force approach},
+       label={lst:brute_force},
+       keywords={[3]loop,put,return}
+]
+n! - loop over all permutations
+c1 -   put compatibility in list
+c1 - return maximum compatibility rating from list
+\end{lstlisting}
+
+
+\subsection{Improvements}
 
 \section{Conclusion}