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

