Scribd
Upload
14 views2 pages

Hash Table Operations and Complexities

The document presents a problem set involving hash tables, including inserting keys into a hash table with a specific hash function and resolving collisions using linear probing. It also discusses the average case time complexities for successful and unsuccessful searches in a dictionary implemented as a hashtable of hashtables, considering different methods of collision resolution. Additionally, there is a bonus problem that requires computing the average case time complexity of a specific algorithm involving a hashtable.

Uploaded by

cattrespect
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
14 views2 pages

Hash Table Operations and Complexities

The document presents a problem set involving hash tables, including inserting keys into a hash table with a specific hash function and resolving collisions using linear probing. It also discusses the average case time complexities for successful and unsuccessful searches in a dictionary implemented as a hashtable of hashtables, considering different methods of collision resolution. Additionally, there is a bonus problem that requires computing the average case time complexity of a specific algorithm involving a hashtable.

Uploaded by

cattrespect
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Week 3.

Problem set
1. Consider a hash table with 13 slots and the hash function h(k) = (k 2 − k + 11) mod 13. Show
the state of the hash table after inserting the keys (in this order)

6, 28, 19, 15, 20, 33, 12, 17, 10, 13, 3, 39

with collisions resolved by linear probing [CLRS, §11.4].

Index 0 1 2 3 4 5 6 7 8 9 10 11 12
Key

2. Consider a dictionary that maps an integer (e.g. group number) and a short1 string (e.g. student
email) to a number (e.g. grade), and is implemented as a hashtable T of hashtables:

• for an integer k, if T contains k, then T [k] is a hashmap with string keys


• for a string s, if T [k] contains s, then T [k][s] is a floating point number
Compute average case time complexities of successful and unsuccessful search in this hashtable
of hashtables with the different possible combinations of chaining and open addressing, assuming

(a) independent uniform hashing for hashtables with separate chaining [CLRS, §11.2]
(b) independent uniform permutation hashing for hashtables with open addressing [CLRS, §11.4]
(c) for the hashtable T , load factor α and size n
(d) for the hashtables T [k], average load factor β and average size m

Successful search Unsuccessful search


T uses separate chaining and each T [k] uses separate chaining
T uses separate chaining and each T [k] uses open addressing
T uses open addressing and each T [k] uses separate chaining
T uses open addressing and each T [k] uses open addressing

3. (+0.5% extra credit) Compute the average case time complexity of the following algorithm:

1 secret(M, k):
2 Q := new linked queue
3 while [Link](k) and k > 0
4 item := [Link](k)
5 k := min([Link], k) - 1
6 if k == [Link] - 1
7 [Link](item)
8 while not [Link]()
9 [Link]([Link]())
10 return k

M is a hashtable of size n with load factor α that resolves collisions by separate chaining [CLRS,
§11.2]. The answer must use O-notation and may depend on n, k, and α. Assume independent
uniform hashing and worst case for the contents (values) of the input map M .
Justify your answer (3–5 sentences). Detailed proof is not required.
1 Assume that strings have a relatively small constant maximum size.

Data Structures and Algorithms, Spring 2025, Innopolis University


References
[CLRS] Cormen, T.H., Leiserson, C.E., Rivest, R.L. and Stein, C., 2022. Introduction to algo-
rithms, Fourth Edition. MIT press.

You might also like