| author | Eugen Sawin <sawine@me73.com> |
| Mon, 27 Jun 2011 01:01:33 +0200 | |
| changeset 8 | 862ab5c7c6df |
| permissions | -rw-r--r-- |
1 \documentclass[a4paper, 10pt, pagesize, smallheadings]{article}
2 \usepackage{graphicx}
3 %\usepackage[latin1]{inputenc}
4 \usepackage{amsmath, amsthm, amssymb}
5 \usepackage{typearea}
6 \usepackage{algorithm}
7 \usepackage{algorithmic}
8 \usepackage{fullpage}
9 \usepackage[all]{xy}
10 \title{Theory I, Sheet 5 Solution}
11 \author{Eugen Sawin}
12 \renewcommand{\familydefault}{\sfdefault}
13 \include{pythonlisting}
15 \pagestyle{empty}
16 \begin{document}
17 \maketitle
19 \section*{Exercise 5.1}
20 The chained-hash function in Python:
21 \begin{python}
22 def chained_hash(k, table, size):
23 code = k % size
24 if code in table:
25 table[code].append(k)
26 else:
27 table[code] = [k]
28 return table
29 \end{python}
30 For the exercise we will set $size = 15$.\\\\
31 Resulting hash table:\\\\
32 \begin{tabular}{r l}
33 \textbf{index} & \textbf{entries}\\
34 0 & 15\\
35 1 & 16\\
36 2 & \\
37 3 & \\
38 4 & 19, 49\\
39 5 & 5, 65\\
40 6 & 21\\
41 7 & \\
42 8 & 8, 38\\
43 9 & \\
44 10 & \\
45 11 & \\
46 12 & 12, 27, 42\\
47 13 & \\
48 14 & \\
49 \end{tabular}
50 \newpage
52 \section*{Exercise 5.2}
53 General hash function in Python:
54 \begin{python}
55 def h(k, size):
56 return k % size
58 def hash(k, size, table, probe):
59 j = 0
60 code = h(k, size) % size
61 while code in table:
62 j += 1
63 code = (h(k, size) - probe(j, k, size)) % size
64 table[code] = k
65 return table
66 \end{python}
67 For the exercise we will set $size = 15$.\\
68 The $probe$ function will be substituted by the explicit probing functions in the following exercises.\\
69 For the following exercises, empty table entries will be omitted.\\
71 \subsection*{5.2.1}
72 Linear probing:
73 \begin{python}
74 def linear_probing(j, k, size):
75 return j
76 \end{python}
77 \begin{tabular}{r l}
78 \textbf{index} & \textbf{entry}\\
79 0 & 15\\
80 1 & 16\\
81 2 & 65\\
82 3 & 49\\
83 4 & 19\\
84 5 & 5\\
85 6 & 21\\
86 7 & 38\\
87 8 & 8\\
88 10 & 42\\
89 11 & 27\\
90 12 & 12\\
91 \end{tabular}
92 \newpage
94 \subsection*{5.2.2}
95 Quadratic probing:
96 \begin{python}
97 def quadratic_probing(j, k, size):
98 return (-1)**j * math.ceil(j/2.0)**2
99 \end{python}
100 \begin{tabular}{r l}
101 \textbf{index} & \textbf{entry}\\
102 0 & 15\\
103 1 & 16\\
104 3 & 49\\
105 4 & 19\\
106 5 & 5\\
107 6 & 21\\
108 8 & 8\\
109 9 & 38\\
110 11 & 42\\
111 12 & 12\\
112 13 & 27\\
113 14 & 65\\
114 \end{tabular}
116 \subsection*{5.2.3}
117 Double hashing:
118 \begin{python}
119 def h2(k, size):
120 return 1 + (k % (size - 2))
122 def double_hash(j, k, size):
123 return j * h2(k, size)
124 \end{python}
125 \begin{tabular}{r l}
126 \textbf{index} & \textbf{entry}\\
127 0 & 15\\
128 1 & 16\\
129 2 & 65\\
130 3 & 21\\
131 4 & 19\\
132 5 & 5\\
133 6 & 27\\
134 8 & 8\\
135 9 & 49\\
136 10 & 38\\
137 11 & 42\\
138 12 & 12\\
139 \end{tabular}
140 \end{document}