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