\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\\
- \url{mailto:mart@martlubbers.net}
+ \href{mailto:mart@martlubbers.net}{mart@martlubbers.net}
}
\title{Complexity Assignment}
\date{\today}
\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 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}
-\section{Conclusion}
+\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}
-\end{document}
+\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}
repositories / co1314.git / blobdiff