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}
|
