CS6515 EXAM 2 PRACTICE TEST 2026
QUESTIONS WITH SOLUTIONS GRADED A+
⩥ 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)
⩥ 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
,⩥ 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
⩥ 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
⩥ fixed point decimal. Answer: do the multiplication but then divide by
a base of 10
⩥ what is worrisome about hashpoints. Answer: if there are duplicates
⩥ hashpoints equality. Answer: where both x and y are equal for both
points
⩥ how to map hashpoints to codes. Answer: 31*x + y (some points will
have the same hashcode though)
, ⩥ simplest possible hashcodes where 2 have the same code. Answer:
x+y
⩥ 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
⩥ less uniform distribution for hashing. Answer: smaller # of bins some
values of m might be better than others (kind of depends bc of mod)
⩥ 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
⩥ knuth's constant. Answer: 1737350767
⩥ A x h vs. h' x a if h = h' mod m. Answer: a x h is smaller than h' x a
⩥ difference between size and nBuckets. Answer: size is the number of
elements in the list
QUESTIONS WITH SOLUTIONS GRADED A+
⩥ 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)
⩥ 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
,⩥ 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
⩥ 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
⩥ fixed point decimal. Answer: do the multiplication but then divide by
a base of 10
⩥ what is worrisome about hashpoints. Answer: if there are duplicates
⩥ hashpoints equality. Answer: where both x and y are equal for both
points
⩥ how to map hashpoints to codes. Answer: 31*x + y (some points will
have the same hashcode though)
, ⩥ simplest possible hashcodes where 2 have the same code. Answer:
x+y
⩥ 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
⩥ less uniform distribution for hashing. Answer: smaller # of bins some
values of m might be better than others (kind of depends bc of mod)
⩥ 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
⩥ knuth's constant. Answer: 1737350767
⩥ A x h vs. h' x a if h = h' mod m. Answer: a x h is smaller than h' x a
⩥ difference between size and nBuckets. Answer: size is the number of
elements in the list
