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 maximizes the sum of the compatibiliy values of the pet-child
  49 combination.
  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!)$. This is because there are $n!$ permutations possible for $n$ children.
  59 Because of the rapid growth due to the complexity level the algorithm doesn't
  60 scale up well.
  61 \begin{lstlisting}[caption={Brute Force approach}, label={lst:brute_force},
  62                    keywords={[3]loop,put,return}]
  63 n! - loop over all permutations
  64 n  -   put compatibility in list
  65 c1 - return maximum compatibility rating from list
  66 \end{lstlisting}
  67
  68 \subsection{Improved algorithm}
  69 The improved algorithm makes use of the fact that some rows only have very few
  70 positive compatibilities. If you handle the rows/columns in the order from
  71 little to lots of entries with compatibilites $1$ then a greedy approach will
  72 suffice. This corresponds with the pseudocode specified together with a rough
  73 estimate of the complexity in Listing~\ref{lst:improved}. The algorithm has a
  74 complexity lies in the $\mathcal{O}(nm)$ because the main loop repeats at
  75 maximum $n$ or $m$ times and the searching within the loop has a complexity of
  76 $n$ if the loop runs $m$ times and $m$ otherwise.  The polynomial growth allows
  77 the algorithm to be scaled relatively well.
  78 \begin{lstlisting}[caption={Improved approach}, label={lst:improved},
  79                     keywords={[3]while,create,put,return,find,remove}]
  80 n         - create list result of length n and initialize with -1
  81 n+m       - create list rows/columns that contain pairs of indices and sums of values
  82 nlgn      - sort the rows and columns list on ascending sum
  83 (n+m)/2   - while there are still unused values in the lists
  84 c1        -   pick the lowest value from the lists
  85 c2        -   remove the value
  86 max(n, m) -   find the lowest value in the corresponding antagonist
  87 c2        -   remove the antagonist
  88 c3        -   put the row/column pair in the results list
  89 c4        - return the results list
  90 \end{lstlisting}
  91
  92 \newpage
  93 \section{Appendices}
  94 \subsection{\textit{\href{http://www.java.com}{Java}} source}
  95 \lstinputlisting[
  96         language=java,
  97         keywordstyle=\color{javapurple}\bfseries,
  98         stringstyle=\color{javared},
  99         commentstyle=\color{javagreen},
 100         stepnumber=2
 101 ]{LubbersSolver.java}
 102
 103 \end{document}