# HG changeset patch
# User Eugen Sawin <sawine@me73.com>
# Date 1308665355 -7200
# Node ID 1796e8ba2c1e1f706d654ed8addfaea8fb02c5fe
# Parent  ebfa1b5c4ac7af2c93781910418d7ad318ef1fa0
Ex5.

diff -r ebfa1b5c4ac7 -r 1796e8ba2c1e ex5.txt
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/ex5.txt	Tue Jun 21 16:09:15 2011 +0200
@@ -0,0 +1,59 @@
+chaining
+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: []
+
+linear probing
+0: 15
+1: 16
+2: 65
+3: 49
+4: 19
+5: 5
+6: 21
+7: 38
+8: 8
+10: 42
+11: 27
+12: 12
+
+quadratic probing
+0: 15
+1: 16
+3: 49
+4: 19
+5: 5
+6: 21
+8: 8
+9: 38
+11: 42
+12: 12
+13: 27
+14: 65
+
+double hashing
+0: 15
+1: 16
+2: 65
+3: 21
+4: 19
+5: 5
+6: 27
+8: 8
+9: 49
+10: 38
+11: 42
+12: 12
+
diff -r ebfa1b5c4ac7 -r 1796e8ba2c1e tex/theory1_ex5.tex
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/tex/theory1_ex5.tex	Tue Jun 21 16:09:15 2011 +0200
@@ -0,0 +1,140 @@
+\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}