\documentclass{article}

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

\definecolor{javared}{rgb}{0.6,0,0}
\definecolor{javagreen}{rgb}{0.25,0.5,0.35}
\definecolor{javapurple}{rgb}{0.5,0,0.35}

\lstset{
	basicstyle=\scriptsize,
	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 maximizes the sum of the compatibiliy values of the pet-child
combination.

\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 together with a
rough estimate of the complexity in Listing~\ref{lst:brute_force}. The
algorithm, due to calculating all the values the algorithm has a complexity
within $\mathcal{O}(n!)$. This is because there are $n!$ permutations possible for $n$ children.
Because of the rapid growth due to the complexity level the algorithm doesn't
scale up well.
\begin{lstlisting}[caption={Brute Force approach}, label={lst:brute_force},
                   keywords={[3]loop,put,return}]
n! - loop over all permutations
n  -   put compatibility in list
c1 - return maximum compatibility rating from list
\end{lstlisting}

\subsection{Improved algorithm}
The improved algorithm makes use of the fact that some rows only have very few
positive compatibilities. If you handle the rows/columns in the order from
little to lots of entries with compatibilites $1$ then a greedy approach will
suffice. This corresponds with the pseudocode specified together with a rough
estimate of the complexity in Listing~\ref{lst:improved}. The algorithm has a
complexity lies in the $\mathcal{O}(nm)$ because the main loop repeats at
maximum $n$ or $m$ times and the searching within the loop has a complexity of
$n$ if the loop runs $m$ times and $m$ otherwise.  The polynomial growth allows
the algorithm to be scaled relatively well.
\begin{lstlisting}[caption={Improved approach}, label={lst:improved},
                    keywords={[3]while,create,put,return,find,remove}]
n         - create list result of length n and initialize with -1
n+m       - create list rows/columns that contain pairs of indices and sums of values
nlgn      - sort the rows and columns list on ascending sum
(n+m)/2   - while there are still unused values in the lists
c1        -   pick the lowest value from the lists
c2        -   remove the value
max(n, m) -   find the lowest value in the corresponding antagonist
c2        -   remove the antagonist
c3        -   put the row/column pair in the results list
c4        - return the results list
\end{lstlisting}

\newpage
\section{Appendices}
\subsection{\textit{\href{http://www.java.com}{Java}} source}
\lstinputlisting[
	language=java,
	keywordstyle=\color{javapurple}\bfseries,
	stringstyle=\color{javared},
	commentstyle=\color{javagreen},
	stepnumber=2
]{LubbersSolver.java}

\end{document}
