Exercises A#
Note
You must complete these exercises by Wednesday of W7.
Exercise 4.1.1#
Name at least four different implementations of a symbol table (dictionary). Specify the main properties of each implementation. In which scenario(s) are they most appropriate? What are the time complexities of their main operations?
Exercise 4.1.2#
Recall the following question from the sorting assignment: Given a set \(S\) of size \(n\) and a number \(x\), describe an efficient algorithm using a hash table to determine whether there exists a pair \((a, b)\) with \(a \in S, b \in S\) such that \(a + b = x\). What is the time complexity of your algorithm? Is it better than your solution that used sorting?
Exercise 4.1.3#
Show that \((a + b) \% M\) is equivalent to \(((a \% M) + b) \% M\). How can this property be useful when building a hash function for strings? Explain how Java computes a hash function for strings. What is the time complexity of computing the hash code of a string once, and computing it \(N\) times?
Exercise 4.1.4#
Explain why the hash() method on page 461 of the book returns (x.hashCode() & 0x7FFFFFFF) % M and not simply x.hashCode() % M?
What number does 0x7FFFFFFF represent?
What is its binary representation?
Show the effect at the bit level on an example where x.hashCode() returns a negative number. Hint: use Integer.toBinaryString(int) to verify your answer.
Exercise 4.1.5#
Java provides the class java.util.Hashtable as an implementation of the java.util.Map interface.
Which variant of hash table does it use?
Does Java provide other implementations of the Map interface?
Draw a diagram representing the interfaces and classes related to Map and specify the key characteristics of each.
What can be used as a key for a hash table in Java? Be specific.
Exercise 4.1.6#
What is meant by a « collision » in a hash table? Do collisions affect the time complexity of operations? If so, which operation(s) and with what complexity? If not, explain why.
Exercise 4.1.7#
What is the load factor of a hash table?
Is controlling the load factor necessary or optional for the proper operation of a hash table using linear probing or separate chaining?
What strategy is used by java.util.Hashtable to control the load factor?
How does it differ from the strategy used in LinearProbingHashST?
What is the relationship between the load factor and collisions?
Exercise 4.1.8#
Imagine a new iterator() method that returns an iterator over the keys of LinearProbingHashST.
Your iterator must not allow modifications to the hash table while in use: a ConcurrentModificationException should be thrown if a modification occurs.
How would you implement this? Hint: Take inspiration from the java.util.Hashtable strategy.
Exercise 4.1.9#
Describe the implementation of the put(key) method in a hash table using linear probing where deleted entries are marked with a special sentinel value (tombstone) via the delete(key) method.
In other words, instead of rehashing and shifting subsequent entries so that it is as if the deleted entry was never inserted, delete(key) simply flags the entry with this special marker.
What are the advantages and disadvantages of this approach compared to the LinearProbingHashST implementation in the book?
Exercise 4.1.10 (Rabin-Karp)#
Imagine a hash function for a string \(s\) such that knowing its value for the substring \(s[i \ldots i+n-1]\) allows computing the hash value of the substring \(s[i+1 \ldots i+n]\) in constant time (incrementally).
Exercise 4.1.11 (Rabin-Karp)#
Explain how to search for a substring of length \(m\) in a text of length \(n\) in \(\mathcal{O}(n)\) time using an incremental hash function. How would you do this if you had \(k\) patterns of length \(m\) to search for in a text of length \(n\)? What is the time complexity of your method? Is it better than running the Rabin-Karp algorithm \(k\) times?
Exercise 4.1.12 (INGInious: MCQ)#
Exercise 4.1.13 (INGInious: MCQ)#
Exercise 4.1.14 (INGInious)#
An easy tool to implement for counting word occurrences (exam 2022). Word counting is a frequent task in natural language processing algorithms. Word Counter
Exercise 4.1.15 (INGInious)#
Incremental computation of a hash function (exam 2018). Incremental Hash
Exercise 4.1.16 (INGInious)#
A bounded-capacity cache that retains only the most recently used entries (exam 2022). LRUCache
Exercise 4.1.17 (INGInious)#
Implement a version of Rabin-Karp to search for K patterns simultaneously instead of just one.