\documentclass{article}

\usepackage{listings}
\usepackage[dvipdfm]{hyperref}

\lstset{
	basicstyle=\footnotesize,
	breaklines=true,
	numbers=left,
	numberstyle=\tiny,
	tabsize=2
}

\author{
	Mart Lubbers\\
	s4109503\\
	\href{mailto:mart@martlubbers.net}{mart@martlubbers.net}
}
\title{Complexity Assignment}
\date{\today}

\begin{document}
\maketitle
\tableofcontents
\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}

\end{document}

