# 3b) [4 pts]+ As in the Little SearchEngine assignment, consider a hash table that stores frequencies...

###### 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.

#### Similar Solved Questions

##### The question asking what kind of actions or programs we can implement to make sure the...
The question asking what kind of actions or programs we can implement to make sure the orgnization can get the maximum benefits of the patentable ideas. Thanks 2. As an R&D manager, what actions might you take or programs might you implement to assure your organization got maximum benefit fro...
##### PLEASE USE FOUR FORCES IN TERMS OF F (FRICTION) N(NORMAL REACTION) T(TENSION IN THE ROPE) AND W(W...
PLEASE USE FOUR FORCES IN TERMS OF F (FRICTION) N(NORMAL REACTION) T(TENSION IN THE ROPE) AND W(WEIGHT) Question 6 20 marks You should be able to answer this question after studying Unit 5 A mountain rescue team is preparing to move a stretcher (with an injured climber) down a flat slope. The combin...
##### Problem 2: Consider the circuit shown in Figure 2. VCC-15V, R1-100 K2, R2-47 K2, RE-3.9K, Draw the small signal model Compute rel and re2. Rin1 and Rin2 as (shown in the circuit) . Find the overall g...
Problem 2: Consider the circuit shown in Figure 2. VCC-15V, R1-100 K2, R2-47 K2, RE-3.9K, Draw the small signal model Compute rel and re2. Rin1 and Rin2 as (shown in the circuit) . Find the overall gain. Using OCTC approach compute the high frequency time constants, given Cr-Cμ-1 pF. Stage 2 Load...
##### 1. Draw a free body diagram for the two situations below:
1. Draw a free body diagram for the two situations below:...
##### Need help with python and raptor codes:
Design a program that calculates and displays the number of miles per hour over the speed limit that a speeding driver was doing. The program should ask for the speedlimit and the driver's speed. Validate the input as follows:-The speed limit should be at lease 20, but not greater than 70.-The d...
##### When writing open contrary you Wed filled sublevels end is then. sequoia. you can Lester editor...
When writing open contrary you Wed filled sublevels end is then. sequoia. you can Lester editor tq t0 to- to toe P-tote and the the lest which be lied, to each to drag the items to their appropriate bins....
##### QUESTION 40 A larpe curved Dam is created by rotating the triangle shape BCD through an...
QUESTION 40 A larpe curved Dam is created by rotating the triangle shape BCD through an angle of 60"radions) about vertical axis -9. The drawing is not to scale. -1035ft- 100ft dB 35 1 000ft Determine the Surface Area of the Dam's downstream face (created by the revolution of line DB). 105 (...
##### Why does a solution of a weak base and its conjugate acid act as a better...
Why does a solution of a weak base and its conjugate acid act as a better buffer than does a solution of the weak base alone...
##### Please label parts of questions CLEARLY as well as answering all parts in full. (40 Marks) Problem 3 Desert air at 38°...
Please label parts of questions CLEARLY as well as answering all parts in full. (40 Marks) Problem 3 Desert air at 38°C, bar, and 26% relative humidity is passed through an evaporative cooler. Water is added at 36°C, and the final air temperature exiting the cooler is 24°C. Determine: a...
##### A customer service representative must spend different amounts of time with each customer to resolve various...
A customer service representative must spend different amounts of time with each customer to resolve various concerns. The amount of time spent with each customer can be modeled by the following distribution: X ~ Exp(0.7) Find μ. Round to nearest tenths. a. 4.2 b.2 c.1.4 d. 2.1...