LubbersReport.tex

   1 \documentclass{article}
   2
   3 \usepackage{listings}
   4 \usepackage[dvipdfm]{hyperref}
   5 \usepackage{color}
   6 \usepackage{amssymb}
   7
   8 \definecolor{javared}{rgb}{0.6,0,0}
   9 \definecolor{javagreen}{rgb}{0.25,0.5,0.35}
  10 \definecolor{javapurple}{rgb}{0.5,0,0.35}
  11
  12 \lstset{
  13         basicstyle=\scriptsize,
  14         breaklines=true,
  15         numbers=left,
  16         numberstyle=\tiny,
  17         tabsize=2
  18 }
  19
  20 \author{
  21         Mart Lubbers\\
  22         s4109503\\
  23         \href{mailto:mart@martlubbers.net}{mart@martlubbers.net}
  24 }
  25 \title{Complexity Assignment}
  26 \date{\today}
  27
  28 \begin{document}
  29 \maketitle
  30 \tableofcontents
  31 \newpage
  32
  33 \section{Problem description}
  34 \begin{center}
  35         \textit{
  36                 Every day children come to the zoo to take care of the pets. After an
  37                 introductory meeting with all the pets, the kids are given one pet to
  38                 exclusively take care of for the rest of the visit. However, certain pets
  39                 do not go on well with certain kids, and vice-versa. Pets are also not
  40                 immortal; and the groups vary in size from time to time. Because these pets
  41                 require very special attention, exactly one child can take care of a single
  42                 pet. This implies that sometimes a child does not have a pet to take care
  43                 for and sometimes a pet is left without a caretaker.
  44         }
  45 \end{center}
  46
  47 The assignment is to implement a \textit{\href{http://www.java.com}{Java}}
  48 program that optimizes the assignment of pets to children so that the sum of
  49 all the compatibility values between pets and children is the maximum possible.
  50
  51 \section{Implementation}
  52 \subsection{Brute Force}
  53 The first approach was to implement a brute force algorithm which calculates
  54 every possible combination of pets and children and then takes the one with the
  55 highest value. This corresponds with the pseudocode specified together with a
  56 rough estimate of the complexity in Listing~\ref{lst:brute_force}. The
  57 algorithm, due to calculating all the values the algorithm has a complexity
  58 within $\mathcal{O}(n!)$.
  59 This is because there are $n!$ permutations possible for $n$ children.
  60 \begin{lstlisting}[
  61         caption={Brute Force approach},
  62         label={lst:brute_force},
  63         keywords={[3]loop,put,return}
  64 ]
  65 n! - loop over all permutations
  66 c1 -   put compatibility in list
  67 c1 - return maximum compatibility rating from list
  68 \end{lstlisting}
  69
  70 \subsection{Improved algorithm}
  71 The improved algorithm makes use of the fact that some rows only have very few
  72 positive compatibilities. If you handle the rows/columns in the order from
  73 little to lots of entries with compatibilites $1$ then a greedy approach will
  74 suffice. This corresponds with the pseudocode specified together with a rough
  75 estimate of the complexity in Listing~\ref{lst:improved}. The algorithm has a
  76 complexity lies in the $\mathcal{O}(nm)$ because the main loop repeats at
  77 maximum $n$ or $m$ times and the searching within the loop has a complexity of
  78 $n$ if the loop runs $m$ times and $m$ otherwise.
  79 \begin{lstlisting}[
  80         caption={Improved approach},
  81         label={lst:improved},
  82         keywords={[3]while,create,put,return,find,remove}
  83 ]
  84 n         - create list result of length n and initialize with -1
  85 n+m       - create list rows/columns that contain pairs of indices and sums of values
  86 nlgn      - sort the rows and columns list on ascending sum
  87 (n+m)/2   - while there are still unused values in the lists
  88 c1        -   pick the lowest value from the lists
  89 c2        -   remove the value
  90 max(n, m) -   find the lowest value in the corresponding antagonist
  91 c2        -   remove the antagonist
  92 c3        -   put the row/column pair in the results list
  93 c4        - return the results list
  94 \end{lstlisting}
  95
  96 \section{Conclusion}
  97
  98 \newpage
  99 \section{Appendices}
 100 \subsection{\textit{\href{http://www.java.com}{Java}} source}
 101 \lstinputlisting[
 102         language=java,
 103         keywordstyle=\color{javapurple}\bfseries,
 104         stringstyle=\color{javared},
 105         commentstyle=\color{javagreen},
 106         stepnumber=2
 107 ]{LubbersSolver.java}
 108
 109 \end{document}