From a61b998270e8f955c603de96775e072a555f735d Mon Sep 17 00:00:00 2001
From: Gregor Kleen <gkleen@yggdrasil.li>
Date: Tue, 19 Apr 2016 15:21:02 +0200
Subject: AlgoDat 01

---
 ss2016/algodat/01/H1-1.md        | 32 +++++++++++++++++++++++++++
 ss2016/algodat/01/H1-2.md        | 10 +++++++++
 ss2016/algodat/01/MergeSort.java | 48 ++++++++++++++++++++++++++++++++++++++++
 ss2016/algodat/01/manifest       |  3 +++
 4 files changed, 93 insertions(+)
 create mode 100644 ss2016/algodat/01/H1-1.md
 create mode 100644 ss2016/algodat/01/H1-2.md
 create mode 100644 ss2016/algodat/01/MergeSort.java
 create mode 100644 ss2016/algodat/01/manifest

(limited to 'ss2016/algodat')

diff --git a/ss2016/algodat/01/H1-1.md b/ss2016/algodat/01/H1-1.md
new file mode 100644
index 0000000..d93f86c
--- /dev/null
+++ b/ss2016/algodat/01/H1-1.md
@@ -0,0 +1,32 @@
+a)
+
+\begin{algorithmic}[1]
+  \FORALL{entries $e$ on the shopping list}
+    \STATE{$c \leftarrow \text{category of $e$}$}
+    \STATE{Go to shelf $s$ labeled $c$}
+    \FORALL{products $p$ on $s$} \label{alg:loopstart}
+      \IF{$p$ matches $e$} 
+        \STATE{add $p$ to shopping basket}
+        \STATE{break out of loop started in line \ref{alg:loopstart}}
+      \ENDIF
+    \ENDFOR
+  \ENDFOR
+\end{algorithmic}
+
+b)
+
+\begin{algorithmic}[1]
+  \WHILE{not at destination within forest}
+    \STATE{break crumb of bread}
+    \STATE{drop crumb}
+    \STATE{take step towards destination}
+  \ENDWHILE
+  \WHILE{not out of forest}
+    \IF{we see at least one crumb}
+      \STATE{Go to the closest one}
+      \STATE{Pick it up}
+    \ELSE
+      \STATE{Get eaten by a witch}
+    \ENDIF
+  \ENDWHILE
+\end{algorithmic}
diff --git a/ss2016/algodat/01/H1-2.md b/ss2016/algodat/01/H1-2.md
new file mode 100644
index 0000000..7a50a2a
--- /dev/null
+++ b/ss2016/algodat/01/H1-2.md
@@ -0,0 +1,10 @@
+\begin{align*}
+  L &= \lim_{n \to \infty} \frac{n \cdot 2^n}{n^n} \\
+    &= \lim_{n \to \infty} \frac{2^{\log_2(n) + n}}{2^{\log_2(n) \cdot n}} \\
+    &= \lim_{n \to \infty} 2^{n + \log_2(n) - \log_2(n) \cdot n} \\
+  n + \log(n) - \log(n) \cdot n &\leq 2n - \log(n) \cdot n \\
+    &= (2 - \log(n)) \cdot n \xrightarrow{n \to \infty} - \infty \\
+  L &= 0
+\end{align*}
+
+$n \cdot 2^n$ und $n^n$ sind also sogar in der selben Komplexitätsklasse.
diff --git a/ss2016/algodat/01/MergeSort.java b/ss2016/algodat/01/MergeSort.java
new file mode 100644
index 0000000..97f7cfa
--- /dev/null
+++ b/ss2016/algodat/01/MergeSort.java
@@ -0,0 +1,48 @@
+import java.util.*;
+
+class MergeSort {
+    public static void mergeSort(int[] a, int from, int to) {
+        if (from >= to)
+            return;
+        
+        int mid = (from + to) / 2;
+        mergeSort(a, from, mid);
+        mergeSort(a, mid + 1, to);
+        merge(a, from, mid, to);
+    }
+
+    public static void merge(int[] a, int from, int mid, int to) {
+        int[] b = new int[to - from + 1];
+
+        int i, j;
+        i = from;
+        j = mid + 1;
+        
+        for (int k = 0; k < b.length; k++) {
+            if (j > to || (i <= mid && a[i] < a[j])) {
+                b[k] = a[i];
+                i++;
+            } else {
+                b[k] = a[j];
+                j++;
+            }
+        }
+
+        for (int k = 0; k < b.length; k++) {
+            a[k + from] = b[k];
+        }
+    }
+    
+    public static void mergeSort(int[] a) {
+        mergeSort(a, 0, a.length - 1);
+    }
+    
+    public static void main (String[] argv) {
+        int[] a = new int[argv.length];
+        for (int i = 0; i < argv.length; i++)
+            a[i] = Integer.parseInt(argv[i]);
+        
+        mergeSort(a);
+        System.out.println(Arrays.toString(a));
+    }
+}
diff --git a/ss2016/algodat/01/manifest b/ss2016/algodat/01/manifest
new file mode 100644
index 0000000..d76cd81
--- /dev/null
+++ b/ss2016/algodat/01/manifest
@@ -0,0 +1,3 @@
+H1-1.pdf
+H1-2.pdf
+MergeSort.java
\ No newline at end of file
-- 
cgit v1.2.3