diff options
Diffstat (limited to 'Practical2/report')
| -rw-r--r-- | Practical2/report/algorithm.tex | 68 | ||||
| -rw-r--r-- | Practical2/report/analysis.tex | 18 | ||||
| -rw-r--r-- | Practical2/report/implementation.tex | 19 | ||||
| -rw-r--r-- | Practical2/report/notation.tex | 8 | ||||
| -rw-r--r-- | Practical2/report/report.tex | 8 |
5 files changed, 79 insertions, 42 deletions
diff --git a/Practical2/report/algorithm.tex b/Practical2/report/algorithm.tex index 73780f0..175ad4b 100644 --- a/Practical2/report/algorithm.tex +++ b/Practical2/report/algorithm.tex @@ -6,102 +6,102 @@ I will propose a solution that uses dynamic programming. First, I will describe \subsection{General program flow} \label{sec:algorithm:general} -\begin{thmproof}[P_0_k]{lemma}{For any $\bar p, k$, we have $P_0^k=0$.} - There is only one way to partition $\bar p$ (using $k$ empty partitions). The profit of every member of the partitioning is zero, and therefore the overall profit of the partitioning is zero as well. +\begin{thmproof}[G_0_k]{lemma}{For any $\bar a, k$, we have $G_0^k(\bar a)=0$.} + There is only one way to partition $\bar a$ (using $k$ empty partitions). The profit of every member of the partitioning is zero, and therefore the overall profit of the partitioning is zero as well. \end{thmproof} -\begin{thmproof}[P_p_0]{lemma}{For any $\bar p, p\le|\bar p|$, we have $P_p^0(\bar p)=\PR(S_0^p(\bar p))$.} - In this case there is only one way to partition $\bar p$ (using one complete partition). The profit is the difference between the sum of the elements and their rounded sum. +\begin{thmproof}[G_p_0]{lemma}{For any $\bar a, p\le|\bar a|$, we have $G_p^0(\bar a)=\PR(S_0^p(\bar a))$.} + In this case there is only one way to partition $\bar a$ (using one complete partition). The profit is the difference between the sum of the elements and their rounded sum. \end{thmproof} -\begin{thmproof}[P_p_k]{lemma}{$P_p^k(\bar p) = \max\left(P_p^{k-1}(\bar p), \max\limits_{i=0}^{p-1}\left(P_i^{k-1}(\bar p) + \PR(S_i^p)\right)\right)$.} - Consider the $p$th element of $\bar p$ and a partitioning that gives the maximal profit in the substring until $\bar p_p$, $P_p^k(\bar p)$. We have two possibilities: +\begin{thmproof}[G_p_k]{lemma}{$G_p^k(\bar a) = \max\left(G_p^{k-1}(\bar a), \max\limits_{i=0}^{p-1}\left(G_i^{k-1}(\bar a) + \PR(S_i^p(\bar a))\right)\right)$.} + Consider the $p$th element of $\bar a$ and a partitioning that gives the maximal profit in the substring until $\bar a_p$, $G_p^k(\bar a)$. We have two possibilities: \begin{itemize}[itemsep=0pt] - \item $\bar p_p$ is in one partition with $\bar p_i, \bar p_{i+1}, \dots, \bar p_{p-1}$. In this case we would have $P_p^k(\bar p) = P_i^{k-1}(\bar p) + \PR(S_i^p)$, since we can divide the rest of $\bar p$ over $k-1$ independent partitions and gain a profit of $\PR(S_i^p)$ over that last partition. - \item It is in fact more worthwhile to create $k-1$ partitions rather than $k$. In this case, we have $P_p^k(\bar p)=P_p^{k-1}(\bar p)$. + \item $\bar a_p$ is in one partition with $\bar a_i, \bar a_{i+1}, \dots, \bar a_{p-1}$. In this case we would have $G_p^k(\bar a) = G_i^{k-1}(\bar a) + \PR(S_i^p(\bar a))$, since we can divide the rest of $\bar a$ over $k-1$ independent partitions and gain a profit of $\PR(S_i^p(\bar a))$ over that last partition. + \item It is in fact more worthwhile to create $k-1$ partitions rather than $k$. In this case, we have $G_p^k(\bar a)=G_p^{k-1}(\bar a)$. \end{itemize} To get the actual profit, we take the maximum of the two possibilities. \end{thmproof} -This suggests the general flow of our algorithm: we maintain an $(n+1)\times (k+1)$-table of values for $P_p^d$ with $0\le d\le k, 0\le p\le n$. Using the recurrences from \autoref{lem:P_p_0}, \ref{lem:P_0_k} and \ref{lem:P_p_k}, that only rely on `smaller values' ($P_{p'}^{d'}$ with $p'\le p$ or $d'\le d$), we generate the whole table. The solution to our problem is then $$\PM_k(\bar p) = \sum\bar p-\PP_k(\bar p) = \sum\bar p - P_{|\bar p|}^k(\bar p).$$ +This suggests the general flow of our algorithm: we maintain an $(n+1)\times (k+1)$-table of values for $G_p^d$ with $0\le d\le k, 0\le p\le n$. Using the recurrences from \autoref{lem:G_p_0}, \ref{lem:G_0_k} and \ref{lem:G_p_k}, that only rely on `smaller values' ($G_{p'}^{d'}$ with $p'\le p$ or $d'\le d$), we generate the whole table. The solution to our problem is then $$\PM_k(\bar a) = \sum\bar a-\PP_k(\bar a) = \sum\bar a - G_{|\bar a|}^k(\bar a).$$ \begin{algorithm}[h] \footnotesize - \caption{Finding the maximum profit $\PP_k(\bar p)$ of sequence $\bar p$ with $k$ partitions} + \caption{Finding the maximum profit $\PP_k(\bar a)$ of sequence $\bar a$ with $k$ partitions} \label{alg:maximum-profit} \begin{algorithmic}[1] - \REQUIRE $\bar p, k$ - \STATE $n\gets |\bar p|$ - \STATE $P[n+1][k+1]$ + \REQUIRE $\bar a, k$ + \STATE $n\gets |\bar a|$ + \STATE $G[n+1][k+1]$ \FOR{$0 \le p \le n$} \FOR{$0 \le d \le k$} \IF{$p = 0$} - \STATE $P[p][d] = 0$ \COMMENT{\autoref{lem:P_0_k}} + \STATE $G[p][d] = 0$ \COMMENT{\autoref{lem:G_0_k}} \ELSIF{$d = 0$} - \STATE $P[p][d] = \PR(S_0^p(\bar p))$ \COMMENT{\autoref{lem:P_p_0}} + \STATE $G[p][d] = \PR(S_0^p(\bar a))$ \COMMENT{\autoref{lem:G_p_0}} \ELSE - \STATE $P[p][d] = \max\left(P[p][d-1], \max\limits_{i=0}^{p-1}\left(P[i][d-1] + \PR(S_i^p(\bar p))\right)\right)$ \COMMENT{\autoref{lem:P_p_k}} + \STATE $G[p][d] = \max\left(G[p][d-1], \max\limits_{i=0}^{p-1}\left(G[i][d-1] + \PR(S_i^p(\bar a))\right)\right)$ \COMMENT{\autoref{lem:G_p_k}} \ENDIF \ENDFOR \ENDFOR - \RETURN $P[n][k]$ + \RETURN $G[n][k]$ \end{algorithmic} \end{algorithm} \begin{thmproof}[maximum-profit]{theorem}{\autoref{alg:maximum-profit} is a correct implementation of the $\PP$ function.} - This follows from \autoref{lem:P_0_k} through \ref{lem:P_p_k}. + This follows from \autoref{lem:G_0_k} through \ref{lem:G_p_k}. \end{thmproof} \subsection{Optimisations} \label{sec:algorithm:optimisations} -A first observation we should make is that values in the input sequence $\bar p$ that are divisible by $5$ do not affect the maximum profit of the substring they're in. +A first observation we should make is that values in the input sequence $\bar a$ that are divisible by $5$ do not affect the maximum profit of the substring they're in. -\begin{thmproof}[divide-by-5]{lemma}{For any $\bar p$, $\PP(\bar p) = \PP\left(\seq{p_i \in\bar p \mid 5\nmid p_i}\right)$.} - No matter in which substring, a $p_i$ which is divisible by $5$ will have no influence on the rounded sum of that substring and thus not on the profit. +\begin{thmproof}[divide-by-5]{lemma}{For any $\bar a$, $\PP(\bar a) = \PP\left(\seq{a_i \in\bar a \mid 5\nmid a_i}\right)$.} + No matter in which substring, an $a_i$ which is divisible by $5$ will have no influence on the rounded sum of that substring and thus not on the profit. \end{thmproof} On average, \autoref{lem:divide-by-5} allows us to apply \autoref{alg:maximum-profit} on a input $\frac54$ times as small as the original input. While not decreasing the Big-O complexity of the algorithm, this does give us faster running times. -Another optimisation concerns the $S$-function. In \autoref{alg:maximum-profit} above, it is called once for every $0\le i\le p$ in every iteration over $p$. Usually we would compute $S$ in linear time, iterating over $\bar p$. Computing \emph{all} the values for $S$ we need would then take quadratic time. However, we may as well use dynamic programming to compute all values for $S$ we're going to need in the beginning of the iteration over $p$, which can be done in linear time. This is demonstrated in \autoref{alg:maximum-profit-optimised}. In this algorithm, \autoref{alg:maximum-profit} has been optimised using \autoref{lem:divide-by-5} and the optimisation just discussed. +Another optimisation concerns the $S$-function. In \autoref{alg:maximum-profit} above, it is called once for every $0\le i\le p$ in every iteration over $p$. Usually we would compute $S$ in linear time, iterating over $\bar a$. Computing \emph{all} the values for $S$ we need would then take quadratic time. However, we may as well use dynamic programming to compute all values for $S$ we're going to need in the beginning of the iteration over $p$, which can be done in linear time. This is demonstrated in \autoref{alg:maximum-profit-optimised}. In this algorithm, \autoref{alg:maximum-profit} has been optimised using \autoref{lem:divide-by-5} and the optimisation just discussed. \begin{algorithm}[h] \footnotesize - \caption{Optimised version of \autoref{alg:maximum-profit}, to compute $\PP_k(\bar p)$} + \caption{Optimised version of \autoref{alg:maximum-profit}, to compute $\PP_k(\bar a)$} \label{alg:maximum-profit-optimised} \begin{algorithmic}[1] - \REQUIRE $\bar p, k$ - \STATE $\bar q\gets\seq{p_i\in\bar p\mid 5\nmid p_i}$ \COMMENT{\autoref{lem:divide-by-5}} - \STATE $n\gets |\bar q|$ - \STATE Initialise $P[n+1][k+1]$ + \REQUIRE $\bar a, k$ + \STATE $\bar a'\gets\seq{a_i\in\bar a\mid 5\nmid a_i}$ \COMMENT{\autoref{lem:divide-by-5}} + \STATE $n\gets |\bar a'|$ + \STATE Initialise $G[n+1][k+1]$ \FOR{$0 \le p \le n$} \STATE Initialise $S[p]$ \COMMENT{Here we exploit dynamic programming to compute $S$} \IF{$p=0$} \STATE $S[0] = 0$ \ELSE - \STATE $S[p-1] = q_{p-1}$ + \STATE $S[p-1] = a'_{p-1}$ \FOR{$i=p-2$ through $0$} - \STATE $S[i] = p_i + S[i+1]$ + \STATE $S[i] = a_i + S[i+1]$ \ENDFOR \ENDIF \FOR{$0 \le d \le k$} \IF{$p = 0$} - \STATE $P[p][d] = 0$ \COMMENT{\autoref{lem:P_0_k}} + \STATE $G[p][d] = 0$ \COMMENT{\autoref{lem:G_0_k}} \ELSIF{$d = 0$} - \STATE $P[p][d] = \PR(S[0])$ \COMMENT{\autoref{lem:P_p_0}} + \STATE $G[p][d] = \PR(S[0])$ \COMMENT{\autoref{lem:G_p_0}} \ELSE - \STATE $P[p][d] = \max\left(P[p][d-1], \max\limits_{i=0}^{p-1}\left(P[i][d-1] + \PR(S[i])\right)\right)$ \COMMENT{\autoref{lem:P_p_k}} + \STATE $G[p][d] = \max\left(G[p][d-1], \max\limits_{i=0}^{p-1}\left(G[i][d-1] + \PR(S[i])\right)\right)$ \COMMENT{\autoref{lem:G_p_k}} \ENDIF \ENDFOR \ENDFOR - \RETURN $P[n][k]$ + \RETURN $G[n][k]$ \end{algorithmic} \end{algorithm} The correctness of \autoref{alg:maximum-profit-optimised} depends on the correctness of \autoref{alg:maximum-profit} which has been proven in \autoref{thm:maximum-profit}. -We can now easily find $\PM_k(\bar p)$ using the equation we saw in \autoref{sec:notation}: $$\PM_k(\bar p) = \sum\bar p - \PP_k(\bar p).$$ +We can now easily find $\PM_k(\bar a)$ using the equation we saw in \autoref{sec:notation}: $$\PM_k(\bar a) = \sum\bar a - \PP_k(\bar a).$$ diff --git a/Practical2/report/analysis.tex b/Practical2/report/analysis.tex new file mode 100644 index 0000000..d989fe6 --- /dev/null +++ b/Practical2/report/analysis.tex @@ -0,0 +1,18 @@ +\section{Complexity analysis} +\label{sec:analysis} + +We iterate $p$ in $\pazocal O(|\bar a'|) = \pazocal O(|\bar a|)$. In every iteration we do two things: + +\begin{itemize} + \item We build $S$ in $\pazocal O(p)=\pazocal O(|\bar a|)$. + \item We iterate $d$ in $\pazocal O(k)$. Apart from the special cases that $p=0$ or $d=0$, we then have to iterate over $i$ in $\pazocal O(p)=\pazocal O(|\bar a|)$. + + The computations in this last loop take constant time: $\PR$ can be implemented in constant time as has been seen in \autoref{sec:implementation}, and computing the maximum can be done while iterating over $i$. +\end{itemize} + +This gives a total time complexity of $\pazocal O(k\cdot|\bar a|^2)$. + +\medskip + +The algorithm uses a two-dimensional array $G$ to store solutions to subproblems. This array uses $\pazocal O(k\cdot|\bar a|)$ space. The auxiliary array $S$ takes only linear space in $|\bar a|$ and can therefore be ignored in the overall space complexity. This gives the algorithm a space complexity of $\pazocal O(k\cdot|\bar a|)$. + diff --git a/Practical2/report/implementation.tex b/Practical2/report/implementation.tex new file mode 100644 index 0000000..cc8a940 --- /dev/null +++ b/Practical2/report/implementation.tex @@ -0,0 +1,19 @@ +\section{Implementation} +\label{sec:implementation} + +A C implementation accompanies this report. The $\PR$ function is implemented in $\pazocal O(1)$ in \mintinline{c}{round_profit}, but is not shown here for the sake of brevity. + +The implementation of the $\PP$ function, \mintinline{c}{maximum_profit}, follows the flow of \autoref{alg:maximum-profit-optimised}. However, it was easier to take the optimisation of \autoref{lem:divide-by-5} out of this function and apply it when reading in the input sequence. + +\inputminted[fontsize=\footnotesize,linenos,firstline=17,lastline=48]{c}{../checkout.c} + +In the \mintinline{c}{main} function we see how \autoref{lem:divide-by-5} can be applied. In the last line we also see how the minimal sum may be computed from the maximum profit. + +\inputminted[fontsize=\footnotesize,linenos,firstline=50,lastline=67]{c}{../checkout.c} + +\subsection{Compilation} +\label{sec:implementation:compilation} +Optimal results are achieved with \texttt{clang}, which is on average $25\%$ faster than \texttt{gcc}. In any case, the \texttt{-Ofast} flag should be used. It speeds up the program with a factor $4$ in the case of \texttt{clang} and a factor $3$ in the case of \texttt{gcc}. + +A Makefile accompanies the C code. If you don't have \texttt{clang} installed, you should install it. If you don't want to install it, use \mintinline{bash}{make CC=gcc}. + diff --git a/Practical2/report/notation.tex b/Practical2/report/notation.tex index d21295e..cbbbc1d 100644 --- a/Practical2/report/notation.tex +++ b/Practical2/report/notation.tex @@ -1,11 +1,9 @@ \section{Notation} \label{sec:notation} -Given a list of $n$ numbers $p_0,p_1,\dots,p_{n-1}$, we consider one of its partitions in $k$ (possibly empty) pairwise disjoint substrings such that the sum of the sums of the substrings, rounded to multiples of $5$, is minimal. Output that minimal sum. +I will write $\bar a = \seq{a_i \mid i<n}$ for the sequence of numbers and $k$ for the number of substrings. I redefine $\round{x}$ to mean `the nearest multiple of $5$ to $x$'. We may define the `round profit' as $\PR(x)=x-\round{x}$. -I will write $\bar p = \seq{p_i \mid i<n}$ for the sequence of numbers and $k$ for the number of substrings. I redefine $\round{x}$ to mean `the nearest multiple of $5$ to $x$'. We may define the `round profit' as $\PR(x)=x-\round{x}$. +Let $\PM_k(\bar a)$ be the minimal sum of rounded sums of $\bar a$ using $k$ partitions. I will use $\PP_k(\bar a)$ as the `maximum profit' of $\bar a$, that is, $\PP_k(\bar a) = \sum\bar a - \PM_k(\bar a)$. This leads to the term `profit' of a particular partitioning of $\bar a$ and of a particular (sub)string $\bar a'$, for which we need not introduce notation. The profit of a string $\bar a'$ is defined as $\PR(\sum\bar a)$. It is not difficult to see that the profit of a partition is equal to the some of the profits of its members. -Let $\PM_k(\bar p)$ be the minimal sum of rounded sums of $\bar p$ using $k$ partitions. I will use $\PP_k(\bar p)$ as the `maximum profit' of $\bar p$, that is, $\PP_k(\bar p) = \sum\bar p - \PM_k(\bar p)$. This leads to the term `profit' of a particular partitioning of $\bar p$ and of a particular (sub)string $\bar q$, for which we need not introduce notation. The profit of a string $\bar q$ is defined as $\PR(\sum\bar q)$. It is not difficult to see that the profit of a partition is equal to the some of the profits of its members. - -I will write $P^k_p(\bar p)$ for $\PP_k(\seq{p_i\in\bar p\mid i<p})$ (that is, the maximal profit on $\bar p$'s prefix with length $p$ using $k$ partitions). Lastly, let $S_i^j(\bar p)$ be the sum of all $p_x\in\bar p$ with $i\le x<j$. +We define the gain $G^k_p(\bar a)$ as $\PP_k(\seq{a_i\in\bar a\mid i<p})$ (that is, the maximal profit on $\bar a$'s prefix with length $p$ using $k$ partitions). Lastly, let $S_i^j(\bar a)$ be the sum of all $p_x\in\bar a$ with $i\le x<j$. diff --git a/Practical2/report/report.tex b/Practical2/report/report.tex index 4c71eee..2aeb621 100644 --- a/Practical2/report/report.tex +++ b/Practical2/report/report.tex @@ -63,7 +63,9 @@ \thispagestyle{fancy} \begin{abstract} - %todo + Given a list of $n$ numbers $a_0, a_1, \dots, a_{n-1}$, we consider one of its partitions in $k$ (possibly empty) pairwise disjoint substrings such that the sum of the sums of the substrings, rounded to multiples of $5$, is minimal. + + This paper describes an algorithm to find the minimal sum for such a partition. It can easily be extended to find such a partition as well. \end{abstract} \section{Report organisation} @@ -73,8 +75,8 @@ When we have seen the algorithm, \autoref{sec:implementation} will go into detai \input{notation} \input{algorithm} -%\input{implementation} -%\input{analysis} +\input{implementation} +\input{analysis} %\input{discussion} \end{document} |