1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
|
\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}
|
