bhaskar_feb21
December 14th, 2006, 12:18 PM
Construct an efficient algorithm using hashing to do the following. Given a
natural language text with w words, of which d are distinct, generate a list of distinct words with the number of occurrences of each word in the text. You may assume a constant time function word2num that maps a word of text to a natural number. Prove your algorithm correct and derive its time complexity in terms of w and d.
A hash function maps a key, which is a natural number, to a hash
value, which is some (other) natural number. We have a text of
words, but need numbers instead of words. The purpose of function
word2num is to generate a unique key for each unique text word. So
word2num applied to different text words would produce different
keys, but different keys may hash to the same hash value.
Awaiting your replies...
natural language text with w words, of which d are distinct, generate a list of distinct words with the number of occurrences of each word in the text. You may assume a constant time function word2num that maps a word of text to a natural number. Prove your algorithm correct and derive its time complexity in terms of w and d.
A hash function maps a key, which is a natural number, to a hash
value, which is some (other) natural number. We have a text of
words, but need numbers instead of words. The purpose of function
word2num is to generate a unique key for each unique text word. So
word2num applied to different text words would produce different
keys, but different keys may hash to the same hash value.
Awaiting your replies...