sawine@6: \documentclass[a4paper, 10pt, pagesize, smallheadings]{article}  
sawine@6: \usepackage{graphicx}
sawine@6: %\usepackage[latin1]{inputenc}
sawine@6: \usepackage{amsmath, amsthm, amssymb}
sawine@6: \usepackage{typearea}
sawine@6: \usepackage{algorithm}
sawine@6: \usepackage{algorithmic}
sawine@6: \usepackage{fullpage}
sawine@6: \usepackage[all]{xy}
sawine@6: \title{Theory I, Sheet 5 Solution}
sawine@6: \author{Eugen Sawin}
sawine@6: \renewcommand{\familydefault}{\sfdefault}
sawine@6: \include{pythonlisting}
sawine@6: 
sawine@6: \pagestyle{empty}
sawine@6: \begin{document}
sawine@6: \maketitle
sawine@6: 
sawine@6: \section*{Exercise 5.1}
sawine@6: The chained-hash function in Python:
sawine@6: \begin{python}
sawine@6: def chained_hash(k, table, size):
sawine@6:     code = k % size
sawine@6:     if code in table:
sawine@6:         table[code].append(k)
sawine@6:     else:
sawine@6:         table[code] = [k]
sawine@6:     return table
sawine@6: \end{python}
sawine@6: For the exercise we will set $size = 15$.\\\\
sawine@6: Resulting hash table:\\\\
sawine@6: \begin{tabular}{r l}
sawine@6: \textbf{index} & \textbf{entries}\\
sawine@6: 0 & 15\\
sawine@6: 1 & 16\\
sawine@6: 2 & \\
sawine@6: 3 & \\
sawine@6: 4 & 19, 49\\
sawine@6: 5 & 5, 65\\
sawine@6: 6 & 21\\
sawine@6: 7 & \\
sawine@6: 8 & 8, 38\\
sawine@6: 9 & \\
sawine@6: 10 & \\
sawine@6: 11 & \\
sawine@6: 12 & 12, 27, 42\\
sawine@6: 13 & \\
sawine@6: 14 & \\
sawine@6: \end{tabular}
sawine@6: \newpage
sawine@6: 
sawine@6: \section*{Exercise 5.2}
sawine@6: General hash function in Python:
sawine@6: \begin{python}
sawine@6: def h(k, size):
sawine@6:     return k % size
sawine@6: 
sawine@6: def hash(k, size, table, probe):
sawine@6:     j = 0
sawine@6:     code = h(k, size) % size
sawine@6:     while code in table:
sawine@6:         j += 1
sawine@6:         code = (h(k, size) - probe(j, k, size)) % size
sawine@6:     table[code] = k
sawine@6:     return table
sawine@6: \end{python}
sawine@6: For the exercise we will set $size = 15$.\\
sawine@6: The $probe$ function will be substituted by the explicit probing functions in the following exercises.\\
sawine@6: For the following exercises, empty table entries will be omitted.\\
sawine@6: 
sawine@6: \subsection*{5.2.1}
sawine@6: Linear probing:
sawine@6: \begin{python}
sawine@6: def linear_probing(j, k, size):
sawine@6:     return j
sawine@6: \end{python}
sawine@6: \begin{tabular}{r l}
sawine@6: \textbf{index} & \textbf{entry}\\
sawine@6: 0 & 15\\
sawine@6: 1 & 16\\
sawine@6: 2 & 65\\
sawine@6: 3 & 49\\
sawine@6: 4 & 19\\
sawine@6: 5 & 5\\
sawine@6: 6 & 21\\
sawine@6: 7 & 38\\
sawine@6: 8 & 8\\
sawine@6: 10 & 42\\
sawine@6: 11 & 27\\
sawine@6: 12 & 12\\
sawine@6: \end{tabular}
sawine@6: \newpage
sawine@6: 
sawine@6: \subsection*{5.2.2}
sawine@6: Quadratic probing:
sawine@6: \begin{python}
sawine@6: def quadratic_probing(j, k, size):
sawine@6:     return (-1)**j * math.ceil(j/2.0)**2
sawine@6: \end{python}
sawine@6: \begin{tabular}{r l}
sawine@6: \textbf{index} & \textbf{entry}\\
sawine@6: 0 & 15\\
sawine@6: 1 & 16\\
sawine@6: 3 & 49\\
sawine@6: 4 & 19\\
sawine@6: 5 & 5\\
sawine@6: 6 & 21\\
sawine@6: 8 & 8\\
sawine@6: 9 & 38\\
sawine@6: 11 & 42\\
sawine@6: 12 & 12\\
sawine@6: 13 & 27\\
sawine@6: 14 & 65\\
sawine@6: \end{tabular}
sawine@6: 
sawine@6: \subsection*{5.2.3}
sawine@6: Double hashing:
sawine@6: \begin{python}
sawine@6: def h2(k, size):
sawine@6:     return 1 + (k % (size - 2)) 
sawine@6: 
sawine@6: def double_hash(j, k, size):
sawine@6:     return j * h2(k, size)
sawine@6: \end{python}
sawine@6: \begin{tabular}{r l}
sawine@6: \textbf{index} & \textbf{entry}\\
sawine@6: 0 & 15\\
sawine@6: 1 & 16\\
sawine@6: 2 & 65\\
sawine@6: 3 & 21\\
sawine@6: 4 & 19\\
sawine@6: 5 & 5\\
sawine@6: 6 & 27\\
sawine@6: 8 & 8\\
sawine@6: 9 & 49\\
sawine@6: 10 & 38\\
sawine@6: 11 & 42\\
sawine@6: 12 & 12\\
sawine@6: \end{tabular}
sawine@6: \end{document}