CS 6515 EXAM 2 TEST BANK SOLVED QUESTIONS 100 PERCENT CORRECT ANSWERS
Question:
multiplicative hashing.
Answer:
-b(c) = the floor of ((C*A )mod 1.0) * m mod 1.0 is the fractional part of x so 47.2465 mod 1.0 is
0.2465 CA mod 1.0 is in [0,1) so b(c) is an integer in [0,m) an index. floor is the next lowest integer
so an integer between 0 to 1 gets mapped to 0 to m initial observations: A should not be too small
because then too many hashcodes would be mapped to 0. suggest picking from [0.5,1) if q= CA mod
1.0 is distributed uniformly in [0,1) then we can use any value for m and still get uniform indices
(we could use m=2^v if we want)
Question:
why is multiplication a good strategy?
Answer:
-mapping c-> q = CA mod 1.0 is a diffusing operation i.e. most significant digits of q depend in a
complex way on many digits of c (makes q look uniform, obscures correlations among c's) hence
bin # floor of q * m looks uniform, uncorrelated w c. same is true if we replace digits by bits and
work in binary
Question:
diffusion.
Answer:
if you multiply two long decimals together, you have to add placeholders and stuff. and then the
only digit where none of them have 0s is the digit right after the decimal (bc further right is
placeholder 0 and left could be initial 0). these digits determine the bin number
Question:
,is every choice of A for multiplication equally good?
Answer:
-not all A's have equally good diffusion/complexity properties fractions w few nonzero digits (0.75)
or repeating decimals have poor diffusion and or low complexity advice: pick an irrational # btwn
0.5 and 1 ex. root 5 - 1 over 2 (0.618033998.) knuth
Question:
fixed point decimal.
Answer:
do the multiplication but then divide by a base of 10
Question:
what is worrisome about hashpoints.
Answer:
if there are duplicates
Question:
hashpoints equality.
Answer:
where both x and y are equal for both points
Question:
how to map hashpoints to codes.
Answer:
31*x + y (some points will have the same hashcode though)
Question:
, simplest possible hashcodes where 2 have the same code.
Answer:
x+y
Question:
how many bits to represent colors.
Answer:
256 options so that is 2^8 so 8 bits for each colors * 4 colors = 32 bits every color is realizable, there
are about the same number of hashcodes in the same bin for the 32 bins. deviations are small.
because one long bin and one smaller bin which is faster in the smaller bin
Question:
less uniform distribution for hashing.
Answer:
smaller # of bins some values of m might be better than others (kind of depends bc of mod)
Question:
are powers of 2 good for hashcode.
Answer:
no because the mod 32 shifts the bits over and then the 2 will basically move it back so the hashcode
will do nothing
Question:
knuth's constant.
Answer:
1737350767
Question:
multiplicative hashing.
Answer:
-b(c) = the floor of ((C*A )mod 1.0) * m mod 1.0 is the fractional part of x so 47.2465 mod 1.0 is
0.2465 CA mod 1.0 is in [0,1) so b(c) is an integer in [0,m) an index. floor is the next lowest integer
so an integer between 0 to 1 gets mapped to 0 to m initial observations: A should not be too small
because then too many hashcodes would be mapped to 0. suggest picking from [0.5,1) if q= CA mod
1.0 is distributed uniformly in [0,1) then we can use any value for m and still get uniform indices
(we could use m=2^v if we want)
Question:
why is multiplication a good strategy?
Answer:
-mapping c-> q = CA mod 1.0 is a diffusing operation i.e. most significant digits of q depend in a
complex way on many digits of c (makes q look uniform, obscures correlations among c's) hence
bin # floor of q * m looks uniform, uncorrelated w c. same is true if we replace digits by bits and
work in binary
Question:
diffusion.
Answer:
if you multiply two long decimals together, you have to add placeholders and stuff. and then the
only digit where none of them have 0s is the digit right after the decimal (bc further right is
placeholder 0 and left could be initial 0). these digits determine the bin number
Question:
,is every choice of A for multiplication equally good?
Answer:
-not all A's have equally good diffusion/complexity properties fractions w few nonzero digits (0.75)
or repeating decimals have poor diffusion and or low complexity advice: pick an irrational # btwn
0.5 and 1 ex. root 5 - 1 over 2 (0.618033998.) knuth
Question:
fixed point decimal.
Answer:
do the multiplication but then divide by a base of 10
Question:
what is worrisome about hashpoints.
Answer:
if there are duplicates
Question:
hashpoints equality.
Answer:
where both x and y are equal for both points
Question:
how to map hashpoints to codes.
Answer:
31*x + y (some points will have the same hashcode though)
Question:
, simplest possible hashcodes where 2 have the same code.
Answer:
x+y
Question:
how many bits to represent colors.
Answer:
256 options so that is 2^8 so 8 bits for each colors * 4 colors = 32 bits every color is realizable, there
are about the same number of hashcodes in the same bin for the 32 bins. deviations are small.
because one long bin and one smaller bin which is faster in the smaller bin
Question:
less uniform distribution for hashing.
Answer:
smaller # of bins some values of m might be better than others (kind of depends bc of mod)
Question:
are powers of 2 good for hashcode.
Answer:
no because the mod 32 shifts the bits over and then the 2 will basically move it back so the hashcode
will do nothing
Question:
knuth's constant.
Answer:
1737350767
