From 52a67a6466a4bc10f809f1fb68e2db5830c05f64 Mon Sep 17 00:00:00 2001
From: Camil Staps
Date: Fri, 11 Dec 2015 13:19:52 +0000
Subject: Finish first version report practical 2

Some changes were made to the code and the Makefile to clean up, make it
more in line with the algorithm as described in the report, etc. No
significant changes.
---
 Practical2/report/algorithm.tex | 68 ++++++++++++++++++++---------------------
 1 file changed, 34 insertions(+), 34 deletions(-)

(limited to 'Practical2/report/algorithm.tex')

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).$$
 
-- 
cgit v1.2.3