\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}
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.
-\begin{lstlisting}[
- caption={Brute Force approach},
- label={lst:brute_force},
- keywords={[3]loop,put,return}
-]
+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}
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.
-\begin{lstlisting}[
- caption={Improved approach},
- label={lst:improved},
- keywords={[3]while,create,put,return,find,remove}
+\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