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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
|
\documentclass[10pt,a4paper]{article}
\usepackage[margin=2cm]{geometry}
\usepackage{enumitem}
\setenumerate[1]{label=2.\arabic*.}
\setenumerate[2]{label=\textit{\alph*})}
% textcomp package is not available everywhere, and we only need the Copyright symbol
% taken from http://tex.stackexchange.com/a/1677/23992
\DeclareTextCommandDefault{\textregistered}{\textcircled{\check@mathfonts\fontsize\sf@size\z@\math@fontsfalse\selectfont R}}
\usepackage{fancyhdr}
\renewcommand{\headrulewidth}{0pt}
\renewcommand{\footrulewidth}{0pt}
\fancyhead{}
\fancyfoot[C]{Copyright {\textcopyright} 2015 Camil Staps}
\pagestyle{fancy}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\DeclareMathAlphabet{\pazocal}{OMS}{zplm}{m}{n}
\usepackage{mathtools}
\DeclarePairedDelimiter{\ceil}{\lceil}{\rceil}
\DeclarePairedDelimiter{\floor}{\lfloor}{\rfloor}
\usepackage{minted}
\parindent0pt
\title{Algoritmen en Datastructuren - assignment 2}
\author{Camil Staps\\\small{s4498062}}
\begin{document}
\maketitle
\thispagestyle{fancy}
\begin{enumerate}
\item \begin{enumerate}
\item Claim: $T(n) \in\pazocal O\left(n^2\right)$.
\begin{proof}
With induction over $n$ we prove $T(n) \leq 3\cdot\frac{n(n+1)}{2}$ for all $n\in\mathbb N$.
\textbf{Induction basis}: for $n=0$ we have $T(n) \leq 3\cdot n = 0 = 3\cdot\frac{n(n+1)}{2}$.
\textbf{Inductive step}: let's assume $T(k) \leq 3\cdot\frac{k(k+1)}{2}$ for some $k\in\mathbb N$ (IH). Then for $k+1$:
\begin{align*}
T(k+1) &\leq T(k) + 3(k+1)\\
&\leq 3\cdot\frac{k(k+1)}{2} + 3k + 1 \qquad\text{(IH)}\\
&= 1\frac12\left(k^2+3k\right) + 1\\
&\leq 1\frac12\left(k^2+3k+2\right)\\
&= 3\cdot\frac{(k+1)(k+2)}{2}.
\end{align*}
So we see that if $T(k)\leq3\cdot\frac{k(k+1)}{2}$ for some $k\in\mathbb N$, also $T(k+1)\leq3\cdot\frac{(k+1)(k+2)}{2}$. From the principle of induction now follows that for all $n\in\mathbb N$ we have $T(n) \leq 3\cdot\frac{n(n+1)}{2}$.
Now since $3\cdot\frac{n(n+1)}{2}$ has order $n^2$, also $T(n)\in\pazocal O\left(n^2\right)$.
\end{proof}
\item Claim: $T(n) \in\pazocal O\left(\ln n\right)$.
\begin{proof}
With induction over $n$ we prove $T(n) \leq 42\log_2 n$ for all $n \in\mathbb N, n>1$.
\textbf{Induction basis}: for $n=2$ we have $T(n) = T\left(\frac n2\right)+42 = 42 \leq 42\log_2 n$.
\textbf{Inductive step}: let's assume for some $k\in\mathbb N$ that $T(k') \leq 42\log_2k'$ for all $k'\in\{n\in\mathbb N\mid n>1\}, k'<k$ (IH). Then for $k$:
\begin{align*}
T(k) &\leq T\left(\tfrac k2\right) + 42\\
&\leq 42\log_2\left(\tfrac k2\right) + 42 \qquad\text{(IH)}\\
&= 42\left(\log_2k - \log_22\right) + 42\\
&= 42\log_2k.
\end{align*}
From the principle of induction now follows that for all $n\in\mathbb N$ we have $T(n)\leq 42\log_2n$.
Now since $42\log_2n \in\pazocal O(\ln n)$, also $T(n)\in\pazocal O(\ln n)$.
\end{proof}
\item Claim: $T(n) \in\pazocal O(\ln n)$.
\begin{proof}
With induction over $n$ we prove there exists some $c\in\mathbb N$ s.t. $T(n)\leq c\cdot\log_3n$ for all $n\in\mathbb{N},n>4$.
\textbf{Induction basis}: for $n=5$ we have $T(n) = 3T(\frac n3)+13 = 13 \leq c\log_3n$ with $c=13$ for example.
\textbf{Inductive step}: let's assume for some $k\in\mathbb N$ that $T(k') \leq c_{k'}\log_3k'$ for all $k'\in\{n\in\mathbb N\mid n>4\}$, $k'<k$ (IH). Then for $k$:
\begin{align*}
T(k) &\leq 3T\left(\tfrac k3\right) + 13\\
&\leq 3\cdot c\log_3\left(\tfrac k3\right) + 13 \qquad\text{with $c=c_{\left(\tfrac k3\right)}$}\\
&= 3c\cdot(\log_3k - 1) + 13\\
&= 3c\cdot\log_3k + 13 - 3c \qquad\text{$3c>13$ for $c>4$, therefore:}\\
&\leq 3c\cdot\log_3k\\
&= c'\cdot\log_3k \qquad\text{with $c'=3c$}.
\end{align*}
So under the assumption of the IH for $k'<k$ we see there exists a $c\in\mathbb N$ s.t. $T(k) \leq c\cdot\log_3 k$.
From the principle of induction this now follows for any $k\in\{n\in\mathbb N\mid n>4\}$.
Now since $c\cdot\log_3n \in\pazocal O(\ln n)$ we also have $T(n)\in\pazocal O(\ln n)$.
\end{proof}
\item Claim: $T(n) \in\pazocal O(n\ln n)$.
\begin{proof}
With induction over $n$ we prove there exists some $c\in\mathbb N^+$ s.t. $(T(n)\leq c\cdot n\cdot\log_4n$ for all $n\in\mathbb N,n>4$.
\textbf{Induction basis}: for $n=5$ we have $T(n) = 4T(\frac n4)+n = n \leq c\cdot n\log_4n$ with $c=1$ for example.
\textbf{Inductive step}: let's assume for some $k\in\mathbb N$ that $T(k') \leq c_{k'}\cdot k'\cdot\log_4k'$ for all $k'\in\{n\in\mathbb N\mid n>4\}$, $k'<k$ (IH). Then for $k$:
\begin{align*}
T(k) &\leq 4T\left(\tfrac k4\right) + k\\
&\leq 4\cdot c\cdot \tfrac k4\cdot\log_4\tfrac k4 + k\\
&= c\cdot k\cdot(\log_4k - 1) + k\\
&= c\cdot k\cdot\log_4k + (1-c)k \qquad\text{and since $c\in\mathbb N^+$\dots}\\
&\leq c\cdot k\cdot\log_4k.
\end{align*}
So under the assumption of the IH for $k'<k$ we see there exists a $c\in\mathbb N$ s.t. $T(k)\leq c\cdot k\cdot\log_4 k$.
From the principle of induction this now follows for any $k\in\{n\in\mathbb N\mid n>4\}$.
Now since $c\cdot n\cdot\log_4n \in\pazocal O(n\ln n)$ we also have $T(n)\in\pazocal O(n \ln n)$.
\end{proof}
\end{enumerate}
\item \begin{enumerate}
\item The algorithm is performs equally well on sorted and unsorted lists. However, it performs better on lists with size (close to) $2^n$ for some $n\in\mathbb N$, since it needs a minimum amount of \texttt{merge} calls in that case. The best case would be a list of size $2^n$ for some $n\in\mathbb N$, the worst case a list of size in between $2^n$ and $2^{n+1}$, that is, $1\frac12\cdot2^n$ for some $n\in\mathbb N$.
\item Dividing takes constant time, i.e. $\Theta(1)$. Conquering takes $T(\ceil{\frac n2})+T(\floor{\frac n2})$. Composing takes linear time, $\Theta(n)$ in the \texttt{merge} function and once again linear time in the final \texttt{for} loop in \texttt{mergesort}. That gives:
$$T(n) \leq T\left(\ceil*{\tfrac n2}\right) + T\left(\floor*{\tfrac n2}\right) + c, \qquad c\in\mathbb N$$
\item This is essentially the same as 2.1d, so this is $\pazocal{O}(n\ln n)$.
\item As said in 2.2a, the worst and best case complexity is the same, so we also have $\Omega(n\ln n)$.
\end{enumerate}
\item \begin{enumerate}
\item \begin{proof}
Since $f\in\pazocal O(h)$, there exists a $c_f\in\mathbb N$ and $n_{0,f}\in\mathbb N$ s.t. for all $n>n_0$ we have $c_f\cdot h(n)\geq f(n)$. Similarly we have $c_g$ and $n_{0,g}$ with respect to $g$.
Then let $c=c_f + c_g, n_0 = \text{max}(n_{0,f},n_{0,g})$. By the above we know $(c_f + c_g)\cdot h(n) \geq f(n) + g(n)$ for all $n>n_0$. It follows from substitution that $c\cdot h(n)\geq f(n) + g(n)$, and therefore $f + g \in\pazocal O(h)$.
\end{proof}
\item \begin{proof}
For $n\in\mathbb N$ we know $n^m\geq n^k$ (since $k\leq m$). We can thus choose $c=1,n_0=0$ to find that for all $n>n_0$ it holds that $n^k \leq c\cdot n^m$. Therefore, $n^k\in\pazocal O\left(n^m\right)$.
\end{proof}
\item \begin{proof}
From (b) we know that all terms ($c_kn^k$, $c_{k-1}n^{k-1}$, etc.) are in $\pazocal O\left(n^k\right)$. From (a) it then follows that their sum is also in $\pazocal O\left(n^k\right)$.
\end{proof}
\end{enumerate}
\item \begin{enumerate}
\item \begin{minted}[tabsize=0,linenos,xleftmargin=20pt,fontsize=\footnotesize]{c}
int findzerosum(float* a, float* b, unsigned int n, float* out) {
unsigned int ai, bi; // counters
bi = n - 1; // start b at the max. element
for (ai = 0; ai < n; ai++) { // start a at the min. element
while (a[ai] + b[bi] > 0) bi--; // as long as b > -a, choose lower b
if (a[ai] + b[bi] == 0) { // if a = -b, return a, b and success
out[0] = a[ai];
out[1] = b[bi];
return 0;
} // otherwise, choose higher a
}
return -1; // if all as checked but nothing found, return failure
}
\end{minted}
The worst case is that we need the highest element from $a$ and the lowest element from $b$, meaning we need to iterate both lists fully. In that case we need $2n+c$ operations for some $n,c\in\mathbb N$: $2n$ for iterating and checking the elements, and $c$ for returning the correct elements.
This shows we have a worst-case complexity of $\pazocal O(n)$. The best case is to find the right elements directly; in this case we need constant time.
\item We first rewrite our answer from \textit{(a)} to support other `goals' than zero:
\begin{minted}[tabsize=0,linenos,xleftmargin=20pt,fontsize=\footnotesize]{c}
int findsum(float* a, float* b, unsigned int n, float goal, float* out) {
unsigned int ai, bi;
bi = n - 1;
for (ai = 0; ai < n; ai++) {
while (a[ai] + b[bi] > goal) bi--; // this line changed
if (a[ai] + b[bi] == goal) { // this line changed
out[0] = a[ai];
out[1] = b[bi];
return 0;
}
}
return -1;
}
\end{minted}
%stopzone
Then for arrays $a,b,c$ we iterate over $a$ and try to find elements in $b$ and $c$ that fit using the algorithm above:
\begin{minted}[tabsize=0,linenos,firstnumber=last,xleftmargin=20pt,fontsize=\footnotesize]{c}
int findzerosum3(float* a, float* b, float* c, unsigned int n, float* out) {
unsigned int ai; // counter
for (ai = 0; ai < n; ai++) { // for every a in [a]
if (0 == findsum(b, c, n, -a[ai], out)) { // if we can find elements in b and c that fit
out[2] = a[ai]; // store values and return success
return 0;
} // otherwise, choose next a
}
return -1; // when [a] is exhausted, return failure
}
\end{minted}
Note that this would also work when $a$ is not sorted. The worst-case complexity of \texttt{findsum} is, as discussed above, in $\pazocal O(n)$. The worst-case complexity of \texttt{findzerosum3} is than $\pazocal O(n^2)$, because \texttt{findsum} is executed at most $n$ times, and the rest of the algorithm uses constant time.
\end{enumerate}
\end{enumerate}
\end{document}
|
