Exercises A¶
Note
You must complete these exercises by Wednesday of W7.
Exercise 4.1.1¶
Name at least four different implementations of a dictionary (table of symbols). Specify, in each case, what are the main properties of these implementations. In which case(s) are they interesting? What are the computational complexities of their main methods?
Exercise 4.1.2¶
Recall the following question proposed in the assignment on sorting: Given a set \(S\) of size \(n\), and a number \(x\). Describe an efficient algorithm using a HashTable to find if there exists a pair \((a,b)\) with \(a \in S,b \in S\) such that \(a+b=x\). What is the complexity of your algorithm? Is it better than your solution which used a sort?
Exercise 4.1.3¶
Show that \((a + b) \% M\) is equivalent to \(((a \% M) + b) \% M\). How can this property be useful to build a hash function on Strings. Explain how Java computes a hash function on Strings? What is the complexity of computing 1 time and \(N\) times the hashcode of a String.
Exercise 4.1.4¶
Explain why the hash() method p461 in the book returns (x.hashCode() & 0x7FFFFFFF) % M and not just x.hashCode() % M?
What number represents 0x7FFFFFFF ?
What is its binary representation ?
Show the binary impact 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.
Can you determine exactly which variant of hash table this is?
Does Java provide other implementations of the Map interface?
Make a diagram that represents the interfaces and classes that relate to Map and specify what, in each case, characterizes them.
What can be used as a key for a hashtable in Java? Be specific.
Exercise 4.1.6¶
What is meant by the notion of « collision » in a hash table? Do collisions have an influence on the complexity of operations? If yes, which operation(s) with which complexity(ies), otherwise specify why.
Exercise 4.1.7¶
What is the load factor of a hash table.
Is the load factor control necessary/optional for the proper functioning of a hash table with Linear Probing or Separate Chaining?
What is the strategy used by java.util.Hashtable to control the load factor?
How is it different from the one proposed in LinearProbinHashST?
What is the link between load factor and collision?
Exercise 4.1.8¶
Imagine a new iterator() method that returns an iterator over the keys of LinearProbingHashST.
Your iterator should not accept a modification of the hash table while it is in use: a ConcurrentModificationException() should be thrown if it does.
What do you suggest to do 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 that uses the linear probing technique to handle collisions that would use a special marker to represent entries deleted using the delete(key) method.
In other words the delete(key) method instead of rearranging the contents of the hash table so that it is as if the deleted entry had never been inserted, will simply mark the entry with the special marker.
What is the advantage or disadvantage of this approach over the « LinearProbingHashST » approach in the book?
Exercise 4.1.10 (Rabin-Karp)¶
Imagine a hash function for a string \(s\) such that knowing its value for the sub-string \(s[i,...,i+n-1]\) would allow to compute the hash function of the string \(s[i+1,...,i+n]\) in constant time (incrementally).
Exercise 4.1.11 (Rabin-Karp)¶
Explain how to search for a sub-string of size \(m\) in a long string of size \(n\) in \(\mathcal{O}(n)\) using an incremental hash function. How would you do it if you have \(k\) strings of size \(m\) to search in the long string of size \(n\)? What would be the 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 to implement a tool for counting word occurences (exam 2022). Word counting is a frequent task in natural language processing algorithm. Word Counter
Exercise 4.1.15 (Inginious)¶
Incremental computation of a hash function (exam 2018). Incremental Hash
Exercise 4.1.16 (Inginious)¶
Very interesting hash-map with a bounded memory keeping only the most recently used ones (exam 2022). LRUCache
Exercise 4.1.17 (Inginious)¶
Implement a version of RabinKarp but for looking for K patterns instead of just one.
