The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
Facebook Login
or
Email or Username
Password
Remember
Login
Register

I forgot my password
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
Recent questions tagged hashing
+1
vote
1
answer
1
ISRO202024
In linear hashing, if blocking factor $bfr$, loading factor $i$ and file buckets $N$ are known, the number of records will be $cr= i+bfr+N$ $r=ibfrN$ $r=i+bfrN$ $r=i*bfr*N$
asked
Jan 13
in
DS
by
Satbir
Boss
(
24k
points)

94
views
isro2020
datastructures
hashing
normal
+4
votes
3
answers
2
Made Easy Test Series: DSHash Table
Consider a hash table with $N$ slots. It is given that the collision resolution technique used in chaining. Assume simple uniform hashing, what is the probability that the last $k$ slots are unfilled after the first $'r'$ insertions? $A)\left ( 1\frac{N}{k} \right )^{r}$ ... $C)\left ( 1+\frac{N}{k} \right )^{r1}$ $D)\left ( 1\frac{k}{N} \right )^{r1}$
asked
May 5, 2019
in
DS
by
srestha
Veteran
(
119k
points)

168
views
datastructures
madeeasytestseries
hashing
0
votes
0
answers
3
Cormen Edition 3 Exercise 11.4 Question 5 (Page No. 277)
Consider an openaddress hash table with a load factor $\alpha$ Find the nonzero value $\alpha$ for which the expected number of probes in an unsuccessful search equals twice the expected number of probes in a successful search.
asked
Apr 4, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.4k
points)

42
views
cormen
algorithms
hashing
descriptive
0
votes
0
answers
4
Cormen Edition 3 Exercise 11.4 Question 4 (Page No. 277)
Suppose that we use double hashing to resolve collisionsthat is, we use the hash function $h(k,i) = (h_1(k) + ih_2(k))$ $mod$ $m$.Show that if $m$ and $h_2(k)$ have greatest common divisor $d\geq 1$ for some key $k$,then ... $d=1$, so that $m$ and $h_2(k)$ are relatively prime, the search may examine the entire hash table.
asked
Apr 4, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.4k
points)

20
views
cormen
algorithms
hashing
descriptive
0
votes
0
answers
5
Cormen Edition 3 Exercise 11.4 Question 3 (Page No. 277)
Consider an openaddress hash table with uniform hashing. Give upper bounds on the expected number of probes in an unsuccessful search and on the expected number of probes in a successful search when the load factor is $3/4$ and when it is $7/8$.
asked
Apr 4, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.4k
points)

32
views
cormen
algorithms
hashing
descriptive
0
votes
0
answers
6
Cormen Edition 3 Exercise 11.4 Question 2 (Page No. 277)
Write pseudo code for $HASHDELETE$ as outlined in the text, and modify $HASHINSERT$ to handle the special value $DELETED.$
asked
Apr 4, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.4k
points)

11
views
cormen
algorithms
hashing
descriptive
0
votes
0
answers
7
Cormen Edition 3 Exercise 11.4 Question 1 (Page No. 277)
Consider inserting the keys $10, 22, 31, 4,15,28,17,88,59$ into a hash table of length $m =11$ using open addressing with the auxiliary hash function $h'(k) =k$ ... double hashing with $h_1(k) =k$ and $h_2(k)$ $=$ $1$+$($k$ $mod$ $(m1)$)$.
asked
Apr 4, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.4k
points)

22
views
cormen
algorithms
hashing
descriptive
0
votes
0
answers
8
Cormen Edition 3 Exercise 11.3 Question 6 (Page No. 269)
Let $U$ be a set of $ntuples$ of values drawn from$\mathbb{\ Z_p}$ , let $B$ $=$ $\mathbb{\ Z_p}$ , where p is prime. Define the hash function $h_b :U \rightarrow B$ for $b$ $\in$\mathbb{\ Z_p}$ on an input $ ... $\mathscr{H}$ is $n(n1)/p$ universal according to the definition of the $\epsilon$ universal.
asked
Apr 4, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.4k
points)

17
views
cormen
algorithms
hashing
descriptive
0
votes
0
answers
9
Cormen Edition 3 Exercise 11.3 Question 5 (Page No. 269)
Define a family $\mathscr{H}$ of hash functions from a finite set $U$ to a finite set $B$ to be universal if for all pairs of distinct elements $k$ and $l$ in $U$, $Pr\{h(k) = h(l)\} \leq \epsilon$ where the probability is ... Show that an $\epsilon$universal family of hash functions must have $\epsilon \geq \frac{1}{B}  \frac{1}{U}$
asked
Apr 4, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.4k
points)

17
views
cormen
algorithms
hashing
descriptive
0
votes
1
answer
10
Cormen Edition 3 Exercise 11.3 Question 4 (Page No. 269)
Consider a hash table of size $m =1000$ and a corresponding hash function $h(k) =$ $\lfloor$ $m$($kA$ $mod$ $1$)$\rfloor$ for $A = \frac{(\sqrt{5} – 1)}{2}$ .Compute the locations to which the keys $61, 62, 63, 64,$ and $65$ are mapped.
asked
Apr 4, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.4k
points)

37
views
cormen
algorithms
hashing
0
votes
0
answers
11
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^p1$ 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.
asked
Apr 4, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.4k
points)

9
views
cormen
algorithms
hashing
descriptive
0
votes
0
answers
12
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 $radix128$ number and then using the division method. We can easily represent the number $m$ as a $32bit$ 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 ?
asked
Apr 4, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.4k
points)

10
views
cormen
algorithms
hashing
descriptive
0
votes
0
answers
13
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 ?
asked
Apr 4, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.4k
points)

5
views
cormen
algorithms
hashing
descriptive
0
votes
0
answers
14
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}))$.
asked
Apr 4, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.4k
points)

19
views
cormen
algorithms
hashing
descriptive
0
votes
0
answers
15
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 worstcase searching time for hashing with chaining is $\Theta(n)$.
asked
Apr 4, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.4k
points)

14
views
cormen
algorithms
hashing
descriptive
0
votes
0
answers
16
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?
asked
Apr 4, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.4k
points)

11
views
cormen
algorithms
hashing
descriptive
0
votes
0
answers
17
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?
asked
Apr 4, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.4k
points)

17
views
cormen
algorithms
hashing
descriptive
0
votes
0
answers
18
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$.$
asked
Apr 4, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.4k
points)

9
views
cormen
algorithms
hashing
0
votes
0
answers
19
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)\}$ ?
asked
Apr 4, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.4k
points)

30
views
cormen
algorithms
hashing
descriptive
0
votes
0
answers
20
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.)
asked
Apr 4, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.4k
points)

15
views
cormen
algorithms
hashing
descriptive
0
votes
0
answers
21
Cormen Edition 3 Exercise 11.1 Question 3 (Page No. 255)
Suggest how to implement a directaddress 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.)
asked
Apr 4, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.4k
points)

24
views
cormen
algorithms
hashing
descriptive
0
votes
0
answers
22
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.
asked
Apr 4, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.4k
points)

23
views
cormen
algorithms
hashing
descriptive
0
votes
0
answers
23
Cormen Edition 3 Exercise 11.1 Question 1 (Page No. 255)
Suppose that a dynamic set $S$ is represented by a directaddress table $T$ of length $m$. Describe a procedure that finds the maximum element of $S$. What is the worstcase performance of your procedure ?
asked
Apr 4, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.4k
points)

10
views
cormen
algorithms
hashing
0
votes
0
answers
24
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 ?
asked
Apr 1, 2019
in
Databases
by
akash.dinkar12
Boss
(
42.4k
points)

6
views
korth
databases
hashing
descriptive
0
votes
1
answer
25
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 ?
asked
Apr 1, 2019
in
Databases
by
akash.dinkar12
Boss
(
42.4k
points)

59
views
korth
databases
hashing
descriptive
0
votes
0
answers
26
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 searchkey 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.
asked
Apr 1, 2019
in
Databases
by
akash.dinkar12
Boss
(
42.4k
points)

23
views
korth
databases
hashing
descriptive
0
votes
1
answer
27
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 ?
asked
Apr 1, 2019
in
Databases
by
akash.dinkar12
Boss
(
42.4k
points)

17
views
korth
databases
hashing
descriptive
0
votes
1
answer
28
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.
asked
Apr 1, 2019
in
Databases
by
akash.dinkar12
Boss
(
42.4k
points)

21
views
korth
databases
hashing
descriptive
0
votes
0
answers
29
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.
asked
Mar 29, 2019
in
Programming
by
Doraemon
Junior
(
787
points)

15
views
multiplicationmethod
hashing
+1
vote
0
answers
30
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?
asked
Mar 6, 2019
in
Algorithms
by
s_dr_13
(
283
points)

196
views
hashing
datastructures
uniformhashing
probability
Page:
1
2
3
4
5
6
7
next »
Quick search syntax
tags
tag:apple
author
user:martin
title
title:apple
content
content:apple
exclude
tag:apple
force match
+apple
views
views:100
score
score:10
answers
answers:2
is accepted
isaccepted:true
is closed
isclosed:true
Recent Posts
ISRO CSE 2020 PAPER ANALYSE
BARC OCES/DGFS 2020
ISI CMI PDF by GATE Overflow
Calculus Important Points
Management Trainee Recruitment COAL INDIA 2020
Follow @csegate
Recent questions tagged hashing
Recent Blog Comments
While raising objections what works as...
It is mentioned "Left for Evaluation" so no...
I think this discussion will keep on going till...
do we have to include marks of qs that are left...
@roh6jmon yes, it is there.
50,737
questions
57,317
answers
198,368
comments
105,103
users