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