sawine@0
|
1 |
\documentclass[a4paper, 10pt, pagesize, smallheadings]{article}
|
sawine@0
|
2 |
\usepackage{graphicx}
|
sawine@0
|
3 |
%\usepackage[latin1]{inputenc}
|
sawine@0
|
4 |
\usepackage{amsmath, amsthm, amssymb}
|
sawine@0
|
5 |
\usepackage{typearea}
|
sawine@0
|
6 |
\usepackage{algorithm}
|
sawine@0
|
7 |
\usepackage{algorithmic}
|
sawine@0
|
8 |
\usepackage{fullpage}
|
sawine@0
|
9 |
\usepackage[all]{xy}
|
sawine@0
|
10 |
\title{Theory I, Sheet 4 Solution}
|
sawine@0
|
11 |
\author{Eugen Sawin}
|
sawine@0
|
12 |
\renewcommand{\familydefault}{\sfdefault}
|
sawine@0
|
13 |
\include{pythonlisting}
|
sawine@0
|
14 |
|
sawine@0
|
15 |
|
sawine@0
|
16 |
\pagestyle{empty}
|
sawine@0
|
17 |
\begin{document}
|
sawine@0
|
18 |
\maketitle
|
sawine@0
|
19 |
|
sawine@0
|
20 |
\section*{Exercise 4.1}
|
sawine@0
|
21 |
\begin{figure}[h]
|
sawine@0
|
22 |
\entrymodifiers={}
|
sawine@0
|
23 |
\xymatrix
|
sawine@0
|
24 |
{
|
sawine@0
|
25 |
& & *++[o][F-]{50} \ar@{-}[dl] \ar@{-}[dr] & & & & & & *++[o][F-]{50} \ar@{-}[dl] \ar@{-}[dr]\\
|
sawine@2
|
26 |
& *++[o][F-]{30} \ar@{-}[dl] \ar@{-}[dr] & & *++[o][F-]{60} \ar@{-}[dr] & \ar@{=>}[rr]^{delete(40)}_{upout(30)} & & & *++[o][F-]{30} \ar@{-}[dl] & & *++[o][F-]{60}\ar@{-}[dr]\\
|
sawine@0
|
27 |
*++[o][F-]{20} & & *++[o][F-]{40} & & *++[o][F-]{70} & & *++[o][F-]{20} & & & & *++[o][F-]{70}\\
|
sawine@0
|
28 |
}
|
sawine@0
|
29 |
\end{figure}
|
sawine@0
|
30 |
\begin{figure}[h]
|
sawine@0
|
31 |
\xymatrix
|
sawine@0
|
32 |
{
|
sawine@0
|
33 |
& & *++[o][F-]{50} \ar@{-}[dl] \ar@{-}[dr] & & & & & & *++[o][F-]{50} \ar@{-}[dl] \ar@{-}[dr]\\
|
sawine@2
|
34 |
& *++[o][F-]{30} \ar@{-}[dl] & & *++[o][F-]{60} \ar@{-}[dr] & \ar@{=>}[rr]^{delete(60)}_{upout(50)} & & & *++[o][F-]{30} \ar@{-}[dl] & & *++[o][F-]{70}\\
|
sawine@0
|
35 |
*++[o][F-]{20} & & & & *++[o][F-]{70} & & *++[o][F-]{20} & & & & \\
|
sawine@0
|
36 |
}
|
sawine@0
|
37 |
\end{figure}
|
sawine@0
|
38 |
There are no rotations required because the AVL-balance property is not violated.
|
sawine@0
|
39 |
|
sawine@0
|
40 |
\section*{Exercise 4.2}
|
sawine@0
|
41 |
We use the following Python function for the calculation of the hash code, which resembles the Java code presented in the lecture:
|
sawine@0
|
42 |
\begin{python}
|
sawine@0
|
43 |
def hash(string, m):
|
sawine@0
|
44 |
return sum(map(ord, string)) % m
|
sawine@0
|
45 |
\end{python}
|
sawine@0
|
46 |
We choose $m = 13$ and get following results:\\\\
|
sawine@0
|
47 |
\begin{tabular}{ l c l}
|
sawine@0
|
48 |
\textbf{string} & \textbf{hash} & \textbf{collisions}\\ \hline
|
sawine@0
|
49 |
\emph{Hashing} & 4 & \\
|
sawine@0
|
50 |
\emph{Exercise} & 5 & \\
|
sawine@0
|
51 |
\emph{THEORYI} & 2 & \\
|
sawine@0
|
52 |
\emph{god} & 2 & \emph{THEORYI}\\
|
sawine@0
|
53 |
\emph{science} & 2 & \emph{THEORYI, god}\\
|
sawine@0
|
54 |
\end{tabular}\\\\
|
sawine@0
|
55 |
As you can see there are conflicts between \emph{god, science} and \emph{THEORYI}.
|
sawine@0
|
56 |
|
sawine@0
|
57 |
\section*{Exercise 4.3}
|
sawine@0
|
58 |
Let $U = \{0,...,N-1\}$, where $N = 49$ and $m = 35$. Let $a_i = 42i$ and $b_i = 28i$.\\
|
sawine@0
|
59 |
Let $H = \{h_i(k) = ((a_ik + b_i) \bmod N) \bmod m\}$ for $ i \in \{1,...,N(N-1)\}$ be a class of hash functions. We show that $H$ is \emph{not} universal by contradiction.\\\\
|
sawine@0
|
60 |
We assume $H$ is universal.
|
sawine@0
|
61 |
% \left\{ x \in X \mid x > \frac{1}{2}\right\} \]
|
sawine@0
|
62 |
\[\iff \frac{|\{h \in H \mid h(x) = h(y) \land x \neq y\}|}{|H|} \leq \frac{1}{m}\]
|
sawine@0
|
63 |
First we look at the mapping space of the inner modulo function for all pairs $(q, r)$ with \\$q = (a_ix + b_i) \bmod N$ and $r = (a_iy + b_i) \bmod N$ for all $x,y \in U$ and $x \neq y$.
|
sawine@0
|
64 |
\[q = r \iff (a_ix + b_i) \bmod N = (a_iy + b_i) \bmod N\]
|
sawine@0
|
65 |
\[\iff a_i(x - y) \bmod N = 0\]
|
sawine@0
|
66 |
\[\iff \exists_{c \in \mathbb{N}}: a_i(x - y) = cN\]
|
sawine@0
|
67 |
\[\implies a_i|N \land (x - y)|N\]
|
sawine@0
|
68 |
\[\iff \exists_{l \in \mathbb{N}, 0<l\leq7}: (x - y) = 7l\]
|
sawine@0
|
69 |
It follows that there are collisions for $(x - y) = 7l$ with $c = \frac{a_i \cdot 7l}{N} = \frac{42i \cdot 7l}{49} = 6il$\\
|
sawine@0
|
70 |
To determine the number of inner collisions, we calculate $\sum_{0 < l \leq 7} (48 - 7l)$.
|
sawine@0
|
71 |
\[\sum_{0 < l \leq 7} (48 - 7l) = 7(48 - \sum_{0 < l \leq 7}l) = 140\]
|
sawine@0
|
72 |
We know that the number of total collisions of a hash function is greater or equal to the number of collisions of its inner modulo mapping space.
|
sawine@0
|
73 |
\[ \implies \frac{140}{|H|} = \frac{140}{49 \cdot 48} > \frac{1}{35} \implies Contradiction!\]
|
sawine@0
|
74 |
Even within the mapping space of the inner modulo function we get more collisions than accepted for a universal class of hash functions; it follows that $H$ is \emph{not} universal. \qed
|
sawine@0
|
75 |
\end{document}
|