Task 3.4.12 (from the book Algorithms, 4th edition, Princeton Uni.) Suppose that the keys A through...
Task 3.4.12 (from the book Algorithms, 4th edition, Princeton Uni.)
Suppose that the keys A through G, with the hash values given below, are inserted in some order into an initially empty table of size 7 using a linear-probing table (with no resizing for this problem),
| key | A | B | C | D | E | F | G |
| hash(M = 7) | 2 | 0 | 0 | 4 | 4 | 4 | 2 |
Which of the following could not possibly result from inserting these keys?
a) E F G A C B D
b) C E B G F D A
c) B D F A C E G
d) C G B A D E F
e) F G B D A C E
f) G E C A D B F
Give the minimum and the maximum number of probes that could be required to build a table of size 7 with these keys, and an insertion order that justifies your answer.
Homework Answers
Add Answer to:
Task 3.4.12 (from the book Algorithms, 4th edition, Princeton
Uni.)
Suppose that the keys A through...
5. Hashing (a) Consider a hash table with separate chaining of size M = 5 and...
5. Hashing (a) Consider a hash table with separate chaining of size M = 5 and the hash function h(x) = x mod 5. i. (1) Pick 8 random numbers in the range of 10 to 99 and write the numbers in the picked sequence. Marks will only be given for proper random numbers (e.g., 11, 12, 13, 14 ... or 10, 20, 30, 40, .. are not acceptable random sequences). ii. (2) Draw a sketch of the hash table...
Tree & Hash Table & Heap Use the following integer keys 73, 58, 91, 42, 60,...
Tree & Hash Table & Heap Use the following integer keys 73, 58, 91, 42, 60, 130, 64, 87 to perform the followings: a) Binary Search Tree - Draw a binary search tree - Retrieve the integers keys in post-order - Retrieve the integers keys in pre-order - Draw a binary search tree after node 58 is deleted b) Create a Hash Table using the methods described below. Show the final array after all integer keys are inserted. Assumes that...
Tree & Hash Table & Heap Use the following integer keys 73, 58, 91, 42, 60, 130, 64, 87 to perform the followings: a) Binary Search Tree - Draw a binary search tree - Retrieve the integers ke...
Tree & Hash Table & Heap Use the following integer keys 73, 58, 91, 42, 60, 130, 64, 87 to perform the followings: a) Binary Search Tree - Draw a binary search tree - Retrieve the integers keys in post-order - Retrieve the integers keys in pre-order - Draw a binary search tree after node 58 is deleted b) Create a Hash Table using the methods described below. Show the final array after all integer keys are inserted. Assumes that...
13) consider the following sequence of keys to be inserted in a hash table of size...
13) consider the following sequence of keys to be inserted in a hash table of size 13 that uses a quadratic probing to resolve collisions select the choice that indicateds what the hash table looks like after all the keys are inserted (0 indicates an empty slot) {23, 4, 78 , 17 , 30, 81, 41, 5} a) 78, 41, 0, 81, 4, 5, 17, 0, 30, 0, 23, 0, 0 b) 78, 17, 41, 81, 4, 5, 0, 30,...
10 points 10) Using Hopscotch hashing with a max hop of 4, hash the following keys....
10 points 10) Using Hopscotch hashing with a max hop of 4, hash the following keys. Table size is 15 A: 6 B: 7 c: 9 D: 7 E: 7 F: 6 G: 8
Show how the following data would be stored in a hash table of size 7 (the...
Show how the following data would be stored in a hash table of size 7 (the size is fixed) using quadratic probing. If any insertion fails, indicate that, but keep trying to insert all the remaining data. The hash function is hash(x) = x mod 7. Here is the data to be stored: 17, 10, 31, 45, 3, 53, 14. Insert the data in the order given. Data: Index: 0 1 2 3 4 5 6 4 data: Index: 31...
1. Suppose that a hash table contains hash_size = 13 entries indexed from 0 through 12...
1. Suppose that a hash table contains hash_size = 13 entries indexed from 0 through 12 and that the following keys are to be mapped into the table: 24 34 33 55 46 38 37 The hash function determines the hash address by first summing all digits of a key (in ordinary decimal representation) and then applying % hash_size. Answer the following questions. Assume that double hashing g(k) = 7 – (k mod 7) is used. Present the hash table...
DATA STRUCTURE: Draw the structure that results from inserting the following numerical keys into each of...
DATA STRUCTURE: Draw the structure that results from inserting the following numerical keys into each of the structures given, starting from an empty structure. Keys: 17 29 25 48 9 36 3 31 (a) Heap (min heap) (b) Hash table of size 11, using double hashing with primary hash function h(x) =x mod 11 and secondary hash function d(x) = 5 − (x mod 5) (c) AVL Tree
Assume a Hash table has 7 slots and the hash function h(k) = k mod 7...
Assume a Hash table has 7 slots and the hash function h(k) = k mod 7 is used. The keys 14, 3, 11, 6, 10, 4, 20, and 17 are inserted in the table with collision resolution by chaining. Assume that the keys arrive in the order shown. (a) Show the hash table obtained after inserting all 8 keys. [Show only the final table] (b) Under the assumption that each key is searched with probability 1/8, calculate expected number of...
design hash table Suppose you need to design a hash table. The keys themselves are (pointers...
design hash table
Suppose you need to design a hash table. The keys themselves are (pointers to) C-style zero-terminating strings, so the string "foobar" occupies seven bytes. You are interested in minimizing the space used while keeping search time within reasonable bounds. You expect to store 1000 names with (on average) 7 letters each. If, for example, you choose separate chaining with 2000 buckets, the space required will be 24000 bytes: 8000 = (2000 buckets times 4 bytes per bucket...
5. Hashing (a) Consider a hash table with separate chaining of size M = 5 and the hash function h(x) = x mod 5. i. (1) Pick 8 random numbers in the range of 10 to 99 and write the numbers in the picked sequence. Marks will only be given for proper random numbers (e.g., 11, 12, 13, 14 ... or 10, 20, 30, 40, .. are not acceptable random sequences). ii. (2) Draw a sketch of the hash table...
10 points 10) Using Hopscotch hashing with a max hop of 4, hash the following keys. Table size is 15 A: 6 B: 7 c: 9 D: 7 E: 7 F: 6 G: 8
Show how the following data would be stored in a hash table of size 7 (the size is fixed) using quadratic probing. If any insertion fails, indicate that, but keep trying to insert all the remaining data. The hash function is hash(x) = x mod 7. Here is the data to be stored: 17, 10, 31, 45, 3, 53, 14. Insert the data in the order given. Data: Index: 0 1 2 3 4 5 6 4 data: Index: 31...
design hash table
Suppose you need to design a hash table. The keys themselves are (pointers to) C-style zero-terminating strings, so the string "foobar" occupies seven bytes. You are interested in minimizing the space used while keeping search time within reasonable bounds. You expect to store 1000 names with (on average) 7 letters each. If, for example, you choose separate chaining with 2000 buckets, the space required will be 24000 bytes: 8000 = (2000 buckets times 4 bytes per bucket...
Most questions answered within 3 hours.
-
I calculate Rosetta Stone’s P/E ratio as 10x prior to a report
about future industry growth....
asked 18 minutes ago -
What major physiological changes account for electrodermal
activity (as in during a lie-detector test)?
asked 1 hour ago -
You are going to sell fruits & vegetables at a local
roadside market. List separately and...
asked 1 hour ago -
Hows does water affect the digestion of fats ?
asked 4 hours ago -
A buffer that contains 0.41 M of a base, B and 0.21 M of its
conjugate...
asked 4 hours ago -
Pleaaaaaaaasssssse help me please please it's more important
:((((((((((((((((((((
CASE STUDY
Nissan Company
Nissan Motor Company,...
asked 4 hours ago -
Calculate the concentration of hydronium and hyroxide ions in 1)
2.0 mol/L HNO3 2) 0.5 mol/L...
asked 4 hours ago -
In a loop-the-loop ride a car goes around a vertical, circular
loop at a constant speed....
asked 4 hours ago -
50 grams each of water (18.015 g/mol) and ethylene glycol
(C2H6O2) (62.07 g/mol) are mixed. At...
asked 4 hours ago -
The life expectancy of sport utility vehicles follows a normal
distribution with a mean of 145.8...
asked 5 hours ago -
If an object with mass of 5 kg is pushed with a force of 552 N,...
asked 4 hours ago -
Suppose your program already has a list called nums, which
contains several numbers. Write a for...
asked 5 hours ago