Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Recent questions tagged hashing
0
votes
0
answers
91
Cormen Edition 3 Exercise 11.3 Question 3 (Page No. 269)
Consider a version of the division method in which $h(k) =k$ $mod$ $m$, where $m = 2^p-1$ and $k$ is a character string interpreted in $radix$ $2^p$. Show that if we can derive string $x$ from string $y$ by ... $y$ hash to the same value. Give an example of an application in which this property would be undesirable in a hash function.
Consider a version of the division method in which $h(k) =k$ $mod$ $m$, where $m = 2^p-1$ and $k$ is a character string interpreted in $radix$ $2^p$. Show that if we can ...
akash.dinkar12
329
views
akash.dinkar12
asked
Apr 4, 2019
Algorithms
cormen
algorithms
hashing
descriptive
+
–
0
votes
0
answers
92
Cormen Edition 3 Exercise 11.3 Question 2 (Page No. 268)
Suppose that we hash a string of $r$ characters into $m$ slots by treating it as a $radix-128$ number and then using the division method. We can easily represent the number $m$ as a $32-bit$ computer word, but ... the hash value of the character string without using more than a constant number of words of storage outside the string itself ?
Suppose that we hash a string of $r$ characters into $m$ slots by treating it as a $radix-128$ number and then using the division method. We can easily represent the numb...
akash.dinkar12
194
views
akash.dinkar12
asked
Apr 4, 2019
Algorithms
cormen
algorithms
hashing
descriptive
+
–
0
votes
0
answers
93
Cormen Edition 3 Exercise 11.3 Question 1 (Page No. 268)
Suppose we wish to search a linked list of length $n$, where each element contains a key $k$ along with a hash value $h(k)$. Each key is a long character string. How might we take advantage of the hash values when searching the list for an element with a given key ?
Suppose we wish to search a linked list of length $n$, where each element contains a key $k$ along with a hash value $h(k)$. Each key is a long character string. How migh...
akash.dinkar12
191
views
akash.dinkar12
asked
Apr 4, 2019
Algorithms
cormen
algorithms
hashing
descriptive
+
–
0
votes
0
answers
94
Cormen Edition 3 Exercise 11.2 Question 6 (Page No. 261)
Suppose we have stored $n$ keys in a hash table of size $m$, with collisions resolved by chaining, and that we know the length of each chain, including the length $L$ of the longest chain. Describe a procedure that selects a key uniformly at ... the keys in the hash table and returns it in expected time $\mathcal{O}(L*(1+\frac{1}{\alpha}))$.
Suppose we have stored $n$ keys in a hash table of size $m$, with collisions resolved by chaining, and that we know the length of each chain, including the length $L$ of ...
akash.dinkar12
338
views
akash.dinkar12
asked
Apr 4, 2019
Algorithms
cormen
algorithms
hashing
descriptive
+
–
0
votes
0
answers
95
Cormen Edition 3 Exercise 11.2 Question 5 (Page No. 261)
Suppose that we are storing a set of $n$ keys into a hash table of size $m$. Show that if the keys are drawn from a universe $U$ with $|U| > nm$, then $U$ has a subset of size $n$ consisting of keys that all hash to the same slot, so that the worst-case searching time for hashing with chaining is $\Theta(n)$.
Suppose that we are storing a set of $n$ keys into a hash table of size $m$. Show that if the keys are drawn from a universe $U$ with $|U| nm$, then $U$ has a subset of ...
akash.dinkar12
280
views
akash.dinkar12
asked
Apr 4, 2019
Algorithms
cormen
algorithms
hashing
descriptive
+
–
0
votes
0
answers
96
Cormen Edition 3 Exercise 11.2 Question 4 (Page No. 261)
Suggest how to allocate and deallocate storage for elements within the hash table itself by linking all unused slots into a free list. Assume that one slot can store a flag and either one element plus a pointer or two pointers. All ... expected time. Does the free list need to be doubly linked, or does a singly linked free list suffice?
Suggest how to allocate and deallocate storage for elements within the hash table itself by linking all unused slots into a free list. Assume that one slot can store a fl...
akash.dinkar12
263
views
akash.dinkar12
asked
Apr 4, 2019
Algorithms
cormen
algorithms
hashing
descriptive
+
–
0
votes
0
answers
97
Cormen Edition 3 Exercise 11.2 Question 3 (Page No. 261)
Professor Marley hypothesizes that he can obtain substantial performance gains by modifying the chaining scheme to keep each list in sorted order. How does the professor’s modification affect the running time for successful searches, unsuccessful searches, insertions, and deletions?
Professor Marley hypothesizes that he can obtain substantial performance gains by modifying the chaining scheme to keep each list in sorted order. How does the professor�...
akash.dinkar12
490
views
akash.dinkar12
asked
Apr 4, 2019
Algorithms
cormen
algorithms
hashing
descriptive
+
–
0
votes
0
answers
98
Cormen Edition 3 Exercise 11.2 Question 2 (Page No. 261)
Demonstrate what happens when we insert the keys $5,28,19,15,20,33,12,17,10$ into a hash table with collisions resolved by chaining. Let the table have $9$ slots, and let the hash function be $h(k) = k$ $mod$ $9$.$
Demonstrate what happens when we insert the keys $5,28,19,15,20,33,12,17,10$ into a hash table with collisions resolved by chaining. Let the table have $9$ slots, and let...
akash.dinkar12
299
views
akash.dinkar12
asked
Apr 4, 2019
Algorithms
cormen
algorithms
hashing
+
–
0
votes
0
answers
99
Cormen Edition 3 Exercise 11.2 Question 1 (Page No. 261)
Suppose we use a hash function $h$ to hash $n$ distinct keys into an array $T$ of length $m$. Assuming simple uniform hashing, what is the expected number of collisions ? More precisely, what is the expected cardinality of $\{\{k,l\}:k\neq l and h(k)=h(l)\}$ ?
Suppose we use a hash function $h$ to hash $n$ distinct keys into an array $T$ of length $m$. Assuming simple uniform hashing, what is the expected number of collisions ?...
akash.dinkar12
408
views
akash.dinkar12
asked
Apr 4, 2019
Algorithms
cormen
algorithms
hashing
descriptive
+
–
1
votes
0
answers
100
Cormen Edition 3 Exercise 11.1 Question 4 (Page No. 255)
We wish to implement a dictionary by using direct addressing on a huge array. At the start, the array entries may contain garbage, and initializing the entire array is impractical because of its size. Describe a scheme for implementing a ... stored in the dictionary, to help determine whether a given entry in the huge array is valid or not.)
We wish to implement a dictionary by using direct addressing on a huge array. At the start, the array entries may contain garbage, and initializing the entire array is im...
akash.dinkar12
338
views
akash.dinkar12
asked
Apr 4, 2019
Algorithms
cormen
algorithms
hashing
descriptive
+
–
0
votes
0
answers
101
Cormen Edition 3 Exercise 11.1 Question 3 (Page No. 255)
Suggest how to implement a direct-address table in which the keys of stored elements do not need to be distinct and the elements can have satellite data. All three dictionary operations ($INSERT$,$ DELETE$, and $SEARCH$ ... (Don't forget that $DELETE$ takes as an argument a pointer to an object to be deleted, not a key.)
Suggest how to implement a direct-address table in which the keys of stored elements do not need to be distinct and the elements can have satellite data. All three dictio...
akash.dinkar12
343
views
akash.dinkar12
asked
Apr 4, 2019
Algorithms
cormen
algorithms
hashing
descriptive
+
–
0
votes
0
answers
102
Cormen Edition 3 Exercise 11.1 Question 2 (Page No. 255)
A bit vector is simply an array of bits ($0s$ and $1s$). A bit vector of length $m$ takes much less space than an array of $m$ pointers. Describe how to use a bit vector to represent a dynamic set of distinct elements with no satellite data. Dictionary operations should run in $\mathcal{O}(1)$ time.
A bit vector is simply an array of bits ($0s$ and $1s$). A bit vector of length $m$ takes much less space than an array of $m$ pointers. Describe how to use a bit vector ...
akash.dinkar12
246
views
akash.dinkar12
asked
Apr 4, 2019
Algorithms
cormen
algorithms
hashing
descriptive
+
–
0
votes
1
answer
103
Cormen Edition 3 Exercise 11.1 Question 1 (Page No. 255)
Suppose that a dynamic set $S$ is represented by a direct-address table $T$ of length $m$. Describe a procedure that finds the maximum element of $S$. What is the worst-case performance of your procedure ?
Suppose that a dynamic set $S$ is represented by a direct-address table $T$ of length $m$. Describe a procedure that finds the maximum element of $S$. What is the worst-c...
akash.dinkar12
872
views
akash.dinkar12
asked
Apr 4, 2019
Algorithms
cormen
algorithms
hashing
+
–
0
votes
0
answers
104
DBMS Korth Edition 4 Exercise 11 Question 20 (Page No. 491)
How does data encryption affect index schemes ? In particular, how might it affect schemes that attempt to store data in sorted order ?
How does data encryption affect index schemes ? In particular, how might it affect schemes that attempt to store data in sorted order ?
akash.dinkar12
297
views
akash.dinkar12
asked
Apr 1, 2019
Databases
korth
databases
hashing
descriptive
+
–
0
votes
1
answer
105
DBMS Korth Edition 4 Exercise 12 Question 16 (Page No. 491)
Why is a hash structure not the best choice for a search key on which range queries are likely ?
Why is a hash structure not the best choice for a search key on which range queries are likely ?
akash.dinkar12
1.7k
views
akash.dinkar12
asked
Apr 1, 2019
Databases
korth
databases
hashing
descriptive
+
–
1
votes
1
answer
106
DBMS Korth Edition 4 Exercise 12 Question 12 (Page No. 490)
Suppose that we are using extendable hashing on a file that contains records with the following search-key values: $2, 3, 5, 7, 11, 17, 19, 23, 29, 31$ Show the extendable hash structure for this file if the hash function is $h(x)$ $=$ $x$ $mod$ $8$ and buckets can hold three records.
Suppose that we are using extendable hashing on a file that contains records with the following search-key values:$2, 3, 5, 7, 11, 17, 19, 23, 29, 31$Show the extendable ...
akash.dinkar12
2.5k
views
akash.dinkar12
asked
Apr 1, 2019
Databases
korth
databases
hashing
descriptive
+
–
0
votes
1
answer
107
DBMS Korth Edition 4 Exercise 12 Question 11 (Page No. 491)
What are the causes of bucket overflow in a hash file organization ? What can be done to reduce the occurrence of bucket overflows ?
What are the causes of bucket overflow in a hash file organization ? What can be done to reduce the occurrence of bucket overflows ?
akash.dinkar12
657
views
akash.dinkar12
asked
Apr 1, 2019
Databases
korth
databases
hashing
descriptive
+
–
0
votes
1
answer
108
DBMS Korth Edition 4 Exercise 12 Question 10 (Page No. 491)
Explain the distinction between closed and open hashing. Discuss the relative merits of each technique in database applications.
Explain the distinction between closed and open hashing. Discuss the relative merits of each technique in database applications.
akash.dinkar12
1.1k
views
akash.dinkar12
asked
Apr 1, 2019
Databases
korth
databases
hashing
descriptive
+
–
0
votes
0
answers
109
self doubt
For multiplication method in hashing the formula is h(k)=m* (KA mod 1); m=2^p, k=key , 0<A<1 My question is how does it actually works. Please explain in a detailed way.
For multiplication method in hashing the formula is h(k)=m* (KA mod 1);m=2^p, k=key , 0<A<1My question is how does it actually works.Please explain in a detailed way.
Doraemon
336
views
Doraemon
asked
Mar 29, 2019
Programming in C
multiplication-method
hashing
+
–
1
votes
1
answer
110
Hashing
Consider an open address hash table with uniform hashing. Out of 10 locations, 8 are occupied. What are the expected number of probes in an unsuccessful and successful search respectively?
Consider an open address hash table with uniform hashing. Out of 10 locations, 8 are occupied. What are the expected number of probes in an unsuccessful and successful se...
s_dr_13
972
views
s_dr_13
asked
Mar 6, 2019
Algorithms
hashing
data-structures
uniform-hashing
probability
+
–
0
votes
1
answer
111
MadeEasy Test Series 2019: Programming & DS - Hashing
Consider the hashing table with 'm' slots and 'n' keys. If the expected number of probes in unsuccessful search is 3. The expected number of probes in a successful search is_ Answer 1.647
Consider the hashing table with 'm' slots and 'n' keys. If the expected number of probes in unsuccessful search is 3. The expected number of probes in a successful search...
Ram Swaroop
1.3k
views
Ram Swaroop
asked
Jan 27, 2019
DS
programming-in-c
data-structures
hashing
made-easy-test-series
+
–
1
votes
1
answer
112
Applied Course | Mock GATE | Test 1 | Question: 57
Insert the following keys in an array of size $17$ using the modulo division method. Use double hashing to resolve collisions. Take $h'(k) = (\text{key%}7)+1$ as the second hash function: $94, 37, 29, 40, 84, 88, 102, 63, 67, 120, 122$. What is the value present at location $7$ ____
Insert the following keys in an array of size $17$ using the modulo division method. Use double hashing to resolve collisions. Take $h'(k) = (\text{key%}7)+1$ as the seco...
Applied Course
1.4k
views
Applied Course
asked
Jan 16, 2019
Algorithms
applied-course-2019-mock1
numerical-answers
algorithms
hashing
+
–
1
votes
3
answers
113
Insertion in Hash table. (M.E.)
The number of different insertion sequences of numbers $\left \{ 7,20,32,50,66,77 \right \}$ on an initially empty hash table H of size $6$ and a hash function $h\left ( k \right )=k\mod6$ with linear probing scheme for collision resolution such that the hash table obtained ... ${\color{Blue} {2}}$ ${\color{Blue} {3}}$. ${\color{Blue} {4}}$ ${\color{Blue} {5}}$
The number of different insertion sequences of numbers $\left \{ 7,20,32,50,66,77 \right \}$ on an initially empty hash table H of size $6$ and a hash function $h\left ( ...
srestha
1.0k
views
srestha
asked
Jan 16, 2019
DS
hashing
data-structures
+
–
0
votes
1
answer
114
me test
Consider an initially empty hash table of length 10. Following set of keys are inserted using open addressing with hash function h(k) = k mod 10 and linear probing. The number of different insertion sequence of the key values using the given hash function and linear probing will result in the hash table shown in above? (given ans is 128 but i am getting 288)
Consider an initially empty hash table of length 10. Following set of keys are inserted using open addressing with hash function h(k) = k mod 10 and linear probing.The nu...
newdreamz a1-z0
1.0k
views
newdreamz a1-z0
asked
Jan 12, 2019
Programming in C
data-structures
hashing
+
–
0
votes
1
answer
115
MadeEasy Test Series: Programming & DS - Hashing
Consider the following keys that are hashed into the hash table in the order given using the hash function H(i) = (3i+5)mod11. 12,44,13,88,23,94,11,39,20,16,5 where to handle the collision chaining is used, after inserting ... in table if 2 new keys inserted into table, what is the probability new items hashed into empty slot?(upto 2 decimal places)
Consider the following keys that are hashed into the hash table in the order given using the hash function H(i) = (3i+5)mod11.12,44,13,88,23,94,11,39,20,16,5where to hand...
Ollie
654
views
Ollie
asked
Jan 11, 2019
DS
made-easy-test-series
hashing
probability
+
–
0
votes
1
answer
116
UPPCL AE 2018:53
Consider a hash table of size $7$ implemented using an array $A[0 \dots 6].$ A modulo hash function $\text{(MOD 7)}$ is used to map the keys, and open addressing is used to handle collisions. If $53, 32, 43, 51, 99$ ... $\text{EMPTY}, 43, 51, 99, 53, 32, \text{EMPTY}$ $\text{EMPTY}, 43, 99, 51, 32, 53, \text{EMPTY}$
Consider a hash table of size $7$ implemented using an array $A[0 \dots 6].$ A modulo hash function $\text{(MOD 7)}$ is used to map the keys, and open addressing is used ...
admin
324
views
admin
asked
Jan 5, 2019
Algorithms
uppcl2018
algorithms
hashing
+
–
1
votes
1
answer
117
MadeEasy Test Series: Programming & DS - Hashing
Consider the hashing table with m' slots and n' keys. If the expected number of probes in an unsuccessful search is 3, the expected number of probes in successful search is _____(Up to 2 decimals) Ans. 1.647 Here by default ... given here in the table http://cs360.cs.ua.edu/notes/hashing_formulas.pdf With linear hashing, I am getting around 1.61
Consider the hashing table with ‘m’ slots and ‘n’ keys. If the expected number of probes in an unsuccessful search is 3, the expected number of probes in success...
MiNiPanda
906
views
MiNiPanda
asked
Jan 1, 2019
Programming in C
made-easy-test-series
data-structures
hashing
+
–
0
votes
0
answers
118
CLRS HASHING(EXERCISE 11.2-3)
Q)Professor Marley hypothesizes that substantial performance gains can be obtained if we modify the chaining scheme so that each list is kept in sorted order. How does the professor's modification affect the running time for successful searches, unsuccessful searches, ... what basis are we going to sort the elements? As, In a list all the elements have same key values
Q)Professor Marley hypothesizes that substantial performance gains can be obtainedif we modify the chaining scheme so that each list is kept in sorted order. Howdoes the ...
vk_9_1_9
629
views
vk_9_1_9
asked
Dec 31, 2018
Algorithms
hashing
chaining
+
–
0
votes
0
answers
119
hashing
A) (1-(N / K)) ^ r b) (1-(K / N)) ^ r c) (1+(N / K)) ^ r-1 d) (1-(K / N)) ^ r-1
A) (1-(N / K)) ^ r b) (1-(K / N)) ^ r c) (1+(N / K)) ^ r-1 d) (1-(K / N)) ^ r-1
Rahul_Rathod_
422
views
Rahul_Rathod_
asked
Dec 28, 2018
DS
hashing
data-structures
probability
uniform-hashing
+
–
0
votes
1
answer
120
Testbook Test Series: Programming & DS - Hashing
How to solve such kind of questions ? Can anybody tell what's is the concept behind this ?? someone provide me link so that I read it and understand the actual concept
How to solve such kind of questions ? Can anybody tell what's is the concept behind this ?? someone provide me link so that I read it and understand the actual concept
Magma
506
views
Magma
asked
Dec 27, 2018
DS
testbook-test-series
data-structures
hashing
+
–
Page:
« prev
1
2
3
4
5
6
7
8
9
...
11
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register