In this article i am gone to share Coursera Course Graph Search, Shortest Paths, and Data Structures Week 4 | Problem Set #4 Quiz Answer with you..

Graph Search, Shortest Paths, and Data Structures

Also Visit This Link: Problem Set #3 Quiz Answer

Problem Set #4 Quiz Answer

Question 1)
Which of the following is not a property that you expect a well-designed hash function to have?

• The hash function should “spread out” every data set (across the buckets/slots of the hash table).
• The hash function should be easy to compute (constant time or close to it).
• The hash function should be easy to store (constant space or close to it).
• The hash function should “spread out” most (i.e., “non-pathological”) data sets (across the buckets/slots of the hash table).

Question 2)
Suppose we use a hash function h to hash n distinct keys into an array T of length m. Assuming simple uniform hashing — that is, with each key mapped independently and uniformly to a random bucket — what is the expected number of keys that get mapped to the first bucket? More precisely, what is the expected cardinality of the set {k: h(k) = 1}.

• n/(2m)
• n/m
• m/n
• m/(2n)
• 1/n
• 1/m

Question 3)
Suppose we use a hash function h to hash n distinct keys into an array T of length m. Say that two distinct keys x, y collide under h if h(x) = h(y). Assuming simple uniform hashing — that is, with each key mapped independently and uniformly to a random bucket — what is the probability that a given pair x, y of distinct keys collide?

• 1/(m – 1)
• 1/m
• 1/m2
• 1/n
• 1/n2

Question 4)
Suppose we use a hash function h to hash n distinct keys into an array T of length m. Assuming simple uniform hashing — that is, with each key mapped independently and uniformly to a random bucket — what is the expected number of pairs of distinct keys that collide? (As above, distinct keys x, y are said to collide if h(x) =h(y).)

• n/(n – 1)/2m
• n/m
• n2/m
• n(n –1)/m
• n/m2

Question 5)
To interpret our heuristic analysis of bloom filters in lecture, we considered the case where we were willing to use 8 bits of space per object in the bloom filter. Suppose we were willing to use twice as much space (16 bits per object). What can you say about the corresponding false positive rate, according to our heuristic analysis (assuming that the number k of hash tables is set optimally)? [Choose the strongest true statement.]

• Less than 1%
• Less than 1%
• Less than .01%
• Less than .001%