final commit, project finished

[co1314.git] / LubbersReport.tex

diff --git a/LubbersReport.tex b/LubbersReport.tex
index abda695..01dd403 100644 (file)
--- a/LubbersReport.tex
+++ b/LubbersReport.tex
@@ -2,9 +2,15 @@
 
 \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=\footnotesize,
+       basicstyle=\scriptsize,
        breaklines=true,
        numbers=left,
        numberstyle=\tiny,
@@ -39,31 +45,59 @@
 \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.
+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 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}
-]
+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
-c1 -   put compatibility in list
+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}
 
-\subsection{Improvements}
-
-\section{Conclusion}
+\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}
-