Assignment 12

1 files changed, 92 insertions, 0 deletions

diff --git a/assignment12.tex b/assignment12.tex
new file mode 100644
index 0000000..723f7ab
--- /dev/null
+++ b/assignment12.tex
@@ -0,0 +1,92 @@
+\documentclass[10pt,a4paper]{article}
+
+\usepackage[margin=2cm,top=1cm]{geometry}
+\usepackage{multicol}
+
+\def\assignment{12}
+
+\usepackage{enumitem}
+\setenumerate[1]{label=\assignment.\arabic*.}
+\setenumerate[2]{label=\textit{\alph*})}
+
+\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{tikz}
+\usepackage{array}
+\usepackage{caption}
+\usepackage[hidelinks]{hyperref}
+\usepackage{minted}
+
+\parindent0pt
+
+\title{Algoritmen en Datastructuren - assignment \assignment}
+\author{Camil Staps\\\small{s4498062}}
+
+\begin{document}
+
+\maketitle
+\thispagestyle{fancy}
+
+\begin{multicols}{2}
+
+\begin{enumerate}
+    \item \begin{minted}[linenos,tabsize=0,xleftmargin=20pt,fontsize=\footnotesize]{python}
+			def select(A, i):
+			    while len(A) != 1:
+			        p = A[random(1, len(A))]
+			        L = [a for a in A if a <= p]
+			        H = [a for a in A if a > p]
+			        if i <= len(L):
+			            A = L
+			        else:
+			            A = H
+			            i = i - len(L)
+			    return A[0]
+        \end{minted}
+
+        The complexity is the same as for the recursive version, because the iterative version doesn't introduce overhead.
+
+    \item We exploit the binary representation of the generated number.
+
+        \begin{minted}[linenos,tabsize=0,xleftmargin=20pt,fontsize=\footnotesize]{python}
+			def rand(n):
+			    if n == 0:
+			        return 0
+			    return 2 * rand(n-1) + coin()
+        \end{minted}
+
+        This takes $\pazocal O(n)\cdot\pazocal O(\textsc{Coin})$, because in every step $n$ is reduced by one.
+
+    \item \begin{enumerate}
+            \item I'm assuming that `as efficient as possible' is considering the worst case efficiency.
+
+                In the worst case, we should just take \textsc{Det-Prim}; in the worst case \textsc{Rand-Prime} returns ambiguous answers so we need to run \textsc{Det-Prim} at least once, and then executing \textsc{Rand-Prime} is pointless.
+
+            \item $100T(n)$.
+
+            \item Idem.
+        \end{enumerate}
+
+    \item %todo
+
+    \item \begin{enumerate}
+            \item $n$ times, if the random ordering of the array elements is strictly descending.
+            \item This is the probability that the minimum element is visited the latest. There are $n!$ $n$-permutations, and $(n-1)!$ of them have that element on the last position. The probability is therefore $\frac{(n-1)!}{n!}=\frac1n$.
+            \item With a similar argument, the probability the line is executed in the $k$th iteration is $\frac1k$. Therefore, the expected number of executions is $$\sum_{k=1}^{n}\tfrac1k.$$
+        \end{enumerate}
+\end{enumerate}
+
+\end{multicols}
+
+\end{document}
+