1 files changed, 93 insertions, 0 deletions
diff --git a/assignment2.tex b/assignment2.tex
new file mode 100644
index 0000000..f8c76cb
--- /dev/null
+++ b/assignment2.tex
@@ -0,0 +1,93 @@
+\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 %todo
+
+    \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 %todo
+            \item %todo
+        \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 (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 error
+					}
+                \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 %todo
+        \end{enumerate}
+\end{enumerate}
+
+\end{document}
+