\documentclass{article}
\usepackage[utf8]{inputenc}

\title{A\&D Practical Assignment}
\author{Laurens Brinker (s4361733), Phil Geelhoed (s4118901) }
\date{8 November 2014}

\usepackage{natbib}
\usepackage{graphicx}

\begin{document}

\maketitle

\section{Introductie}
Dit document is geschreven in het kader van de cursus Algoritme en Datasctructuren. Het probleem wat we voorgelegd kregen is een variant op het kortste pad probleem in de graaftheorie, met een science fiction verhaaltje er over heen. De opdracht was; Gegeven N sterren (Nodes) en voor elk paar sterren, de korste tijd die nodig om te reizen, reconstrueer de banen waarmee je naar de sterren kan reizen (Edges). Deze banen bestaan uit N wormholes. \\
De taak aan ons dus, gegeven een "adjacency matrix" met alle afstanden van elke ster naar de andere sterren, haal de bestaande wormholes uit deze matrix met de bijbehorende sterren en de afstand. \\
Eerst zullen we onze implementatie uitleggen en het algoritme dat we hebben bedacht om het probleem op te lossen. Daarna komt de complexiteit analyse van ons algoritme. Tot slot bekijken we de resultaten die we zelf hebben ondervonden.

\begin{figure}[h!]
\centering
\includegraphics[scale=1.7]{universe.jpg}
\caption{The Universe}
\label{fig:univerise}
\end{figure}
\pagebreak
\section{Uitleg van onze implementatie}
We hadden een oplossing voor het probleem gevonden, die we later uitleggen, en we gingen hierna kijken hoe we het best deze oplossing konden implementeren. Stel we zouden dynamic programming gebruiken, dan zouden we resultaten moeten opslaan die we al een keer berekend hadden. Maar wij kwamen er snel achter dat de waarden die wij meerdere keren nodig hadden simpelweg waarden uit de matrix waren. Het is dus niet handig om dynamic the programmeren als je toch alleen hoeft te lezen (en geen berekenening hoeft uit te voeren). Wij hebben ook gekeken of wij een recursieve implementatie konden toepassen, maar wij kwamen hier ook snel achter dat dit wel mogelijk was, maar dat je in principe geen vooruitgang hiermee boekte omdat je nogsteeds hetzelfde evenvaak uitrekende. Wij hebben ook gekeken naar het sorteren van de rijen, dit was opzich een goede oplossing. We kregen een lagere complexieit dan we nu hebben, maar wij zagen snel dat de daadwerkelijke runtime wel er omhoog ging.
Onze implementatie hoort dus bij deze oplossing:
\begin{enumerate}
\item Je gaat door de rijen 1 t/m N.
\item Je gaat per rij elke waarde langs tot de 0 (de diagonaal)
\item Je kijkt bij deze waarde of er in diezelfde rij nog waarden zijn die kleiner zijn dan die waarde (en niet 0).
\item Je kijkt bij die kleinere waarde wat de lengte is van het eindpunt weer terug naar de originele waarde die we kennen.
\item Als je deze kleinere waarde en de waarde van het eindpunt terug naar de originele waarde optelt kunnen zich twee situaties voordoen:
\begin{enumerate}
\item De optelsom is groter dan de originele waarde, kijk nu naar de volgende kleinere waarde in die rij.
\item De optelsom is gelijk aan de originele waarde: Er is een indirect path dus we kunnen dit punt vergeten en doorgaan naar het volgende punt
\end{enumerate}
\item Op het moment dat alle kleinere waarden een optelsom geven die groter is dan de originele waarde betekent dit dat dit het kleinste pad is en dus een direct path.
\item Als er geen kleinere waarden zijn in de rij is deze waarde per definitie een direct path.
\item Zet alle direct paths in de Navmap omdat dit wormholes zijn.
\end{enumerate}
\pagebreak
Uitleg aan de hand van een voorbeeld:
\\Stel we hebben deze situatie:
\\\includegraphics[scale=0.4]{uitleg_1.png}
\\En we moeten kijken of er van A naar D, dus ad een wormhole is.
\\Bij ons algoritme dus of ab en/of ac kleiner zijn dan ad.
\\Als ab kleiner is dan ad kijken we of ab + bd groter is dan ad. Op het moment dat dit zo is kijken we of ac kleiner is dan ad. Maar als ab + bd = ad dan weten we dat a naar d geen wormhole is omdat het kortste path wordt gemaakt door een indirect path namelijk: A naar B naar D. Stel ab + bd $>$ ad dan kijken we of ac $<$ ad. Op het moment dat dit zo is kijken we of ac + cd $>$ ad. Als dit zo is dan betekent het dat alle kortere paden dan ad vanaf A geen shortest path zijn dus dat ad een direct path is. Als ac + cd = ad dan is er een indirect path A naar C naar D met de lengte ad. Toen we ons algoritme probeerden uit te leggen aan mede studenten hadden ze er moeite mee om het te begrijpen. Wij kwamen erachter dat voorbeeldjes met getallen beter werkten:
\subsection{Voorbeeld 1}
\includegraphics[scale=0.4]{uitleg_2.png}
\\We willen weten of A naar D een wormhole heeft. We gaan dus kijken of er paden zijn uit A die kleiner zijn dan 6. Ja, namelijk ac = 2. Vervolgens kijken we wat de lengte is van cd en dit is 4. 2 + 4 = 6 dus we hebben hier te maken met een indirect path (en dus geen wormhole)!
\subsection{Voorbeeld 2}
\includegraphics[scale=0.4]{uitleg_3.png}
\\We hebben ad = 5, is er een kleinere waarde, ja: ac = 2. Wat is ac + cd? ac + cd = 6 en 6 $<$ 5. Is er nog een waarde kleiner dan 5? Ja: ab = 4. wat is ab + bd? ab + bd = 9 $<$ 5. Is er nog een waarde kleiner dan 5? Nee. Er zijn geen indirect paths dus A naar D heeft wormhole ad met lengte 5.
\subsection{Voorbeeld 3}
\includegraphics[scale=0.4]{uitleg_4.png}
\\Zijn er kleinere waarden die uit A komen dan 3? Nee, er is dus een wormhole van A naar D , ad , met lengte 3.
\subsection{Onze code}
\begin{enumerate}
\item We hebben 3 for loops nodig.
\begin{enumerate}
\item De eerste for-loop gaat van 1 naar N voor alle rijen
\item De tweede for-loop gaat van 0 naar het laatste element voor de diagonaal (de waarde van de eerste forloop) om te kijken of de elementen in die rij wormholes zijn.
\item De derde for-loop gaat van 0 naar N en kijkt voor de elementen van de tweede for-loop of er kleinere waarden zijn in die rij (ongelijk aan 0).
\end{enumerate}
\item Vervolgens moeten we kijken of er geen indirect paths zijn of dat er geen kleinere waarden zijn.
\item Als er geen van beiden bij 2 geldt, dan is er dus een wormhole dus moet hij toegevoegd worden.
\item !LET OP! Er zijn situaties dat het aantal wormholes kleiner is dan N. In dit geval moeten we een wormhole toevoegen tussen twee punten die nog geen wormhole hebben. Dit mag zolang die waarde niet kleiner is dan de shortest path tussen twee punten want dan zal deze wormhole nooit gebruikt worden aangezien dit geen shortest path is.
\begin{enumerate}
\item Kijk of het laatste element null is, dit betekent dat we een wormhole missen.
\item Neem twee random values in de range van N totdat ze niet gelijk zijn aan elkaar.
\item Kijk of de random values al endpoints zijn in de wormhole array, zo niet voeg dan een wormhole toe van random1 naar random2 met de lengte van random1 naar random 2. Als de random values al wel bekend zijn begin dan weer bij (b) om nieuwe values te vinden om toe te voegen.
\end{enumerate}
\end{enumerate}
\subsection{Screenshots van de code}
Eerste gedeelte:
\\\includegraphics[scale = 0.45]{code1.png}
\\Tweede gedeelte:
\\\includegraphics[scale = 0.45]{code2.png}
\subsection{extra}
We hebben bij de klasse test nog wat code toegevoegd zodat we de tijd kunnen meten van de individuele problemen en de totale tijd om de problemen op te lossen. Zodat we de volgende output kregen:
\\\includegraphics[scale=1]{output.png}
\section{Complexiteit analyse}
In onze implementatie gebruiken we drie nested for-loops. De eerste loopt langs de rijen van de matrix, de tweede loopt in elke rij langs de elementen voor de diagonaal en de derde kijkt in dezelfde rij per element of er kleinere waarden zijn in de rij. De matrix waar het algoritme door heen loopt is een NxN matrix, waarbij N het aantal sterren representeert in het probleem. Elke for-loop loopt dus in een "worst-case scenario" langs al de sterren, dus langs N sterren.Behalve de tweede for-loop die loopt tot de diagonaal in elke rij en gaat dus uiteindelijk door \(\frac{1}{2}N\). Hierdoor krijgen we een complexiteit van: \[O(N*\frac{1}{2}N*N) = O(\frac{1}{2}N^{3}) \in O(N^{3})\] \\
\section{Resultaten}
Ons algoritme was bij de testcases redelijk snel. Hieronder een tabel van enkele tijdmetingen die we zelf hebben getest.
\\
\begin{center}
    \begin{tabular}{|1|1|}
    \hline
    N (aantal sterren) & Tijd (in ms)\\ \hline
    10 &  9\\ \hline
    100 &  22\\ \hline
    200&  61\\ \hline
    300&  172\\ \hline
    400&  328\\ \hline
    500&  580\\ \hline
    600&  991\\ \hline
    700&  1497\\ \hline
    800&  2184\\ \hline
    900 &  3049\\ \hline
    1000 &  4062\\ \hline
    alle tests & 30000 \\ \hline
    \end{tabular}
\end{center}
Deze tijden zijn gemeten op een laptop met de volgende specs:\\
\\\includegraphics[scale=0.5]{specs.png}
\\
We hebben alle metingen in een excel file gestopt en er een grafiek van geplot. Je ziet hier duidelijk dat de grafiek een vorm aan neemt die aardig lijkt op wat we dachten. Namelijk een derdemachts funcie, vanwege een complexiteit van $O(N^3)$.
\begin{figure}[h]
\centering
\includegraphics[scale=0.5]{performancegrafiek.JPG}
\caption{Performance Grafiek}
\label{fig:univerise}
\end{figure}
In vergelijking met andere studie genoten aan wie we vroegen hoe snel hun algoritme was, hadden we naar onze mening een snel algoritme bedacht. Bij de meeste tests duurde het inlezen langer dan het algoritme zelf. Op de computer in de terminalkamer van het Huygensgebouw deden de tests er wel iets langer over. We denken dat dit komt doordat wij de processor of GPU of een andere component op Laurens' laptop `meer' kunnen gebruiken waardoor de operaties zoals het optellen en het lezen uit de array net iets sneller gaat. \\

Toch is er iets wat we niet goed hadden: in de opdracht staat dat we mogen aannemen dat N $<$ 10000. Maar hier komen wij in de problemen. Aangezien wij een algoritme hebben dat sterk oploopt komen we in de problemen als N groter wordt. Wij hebben uitgerekend dat wij bij N = 5.000 er waarschijnlijk 798426915 (berekend met GROWTH in excel) ms = 798426 sec = 12807 min =  221,8 uur = 9 dagen over doen. Op het moment dat we N = 10.000 nemen doen we er 3.22381 * $10^{12}$ seconden over dit zijn ongeveer 37 miljoen dagen. We hopen dus de `neem aan dat N $<$ 10.000' een typo is en dat daar `neem aan dat N $<$ 1000', net als in de examples, moet staan.
\subsection{resultaten van voorbeeld}
In de opdracht stond een voorbeeld. We hebben met ons programma en de funtie printGraphviz de graph gereconstrueerd. (We hebben de output in een online graphviz simulator gezet.
\\\includegraphics[scale=0.4]{output1.png} gaf de graph: \includegraphics[scale=0.4]{output2.png}
\\ En dit komt overeen met de gegeven graph in de opdracht.
\end{document}