From bc5f7b00e652f7eb23476359b1cbab4bb0504ad9 Mon Sep 17 00:00:00 2001 From: Camil Staps Date: Mon, 14 Sep 2015 14:40:59 +0200 Subject: Finish assignment 2 --- assignment2.tex | 135 +++++++++++++++++++++++++++++++++++++++++++++++++++++--- 1 file changed, 129 insertions(+), 6 deletions(-) (limited to 'assignment2.tex') diff --git a/assignment2.tex b/assignment2.tex index f8c76cb..930aea0 100644 --- a/assignment2.tex +++ b/assignment2.tex @@ -38,15 +38,103 @@ \thispagestyle{fancy} \begin{enumerate} - \item %todo + \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'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'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'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'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 %todo - \item %todo + \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} @@ -67,7 +155,7 @@ \item \begin{enumerate} \item \begin{minted}[tabsize=0,linenos,xleftmargin=20pt,fontsize=\footnotesize]{c} - int (float* a, float* b, unsigned int n, float* out) { + 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 @@ -78,14 +166,49 @@ return 0; } // otherwise, choose higher a } - return -1; // if all as checked but nothing found, return error + 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 %todo + + \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} -- cgit v1.2.3