1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/ex5.txt	Tue Jun 21 16:09:15 2011 +0200
     1.3 @@ -0,0 +1,59 @@
     1.4 +chaining
     1.5 +0: [15]
     1.6 +1: [16]
     1.7 +2: []
     1.8 +3: []
     1.9 +4: [19, 49]
    1.10 +5: [5, 65]
    1.11 +6: [21]
    1.12 +7: []
    1.13 +8: [8, 38]
    1.14 +9: []
    1.15 +10: []
    1.16 +11: []
    1.17 +12: [12, 27, 42]
    1.18 +13: []
    1.19 +14: []
    1.20 +
    1.21 +linear probing
    1.22 +0: 15
    1.23 +1: 16
    1.24 +2: 65
    1.25 +3: 49
    1.26 +4: 19
    1.27 +5: 5
    1.28 +6: 21
    1.29 +7: 38
    1.30 +8: 8
    1.31 +10: 42
    1.32 +11: 27
    1.33 +12: 12
    1.34 +
    1.35 +quadratic probing
    1.36 +0: 15
    1.37 +1: 16
    1.38 +3: 49
    1.39 +4: 19
    1.40 +5: 5
    1.41 +6: 21
    1.42 +8: 8
    1.43 +9: 38
    1.44 +11: 42
    1.45 +12: 12
    1.46 +13: 27
    1.47 +14: 65
    1.48 +
    1.49 +double hashing
    1.50 +0: 15
    1.51 +1: 16
    1.52 +2: 65
    1.53 +3: 21
    1.54 +4: 19
    1.55 +5: 5
    1.56 +6: 27
    1.57 +8: 8
    1.58 +9: 49
    1.59 +10: 38
    1.60 +11: 42
    1.61 +12: 12
    1.62 +

     2.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     2.2 +++ b/tex/theory1_ex5.tex	Tue Jun 21 16:09:15 2011 +0200
     2.3 @@ -0,0 +1,140 @@
     2.4 +\documentclass[a4paper, 10pt, pagesize, smallheadings]{article}  
     2.5 +\usepackage{graphicx}
     2.6 +%\usepackage[latin1]{inputenc}
     2.7 +\usepackage{amsmath, amsthm, amssymb}
     2.8 +\usepackage{typearea}
     2.9 +\usepackage{algorithm}
    2.10 +\usepackage{algorithmic}
    2.11 +\usepackage{fullpage}
    2.12 +\usepackage[all]{xy}
    2.13 +\title{Theory I, Sheet 5 Solution}
    2.14 +\author{Eugen Sawin}
    2.15 +\renewcommand{\familydefault}{\sfdefault}
    2.16 +\include{pythonlisting}
    2.17 +
    2.18 +\pagestyle{empty}
    2.19 +\begin{document}
    2.20 +\maketitle
    2.21 +
    2.22 +\section*{Exercise 5.1}
    2.23 +The chained-hash function in Python:
    2.24 +\begin{python}
    2.25 +def chained_hash(k, table, size):
    2.26 +    code = k % size
    2.27 +    if code in table:
    2.28 +        table[code].append(k)
    2.29 +    else:
    2.30 +        table[code] = [k]
    2.31 +    return table
    2.32 +\end{python}
    2.33 +For the exercise we will set $size = 15$.\\\\
    2.34 +Resulting hash table:\\\\
    2.35 +\begin{tabular}{r l}
    2.36 +\textbf{index} & \textbf{entries}\\
    2.37 +0 & 15\\
    2.38 +1 & 16\\
    2.39 +2 & \\
    2.40 +3 & \\
    2.41 +4 & 19, 49\\
    2.42 +5 & 5, 65\\
    2.43 +6 & 21\\
    2.44 +7 & \\
    2.45 +8 & 8, 38\\
    2.46 +9 & \\
    2.47 +10 & \\
    2.48 +11 & \\
    2.49 +12 & 12, 27, 42\\
    2.50 +13 & \\
    2.51 +14 & \\
    2.52 +\end{tabular}
    2.53 +\newpage
    2.54 +
    2.55 +\section*{Exercise 5.2}
    2.56 +General hash function in Python:
    2.57 +\begin{python}
    2.58 +def h(k, size):
    2.59 +    return k % size
    2.60 +
    2.61 +def hash(k, size, table, probe):
    2.62 +    j = 0
    2.63 +    code = h(k, size) % size
    2.64 +    while code in table:
    2.65 +        j += 1
    2.66 +        code = (h(k, size) - probe(j, k, size)) % size
    2.67 +    table[code] = k
    2.68 +    return table
    2.69 +\end{python}
    2.70 +For the exercise we will set $size = 15$.\\
    2.71 +The $probe$ function will be substituted by the explicit probing functions in the following exercises.\\
    2.72 +For the following exercises, empty table entries will be omitted.\\
    2.73 +
    2.74 +\subsection*{5.2.1}
    2.75 +Linear probing:
    2.76 +\begin{python}
    2.77 +def linear_probing(j, k, size):
    2.78 +    return j
    2.79 +\end{python}
    2.80 +\begin{tabular}{r l}
    2.81 +\textbf{index} & \textbf{entry}\\
    2.82 +0 & 15\\
    2.83 +1 & 16\\
    2.84 +2 & 65\\
    2.85 +3 & 49\\
    2.86 +4 & 19\\
    2.87 +5 & 5\\
    2.88 +6 & 21\\
    2.89 +7 & 38\\
    2.90 +8 & 8\\
    2.91 +10 & 42\\
    2.92 +11 & 27\\
    2.93 +12 & 12\\
    2.94 +\end{tabular}
    2.95 +\newpage
    2.96 +
    2.97 +\subsection*{5.2.2}
    2.98 +Quadratic probing:
    2.99 +\begin{python}
   2.100 +def quadratic_probing(j, k, size):
   2.101 +    return (-1)**j * math.ceil(j/2.0)**2
   2.102 +\end{python}
   2.103 +\begin{tabular}{r l}
   2.104 +\textbf{index} & \textbf{entry}\\
   2.105 +0 & 15\\
   2.106 +1 & 16\\
   2.107 +3 & 49\\
   2.108 +4 & 19\\
   2.109 +5 & 5\\
   2.110 +6 & 21\\
   2.111 +8 & 8\\
   2.112 +9 & 38\\
   2.113 +11 & 42\\
   2.114 +12 & 12\\
   2.115 +13 & 27\\
   2.116 +14 & 65\\
   2.117 +\end{tabular}
   2.118 +
   2.119 +\subsection*{5.2.3}
   2.120 +Double hashing:
   2.121 +\begin{python}
   2.122 +def h2(k, size):
   2.123 +    return 1 + (k % (size - 2)) 
   2.124 +
   2.125 +def double_hash(j, k, size):
   2.126 +    return j * h2(k, size)
   2.127 +\end{python}
   2.128 +\begin{tabular}{r l}
   2.129 +\textbf{index} & \textbf{entry}\\
   2.130 +0 & 15\\
   2.131 +1 & 16\\
   2.132 +2 & 65\\
   2.133 +3 & 21\\
   2.134 +4 & 19\\
   2.135 +5 & 5\\
   2.136 +6 & 27\\
   2.137 +8 & 8\\
   2.138 +9 & 49\\
   2.139 +10 & 38\\
   2.140 +11 & 42\\
   2.141 +12 & 12\\
   2.142 +\end{tabular}
   2.143 +\end{document}