Question

3b) [4 pts]+ As in the Little SearchEngine assignment, consider a hash table that stores frequencies (number of occurrences) of words in a set of documents. Words are the keys, and for each word, the associated value is an array list of (document name, frequency) pairs, in descending order of frequencies. Now suppose you are given a list of 50 words. You are asked to find all documents in the hash table in which one or more of these words each occurs with a frequency of f or more (f is an integer parameter). The final result should be a list of documents without duplicates. (In other words, if word1 occurs with a frequency >= f in doc1, and word2 also occurs with a frequency >= f in doc1, then doc1 should only be reported once in the final result.) This non-duplication can be achieved by storing the resulting document names in a hash set. Describe an algorithm for how you would do this (no Java code, write steps in plain English). Your algorithm should not look at more documents in the hash table than is absolutely necessary to find those with frequencies >= f for the given words." 3c) [4 pts] This part pertains to the algorithm you came up with in Q3b above. Assuming that a total of n document names appear in the hash table, and there are k document matches (duplicates included, of which u are unique) over all the 50 words combined, derive the big O running time of your algorithm. For each big O component of the running time, specify whether it is worst case or expected case. You don't have to add up the components to a single big 0. Show your work - just big O answers without derivation will get no credit. Also, your big O derivation will not get credit if your algorithm in 3b) is incorrect.

Answer 1

Ans for Qn 3b):

Let, the set of words we have W = (w1,w2,.....,w50) for which we have to find the document names.

We have the hash table that stores the frequencies of each individual word in a set of documents, where each entry in the hash table contains the pair of (word frequency, document name) pair.

We have to find the document list for all the words given in the set.

Step 1: Take an empty hash set(set size = number of documents) where the key is the document name.

Step 2: For each word in the given word set (50 words), steps 3 to 5 will be executed.

Step 3: Search for that particular word in the given hash table.

Step 4: If the occurance of that word >=f, then remember all the corresponding document name(s) present in the array list associated with that word in the given hash table. (Suppose if any word is present in two documents but it is present for >=f times only in one document, then consider that document only from the list.)

Step 5: Try to insert all the document name(s) in the new hash set. If the particular position is not empty (i.e. if that specific document name is already present in the hash set, then that entry is full and the document name can't be inserted twice), then skip the document name, otherwise enter the name into the hash set accordingly.

Step 6: Iteration for the 50 words ends here.

Step 7: The required result will be stored in the newly created hash set.

Step :