aboutsummaryrefslogtreecommitdiff
path: root/Practical2/report/report.tex
blob: 96ec502786cdd2eb5a73d5eb8b58791bbad01463 (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
\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{Maximising the Rounding Advantage of a Division of a List Into Sublists}
\author{Camil Staps}

\begin{document}

\maketitle
\thispagestyle{fancy}

\begin{abstract}
    Given a list of $n$ numbers $a_0, a_1, \dots, a_{n-1}$, we consider one of its partitions in $k+1$ (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}
\autoref{sec:notation} will define the notation used throughout this report. In \autoref{sec:algorithm} I will describe the algorithm and argue its correctness.

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.

We finish in \autoref{sec:future-work} with a discussion about possible future work.

\input{notation}
\input{algorithm}
\input{implementation}
\input{analysis}
\input{future-work}

\end{document}