1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/tex/theory1_ex4.tex	Tue Jun 07 01:09:23 2011 +0200
     1.3 @@ -0,0 +1,75 @@
     1.4 +\documentclass[a4paper, 10pt, pagesize, smallheadings]{article}  
     1.5 +\usepackage{graphicx}
     1.6 +%\usepackage[latin1]{inputenc}
     1.7 +\usepackage{amsmath, amsthm, amssymb}
     1.8 +\usepackage{typearea}
     1.9 +\usepackage{algorithm}
    1.10 +\usepackage{algorithmic}
    1.11 +\usepackage{fullpage}
    1.12 +\usepackage[all]{xy}
    1.13 +\title{Theory I, Sheet 4 Solution}
    1.14 +\author{Eugen Sawin}
    1.15 +\renewcommand{\familydefault}{\sfdefault}
    1.16 +\include{pythonlisting}
    1.17 +
    1.18 +
    1.19 +\pagestyle{empty}
    1.20 +\begin{document}
    1.21 +\maketitle
    1.22 +
    1.23 +\section*{Exercise 4.1}
    1.24 +\begin{figure}[h]
    1.25 +\entrymodifiers={}
    1.26 +\xymatrix
    1.27 +{
    1.28 +& & *++[o][F-]{50} \ar@{-}[dl] \ar@{-}[dr] & & & & & & *++[o][F-]{50} \ar@{-}[dl] \ar@{-}[dr]\\
    1.29 +& *++[o][F-]{30} \ar@{-}[dl] \ar@{-}[dr] & & *++[o][F-]{60} \ar@{-}[dr] & \ar@{=>}[rr]^{delete(40)} & & & *++[o][F-]{30} \ar@{-}[dl] & & *++[o][F-]{60}\ar@{-}[dr]\\
    1.30 +*++[o][F-]{20} & & *++[o][F-]{40} & & *++[o][F-]{70} & & *++[o][F-]{20} & & & & *++[o][F-]{70}\\
    1.31 +}
    1.32 +\end{figure}
    1.33 +\begin{figure}[h]
    1.34 +\xymatrix
    1.35 +{
    1.36 +& & *++[o][F-]{50} \ar@{-}[dl] \ar@{-}[dr] & & & & & & *++[o][F-]{50} \ar@{-}[dl] \ar@{-}[dr]\\
    1.37 +& *++[o][F-]{30} \ar@{-}[dl] & & *++[o][F-]{60} \ar@{-}[dr] & \ar@{=>}[rr]^{delete(60)} & & & *++[o][F-]{30} \ar@{-}[dl] & & *++[o][F-]{70}\\
    1.38 +*++[o][F-]{20} & & & & *++[o][F-]{70} & & *++[o][F-]{20} & & & & \\
    1.39 +}
    1.40 +\end{figure}
    1.41 +There are no rotations required because the AVL-balance property is not violated.
    1.42 +
    1.43 +\section*{Exercise 4.2}
    1.44 +We use the following Python function for the calculation of the hash code, which resembles the Java code presented in the lecture:
    1.45 +\begin{python}
    1.46 +def hash(string, m):
    1.47 +    return sum(map(ord, string)) % m   
    1.48 +\end{python}
    1.49 +We choose $m = 13$ and get following results:\\\\
    1.50 +\begin{tabular}{ l  c  l}
    1.51 +  \textbf{string} & \textbf{hash} & \textbf{collisions}\\ \hline 
    1.52 +  \emph{Hashing} & 4 & \\
    1.53 +  \emph{Exercise} & 5 & \\ 
    1.54 +  \emph{THEORYI} & 2 & \\
    1.55 +  \emph{god} & 2 & \emph{THEORYI}\\
    1.56 +  \emph{science} & 2 & \emph{THEORYI, god}\\
    1.57 +\end{tabular}\\\\
    1.58 +As you can see there are conflicts between \emph{god, science} and \emph{THEORYI}.
    1.59 +
    1.60 +\section*{Exercise 4.3}
    1.61 +Let $U = \{0,...,N-1\}$, where $N = 49$ and $m = 35$. Let $a_i = 42i$ and $b_i = 28i$.\\
    1.62 +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.\\\\
    1.63 +We assume $H$ is universal.
    1.64 +% \left\{ x \in X \mid x > \frac{1}{2}\right\} \]
    1.65 +\[\iff \frac{|\{h \in H \mid h(x) = h(y) \land x \neq y\}|}{|H|} \leq \frac{1}{m}\]
    1.66 +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$.
    1.67 +\[q = r \iff (a_ix + b_i) \bmod N = (a_iy + b_i) \bmod N\]
    1.68 +\[\iff a_i(x - y) \bmod N = 0\]
    1.69 +\[\iff \exists_{c \in \mathbb{N}}: a_i(x - y) = cN\]
    1.70 +\[\implies a_i|N \land (x - y)|N\]
    1.71 +\[\iff \exists_{l \in \mathbb{N}, 0<l\leq7}: (x - y) = 7l\]
    1.72 +It follows that there are collisions for $(x - y) = 7l$ with $c = \frac{a_i \cdot 7l}{N} = \frac{42i \cdot 7l}{49} = 6il$\\
    1.73 +To determine the number of inner collisions, we calculate $\sum_{0 < l \leq 7} (48 - 7l)$.
    1.74 +\[\sum_{0 < l \leq 7} (48 - 7l) = 7(48 - \sum_{0 < l \leq 7}l) = 140\]
    1.75 +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.
    1.76 +\[ \implies \frac{140}{|H|} = \frac{140}{49 \cdot 48} > \frac{1}{35} \implies Contradiction!\]
    1.77 +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
    1.78 +\end{document}