\documentclass[a4paper, 10pt, pagesize, smallheadings]{article}  

 \usepackage{graphicx}

 %\usepackage[latin1]{inputenc}

 \usepackage{amsmath, amsthm, amssymb}

 \usepackage{typearea}

 \usepackage{algorithm}

 \usepackage{algorithmic}

 \usepackage{fullpage}

 \usepackage[all]{xy}

 \title{Theory I, Sheet 4 Solution}

 \author{Eugen Sawin}

 \renewcommand{\familydefault}{\sfdefault}

 \include{pythonlisting}

 \pagestyle{empty}

 \begin{document}

 \maketitle

 \section*{Exercise 4.1}

 \begin{figure}[h]

 \entrymodifiers={}

 \xymatrix

 {

 & & *++[o][F-]{50} \ar@{-}[dl] \ar@{-}[dr] & & & & & & *++[o][F-]{50} \ar@{-}[dl] \ar@{-}[dr]\\

 & *++[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]\\

 *++[o][F-]{20} & & *++[o][F-]{40} & & *++[o][F-]{70} & & *++[o][F-]{20} & & & & *++[o][F-]{70}\\

 }

 \end{figure}

 \begin{figure}[h]

 \xymatrix

 {

 & & *++[o][F-]{50} \ar@{-}[dl] \ar@{-}[dr] & & & & & & *++[o][F-]{50} \ar@{-}[dl] \ar@{-}[dr]\\

 & *++[o][F-]{30} \ar@{-}[dl] & & *++[o][F-]{60} \ar@{-}[dr] & \ar@{=>}[rr]^{delete(60)}_{upout(50)} & & & *++[o][F-]{30} \ar@{-}[dl] & & *++[o][F-]{70}\\

 *++[o][F-]{20} & & & & *++[o][F-]{70} & & *++[o][F-]{20} & & & & \\

 }

 \end{figure}

 There are no rotations required because the AVL-balance property is not violated.

 \section*{Exercise 4.2}

 We use the following Python function for the calculation of the hash code, which resembles the Java code presented in the lecture:

 \begin{python}

 def hash(string, m):

     return sum(map(ord, string)) % m   

 \end{python}

 We choose $m = 13$ and get following results:\\\\

 \begin{tabular}{ l  c  l}

   \textbf{string} & \textbf{hash} & \textbf{collisions}\\ \hline 

   \emph{Hashing} & 4 & \\

   \emph{Exercise} & 5 & \\ 

   \emph{THEORYI} & 2 & \\

   \emph{god} & 2 & \emph{THEORYI}\\

   \emph{science} & 2 & \emph{THEORYI, god}\\

 \end{tabular}\\\\

 As you can see there are conflicts between \emph{god, science} and \emph{THEORYI}.

 \section*{Exercise 4.3}

 Let $U = \{0,...,N-1\}$, where $N = 49$ and $m = 35$. Let $a_i = 42i$ and $b_i = 28i$.\\

 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.\\\\

 We assume $H$ is universal.

 % \left\{ x \in X \mid x > \frac{1}{2}\right\} \]

 \[\iff \frac{|\{h \in H \mid h(x) = h(y) \land x \neq y\}|}{|H|} \leq \frac{1}{m}\]

 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$.

 \[q = r \iff (a_ix + b_i) \bmod N = (a_iy + b_i) \bmod N\]

 \[\iff a_i(x - y) \bmod N = 0\]

 \[\iff \exists_{c \in \mathbb{N}}: a_i(x - y) = cN\]

 \[\implies a_i|N \land (x - y)|N\]

 \[\iff \exists_{l \in \mathbb{N}, 0<l\leq7}: (x - y) = 7l\]

 It follows that there are collisions for $(x - y) = 7l$ with $c = \frac{a_i \cdot 7l}{N} = \frac{42i \cdot 7l}{49} = 6il$\\

 To determine the number of inner collisions, we calculate $\sum_{0 < l \leq 7} (48 - 7l)$.

 \[\sum_{0 < l \leq 7} (48 - 7l) = 7(48 - \sum_{0 < l \leq 7}l) = 140\]

 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.

 \[ \implies \frac{140}{|H|} = \frac{140}{49 \cdot 48} > \frac{1}{35} \implies Contradiction!\]

 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

 \end{document}