LubbersReport.tex

   1 \documentclass{article}
   2
   3 \usepackage{listings}
   4 \usepackage[dvipdfm]{hyperref}
   5
   6 \lstset{
   7         basicstyle=\footnotesize,
   8         breaklines=true,
   9         numbers=left,
  10         numberstyle=\tiny,
  11         tabsize=2
  12 }
  13
  14 \author{
  15         Mart Lubbers\\
  16         s4109503\\
  17         \href{mailto:mart@martlubbers.net}{mart@martlubbers.net}
  18 }
  19 \title{Complexity Assignment}
  20 \date{\today}
  21
  22 \begin{document}
  23 \maketitle
  24 \tableofcontents
  25 \newpage
  26
  27 \section{Problem description}
  28 \begin{center}
  29         \textit{
  30                 Every day children come to the zoo to take care of the pets. After an
  31                 introductory meeting with all the pets, the kids are given one pet to
  32                 exclusively take care of for the rest of the visit. However, certain pets
  33                 do not go on well with certain kids, and vice-versa. Pets are also not
  34                 immortal; and the groups vary in size from time to time. Because these pets
  35                 require very special attention, exactly one child can take care of a single
  36                 pet. This implies that sometimes a child does not have a pet to take care
  37                 for and sometimes a pet is left without a caretaker.
  38         }
  39 \end{center}
  40
  41 The assignment is to implement a \textit{\href{http://www.java.com}{Java}}
  42 program that optimizes the assignment of pets to children so that the sum of
  43 all the compatibility values between pets and children is the maximum possible.
  44
  45 \section{Implementation}
  46 \subsection{Brute Force}
  47 The first approach was to implement a brute force algorithm which calculates
  48 every possible combination of pets and children and then takes the one with the
  49 highest value. This corresponds with the pseudocode specified in
  50 Listing~\ref{lst:brute_force}. The algorithm, due to calculating all the values
  51 has a minimal complexity of $n!$. This is because there are $n!$ permutations
  52 possible for $n$ children.
  53 \begin{lstlisting}[
  54         caption={Brute Force approach},
  55         label={lst:brute_force},
  56         keywords={[3]loop,put,return}
  57 ]
  58 n! - loop over all permutations
  59 c1 -   put compatibility in list
  60 c1 - return maximum compatibility rating from list
  61 \end{lstlisting}
  62
  63
  64 \subsection{Improvements}
  65
  66 \section{Conclusion}
  67
  68 \end{document}
  69