Question 2. (6 points) We will use data structure type 1 consisting of hash table with 11 positions (indexes 0..10), with separate overflow based on linked lists, with insertion done at the tail of the linked lis. The hash function for a string S combines the hash code h1(S)F(SHA1(S) mod 256) and the compression map h2(X)-X mod 11. Therefore h(S)- h2(hi(S)) Example h("SAM")=(SHA1 ("SAM") mod 256) (04CD61 121 16E058F5A31 DEFEF2BC1 3DA3BDCB82)16 mod 256-(82)16-130 h(SAM")-h2(h1("SAM")) h2(130)-130 mod 11 9 You will use the hash table described above to simulate an algorithm that counts the frequency of words in a text in the following way. The hash table contains a pair (word, current frequency). For each word found on the text, you search for it in the table: if found increment its frequency, if not found, insert it. For example, the first time the word "SAM" is found in the text, the pair ("SAM",1) is inserted at the hash table at position 9. Every time "SAM" is found again, its frequency is incremented, so that at the end of the algorithm processing below the hash table will contain ("SAM",3) Use the text below for your simulation AM SAM. I AM SAM. SAM I AM THAT SAM-I-AM! THAT SAM-I-AM! I DO NOT LIKE THAT SAM-I-AM! Note: Ignore punctuation symbols but consider SAM-1-AM as a single word a) (1pt) Show the hash function for each word SHA1(word) CA73AB65568CD125C2D27A22BBD9E863C10B675D 80D305C58F97EDFAE92A3627F5A66D9BEF4D8D46 64CD61B12116E058F5A31DEFEF2BC 13DA3BDCB82 61A26854EE49839BBB7509F03BCB590FBC565738 word hi(word) h(word) AM SAM THAT SAM-I-AM 7439ABEAA4401A6A7B8B7C6B4A83CB2445E398EC DO NOT LIKE 8FEB29077A1DF95BD8E261F267CF55119B1EAC74 969E7D8DEE132181523A501A068FEC75BDED3005 5DDF6F04739D8BC3A11B487863B27A7BCAA6FC24 b) (1pt) Show the hash table after the first line is processed c) (2 pt) Show the hash table at the end of the word processing Question 2. (6 points) We will use data structure type 1 consisting of hash table with 11 positions (indexes 0..10), with separate overflow based on linked lists, with insertion done at the tail of the linked lis. The hash function for a string S combines the hash code h1(S)F(SHA1(S) mod 256) and the compression map h2(X)-X mod 11. Therefore h(S)- h2(hi(S)) Example h("SAM")=(SHA1 ("SAM") mod 256) (04CD61 121 16E058F5A31 DEFEF2BC1 3DA3BDCB82)16 mod 256-(82)16-130 h(SAM")-h2(h1("SAM")) h2(130)-130 mod 11 9 You will use the hash table described above to simulate an algorithm that counts the frequency of words in a text in the following way. The hash table contains a pair (word, current frequency). For each word found on the text, you search for it in the table: if found increment its frequency, if not found, insert it. For example, the first time the word "SAM" is found in the text, the pair ("SAM",1) is inserted at the hash table at position 9. Every time "SAM" is found again, its frequency is incremented, so that at the end of the algorithm processing below the hash table will contain ("SAM",3) Use the text below for your simulation AM SAM. I AM SAM. SAM I AM THAT SAM-I-AM! THAT SAM-I-AM! I DO NOT LIKE THAT SAM-I-AM! Note: Ignore punctuation symbols but consider SAM-1-AM as a single word a) (1pt) Show the hash function for each word SHA1(word) CA73AB65568CD125C2D27A22BBD9E863C10B675D 80D305C58F97EDFAE92A3627F5A66D9BEF4D8D46 64CD61B12116E058F5A31DEFEF2BC 13DA3BDCB82 61A26854EE49839BBB7509F03BCB590FBC565738 word hi(word) h(word) AM SAM THAT SAM-I-AM 7439ABEAA4401A6A7B8B7C6B4A83CB2445E398EC DO NOT LIKE 8FEB29077A1DF95BD8E261F267CF55119B1EAC74 969E7D8DEE132181523A501A068FEC75BDED3005 5DDF6F04739D8BC3A11B487863B27A7BCAA6FC24 b) (1pt) Show the hash table after the first line is processed c) (2 pt) Show the hash table at the end of the word processing
