\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 5 Solution}
\author{Eugen Sawin}
\renewcommand{\familydefault}{\sfdefault}
\include{pythonlisting}

\pagestyle{empty}
\begin{document}
\maketitle

\section*{Exercise 5.1}
The chained-hash function in Python:
\begin{python}
def chained_hash(k, table, size):
    code = k % size
    if code in table:
        table[code].append(k)
    else:
        table[code] = [k]
    return table
\end{python}
For the exercise we will set $size = 15$.\\\\
Resulting hash table:\\\\
\begin{tabular}{r l}
\textbf{index} & \textbf{entries}\\
0 & 15\\
1 & 16\\
2 & \\
3 & \\
4 & 19, 49\\
5 & 5, 65\\
6 & 21\\
7 & \\
8 & 8, 38\\
9 & \\
10 & \\
11 & \\
12 & 12, 27, 42\\
13 & \\
14 & \\
\end{tabular}
\newpage

\section*{Exercise 5.2}
General hash function in Python:
\begin{python}
def h(k, size):
    return k % size

def hash(k, size, table, probe):
    j = 0
    code = h(k, size) % size
    while code in table:
        j += 1
        code = (h(k, size) - probe(j, k, size)) % size
    table[code] = k
    return table
\end{python}
For the exercise we will set $size = 15$.\\
The $probe$ function will be substituted by the explicit probing functions in the following exercises.\\
For the following exercises, empty table entries will be omitted.\\

\subsection*{5.2.1}
Linear probing:
\begin{python}
def linear_probing(j, k, size):
    return j
\end{python}
\begin{tabular}{r l}
\textbf{index} & \textbf{entry}\\
0 & 15\\
1 & 16\\
2 & 65\\
3 & 49\\
4 & 19\\
5 & 5\\
6 & 21\\
7 & 38\\
8 & 8\\
10 & 42\\
11 & 27\\
12 & 12\\
\end{tabular}
\newpage

\subsection*{5.2.2}
Quadratic probing:
\begin{python}
def quadratic_probing(j, k, size):
    return (-1)**j * math.ceil(j/2.0)**2
\end{python}
\begin{tabular}{r l}
\textbf{index} & \textbf{entry}\\
0 & 15\\
1 & 16\\
3 & 49\\
4 & 19\\
5 & 5\\
6 & 21\\
8 & 8\\
9 & 38\\
11 & 42\\
12 & 12\\
13 & 27\\
14 & 65\\
\end{tabular}

\subsection*{5.2.3}
Double hashing:
\begin{python}
def h2(k, size):
    return 1 + (k % (size - 2)) 

def double_hash(j, k, size):
    return j * h2(k, size)
\end{python}
\begin{tabular}{r l}
\textbf{index} & \textbf{entry}\\
0 & 15\\
1 & 16\\
2 & 65\\
3 & 21\\
4 & 19\\
5 & 5\\
6 & 27\\
8 & 8\\
9 & 49\\
10 & 38\\
11 & 42\\
12 & 12\\
\end{tabular}
\end{document}
