Start report practical 2

3 files changed, 199 insertions, 0 deletions

diff --git a/Practical2/report/algorithm.tex b/Practical2/report/algorithm.tex
new file mode 100644
index 0000000..73780f0
--- /dev/null
+++ b/Practical2/report/algorithm.tex
@@ -0,0 +1,107 @@
+\section{Algorithm}
+\label{sec:algorithm}
+
+I will propose a solution that uses dynamic programming. First, I will describe the general structure of the algorithm, and simultaneously argue its correctness. After this, we will discuss some optimisations.
+
+\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.
+\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.
+\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{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)$.
+    \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).$$
+
+\begin{algorithm}[h]
+    \footnotesize
+    \caption{Finding the maximum profit $\PP_k(\bar p)$ of sequence $\bar p$ 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]$
+        \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}}
+                \ELSIF{$d = 0$}
+                    \STATE $P[p][d] = \PR(S_0^p(\bar p))$ \COMMENT{\autoref{lem:P_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}}
+                \ENDIF
+            \ENDFOR
+        \ENDFOR
+        \RETURN $P[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}.
+\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.
+
+\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.
+\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.
+
+\begin{algorithm}[h]
+    \footnotesize
+    \caption{Optimised version of \autoref{alg:maximum-profit}, to compute $\PP_k(\bar p)$}
+    \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]$
+        \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}$
+                \FOR{$i=p-2$ through $0$}
+                    \STATE $S[i] = p_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}}
+                \ELSIF{$d = 0$}
+                    \STATE $P[p][d] = \PR(S[0])$ \COMMENT{\autoref{lem:P_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}}
+                \ENDIF
+            \ENDFOR
+        \ENDFOR
+        \RETURN $P[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).$$
+
diff --git a/Practical2/report/notation.tex b/Practical2/report/notation.tex
new file mode 100644
index 0000000..d21295e
--- /dev/null
+++ b/Practical2/report/notation.tex
@@ -0,0 +1,11 @@
+\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 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 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$.
+
diff --git a/Practical2/report/report.tex b/Practical2/report/report.tex
new file mode 100644
index 0000000..4c71eee
--- /dev/null
+++ b/Practical2/report/report.tex
@@ -0,0 +1,81 @@
+\documentclass[10pt,a4paper]{article}
+
+\usepackage{fancyhdr}
+\renewcommand{\headrulewidth}{0pt}
+\renewcommand{\footrulewidth}{0pt}
+\fancyhead{}
+\fancyfoot[C]{Copyright {\textcopyright} 2015 Camil Staps}
+\pagestyle{fancy}
+
+\usepackage{enumitem}
+
+\usepackage{amsmath}
+\usepackage{amssymb}
+\usepackage{amsthm}
+\usepackage{amsfonts}
+\DeclareMathAlphabet{\pazocal}{OMS}{zplm}{m}{n}
+
+\usepackage[hidelinks]{hyperref}
+\usepackage{url}
+
+\newcommand*\PM{\pazocal M}
+\newcommand*\PP{\pazocal P}
+\newcommand*\PR{\pazocal R}
+\newcommand*\round[1]{\lfloor #1\rceil}
+\newcommand*\seq[1]{\left\langle #1\right\rangle}
+
+\providecommand*{\lemmaautorefname}{Lemma}
+\newtheorem{lemma}{Lemma}
+\newtheorem{theorem}{Theorem}
+\numberwithin{lemma}{section}
+\numberwithin{theorem}{section}
+
+\newenvironment{thmproof}[3][]{%
+    \begin{samepage}
+    \begin{#2}%
+        \def\templabel{#1}%
+        \def\tempname{#2}%
+        \def\temptheorem{theorem}%
+        \ifx\templabel\empty\else\ifx\tempname\temptheorem\label{thm:#1}\else\label{lem:#1}\fi\fi%
+        #3%
+    \end{#2}%
+    \begin{proof}%
+}{\end{proof}\end{samepage}}
+
+\newcommand{\refeq}[2][]{\begin{equation}\label{eq:#1}#2\end{equation}}
+
+\usepackage{algorithm}
+\usepackage{algorithmic}
+\providecommand*{\algorithmautorefname}{Algorithm}
+
+\renewcommand*{\sectionautorefname}{Section}
+\renewcommand*{\subsectionautorefname}{subsection}
+\renewcommand*{\subsubsectionautorefname}{subsection}
+
+\usepackage{minted}
+
+\title{How To Save Less Money Than Your CPU Costs} %todo working title
+\author{Camil Staps}
+
+\begin{document}
+
+\maketitle
+\thispagestyle{fancy}
+
+\begin{abstract}
+    %todo
+\end{abstract}
+
+\section{Report organisation}
+\autoref{sec:notation} will define the notation used throughout this report. In \autoref{sec:algorithm} I will describe the algorithm and argue its correctness. First, we will discuss the basic structure in \autoref{sec:algorithm:general}. After that, I will show some optimisations in \autoref{sec:algorithm:optimisations}.
+
+When we have seen the algorithm, \autoref{sec:implementation} will go into details about its implementation in C. \autoref{sec:analysis} will contain a complexity analysis, both time- and space-wise, of the algorithm and its C implementation.
+
+\input{notation}
+\input{algorithm}
+%\input{implementation}
+%\input{analysis}
+%\input{discussion}
+
+\end{document}
+