If memory is limited and the entire dictionary cannot be stored in a hash table,

Question

If memory is limited and the entire dictionary cannot be stored in a hash table, we can still get an efficient algorithm that almost always works. We declare a table of boolean (initialized to false) from 0 to Tablesize - 1. As we read in a word, we set table[hash(word)] = true. Which of the following is true?

(a) If a word hashes to a location with value that is false, the word is not in the dictionary.

(b) If a word hashes to a location with value that is true, the word is in the dictionary.

(c) Suppose we choose Tablesize = 200,007 How much memory does this require? Assume that each boolean element takes up 1 bit of memory.

(d) What is the probability that this scheme will not report a misspelled word?

Explanation / Answer

This is based on some assumptions , the answer may be not accurate.

Now, as we read, the value for that word is set to true. i.e unless we dont read ,it will remain false because it is the default value in the table.

now coming to option a and b,

if the word hashes to location with false, the word is not in dictonary, i think this should be not true, because the value is false as it is not read till now.

so, if the word hashed location is true, means it is read, so it should be present in dictonary. So we can say B is true.

200,007 bytes = 1600056 bits

So 1600056 boolean values can be stored into this table.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.