Algoritmiek Practicum Opdracht 3

\documentclass[a4paper]{article}

\usepackage[english]{babel}
\usepackage[utf8]{inputenc}
\usepackage{amsmath}
\usepackage{graphicx}
\usepackage[colorinlistoftodos]{todonotes}
\usepackage{algorithm}
\usepackage[noend]{algpseudocode}

\title{Algoritmiek Practicum Opdracht 3}

\author{Jehan Da Camara \\ jdacamara \\ 4207858 }

\date{\today}
%
\begin{document}
\maketitle

\section{Task A}
As input you will receive a ordered list of Updates that is the original set. Which will contain the following information and other information that can be deduced:

\begin{itemize}
  \item List u = sorted list of updates in increasing order
  \item ConstantCost = Is the amount that must be paid to ship the bundle or update.
  \item amountOfUpdates = is the amount of Updates
  \item $Risk_{i}$ = is the risk from $Update_{i}$ to $Update_{j}$
  \item minimalCost = is the minimal cost from the current version to the desired update.
\end{itemize}

The variable cost for each update is not relevant because it is not risk is converted to a price or currency and with the help of that we will compute which sequece of updates is more optimal.

\section{Task B}
\begin{equation}
  f(x)=\begin{cases}
    1, & \text{if $x<0$}.\\
    0, & \text{otherwise}.
  \end{cases}
\end{equation}

\section{Task C}

\begin{algorithm}
\caption{calculates the minimal cost of bundling}
\begin{algorithmic}[1]
\Procedure{minimalCost}{$list U,amountOfUpdates,concantCost$}

\If{$amountOfUpdate = 0$}
\State \textbf{Return }$0$
\EndIf
\State $minimal \gets {}$
\State $minimal_{0} \gets concantCost$

\For{$i \gets 2 to amountOfUpdates$}
\State $smallest \gets MaxValue$
\State $possible \gets 0$
\For{$j\gets 1 to i$}
\State cost
\If{$Update_{i,j} is in list U$}
\State $ cost \gets the cost of Update_{i,j}$
\Else
\State $ cost \gets 0 $
\EndIf

\If{$ j = 1$}
 \State $possible \gets concantCost + cost$
\Else 
\State $possible \gets minimal_{j-2} + cost + concantCost$
\EndIf

\State $smallest \gets Min{smallest,possible}$

\EndFor
\State $minimal_{i} \gets smallest$
\EndFor

\State \textbf{Return }$minimal_{amountOfUpdates-1}$
\EndProcedure
\end{algorithmic}
\end{algorithm}

\newpage
\section{Task D}
The tighest algorithm for the alogrithm in task C is $O(n^2)$. This hold because it loops twice through the data. Because with my impletation it calculates for every update the minimal cost and that mean for each update it will check every update before this point. The space for this algorithm is $O(n)$  because in the situation that every for each update the risk is given then it would have n records at most.

\section{Task E}
The code is submitted on Codersrv and is available there.

\section{Task F}

\section{Task G}

\end{document}