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
All Activity
Questions
Unanswered
Tags
Categories
Users
Ask a Question
Prev
Blogs
New Blog
Exams
First time here? Checkout the
FAQ
!
x
×
Close
Use the google search bar on side panel. It searches through all previous GATE/other questions. For hardcopy of previous year questions please see
here
Recent questions tagged hashing
+1
vote
2
answers
1
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
in
DS
by
srestha
Veteran
(
113k
points)

84
views
datastructure
madeeasytestseries
hashing
0
votes
0
answers
2
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
in
Algorithms
by
akash.dinkar12
Boss
(
41.3k
points)

25
views
cormen
algorithms
hashing
descriptive
0
votes
0
answers
3
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
in
Algorithms
by
akash.dinkar12
Boss
(
41.3k
points)

12
views
cormen
algorithms
hashing
descriptive
0
votes
0
answers
4
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
in
Algorithms
by
akash.dinkar12
Boss
(
41.3k
points)

16
views
cormen
algorithms
hashing
descriptive
0
votes
0
answers
5
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
in
Algorithms
by
akash.dinkar12
Boss
(
41.3k
points)

8
views
cormen
algorithms
hashing
descriptive
0
votes
0
answers
6
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
in
Algorithms
by
akash.dinkar12
Boss
(
41.3k
points)

13
views
cormen
algorithms
hashing
descriptive
0
votes
0
answers
7
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
in
Algorithms
by
akash.dinkar12
Boss
(
41.3k
points)

10
views
cormen
algorithms
hashing
descriptive
0
votes
0
answers
8
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
in
Algorithms
by
akash.dinkar12
Boss
(
41.3k
points)

10
views
cormen
algorithms
hashing
descriptive
0
votes
1
answer
9
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
in
Algorithms
by
akash.dinkar12
Boss
(
41.3k
points)

18
views
cormen
algorithms
hashing
0
votes
0
answers
10
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
in
Algorithms
by
akash.dinkar12
Boss
(
41.3k
points)

5
views
cormen
algorithms
hashing
descriptive
0
votes
0
answers
11
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
in
Algorithms
by
akash.dinkar12
Boss
(
41.3k
points)

8
views
cormen
algorithms
hashing
descriptive
0
votes
0
answers
12
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
in
Algorithms
by
akash.dinkar12
Boss
(
41.3k
points)

3
views
cormen
algorithms
hashing
descriptive
0
votes
0
answers
13
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
in
Algorithms
by
akash.dinkar12
Boss
(
41.3k
points)

11
views
cormen
algorithms
hashing
descriptive
0
votes
0
answers
14
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
in
Algorithms
by
akash.dinkar12
Boss
(
41.3k
points)

10
views
cormen
algorithms
hashing
descriptive
0
votes
0
answers
15
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
in
Algorithms
by
akash.dinkar12
Boss
(
41.3k
points)

7
views
cormen
algorithms
hashing
descriptive
0
votes
0
answers
16
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
in
Algorithms
by
akash.dinkar12
Boss
(
41.3k
points)

14
views
cormen
algorithms
hashing
descriptive
0
votes
0
answers
17
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
in
Algorithms
by
akash.dinkar12
Boss
(
41.3k
points)

4
views
cormen
algorithms
hashing
0
votes
0
answers
18
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
in
Algorithms
by
akash.dinkar12
Boss
(
41.3k
points)

18
views
cormen
algorithms
hashing
descriptive
0
votes
0
answers
19
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
in
Algorithms
by
akash.dinkar12
Boss
(
41.3k
points)

12
views
cormen
algorithms
hashing
descriptive
0
votes
0
answers
20
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
in
Algorithms
by
akash.dinkar12
Boss
(
41.3k
points)

18
views
cormen
algorithms
hashing
descriptive
0
votes
0
answers
21
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
in
Algorithms
by
akash.dinkar12
Boss
(
41.3k
points)

12
views
cormen
algorithms
hashing
descriptive
0
votes
0
answers
22
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
in
Algorithms
by
akash.dinkar12
Boss
(
41.3k
points)

8
views
cormen
algorithms
hashing
0
votes
0
answers
23
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
in
Databases
by
akash.dinkar12
Boss
(
41.3k
points)

5
views
korth
databases
hashing
descriptive
0
votes
1
answer
24
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
in
Databases
by
akash.dinkar12
Boss
(
41.3k
points)

34
views
korth
databases
hashing
descriptive
0
votes
0
answers
25
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
in
Databases
by
akash.dinkar12
Boss
(
41.3k
points)

13
views
korth
databases
hashing
descriptive
0
votes
1
answer
26
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
in
Databases
by
akash.dinkar12
Boss
(
41.3k
points)

11
views
korth
databases
hashing
descriptive
0
votes
1
answer
27
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
in
Databases
by
akash.dinkar12
Boss
(
41.3k
points)

14
views
korth
databases
hashing
descriptive
0
votes
0
answers
28
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
in
Programming
by
Doraemon
(
351
points)

10
views
multiplicationmethod
hashing
0
votes
0
answers
29
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
in
Algorithms
by
s_dr_13
(
133
points)

109
views
hashing
datastructure
uniformhashing
probability
0
votes
0
answers
30
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
asked
Jan 27
in
DS
by
Ram Swaroop
Active
(
4k
points)

177
views
programminginc
datastructure
hashing
madeeasytestseries2019
madeeasytestseries
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
ISI MTECH CS 2019 INTERVIEW EXPERIENCE
IIT HYDERABAD MTECH TA INTERVIEW EXPERIENCE
How to prepare for GATE with a fulltime job??
Interview Experience at IISc
All subject Gate notes from Standard Books!!
Follow @csegate
Recent questions tagged hashing
Recent Blog Comments
Refund time depends on the payment mode ...
@Arjun Sir , when can i expect my refund in the...
This book is returned you can enable a pay now...
@Pranavcool The book stocks are over and no one...
@Lokesh Thats unfortunate. I have refunded you....
49,830
questions
54,807
answers
189,530
comments
80,840
users