CS 6515 EXAM 2 REVIEW SHEET COMPLETE QUESTIONS ANSWERS GRADED A PLUS
Question:
average case for a string table.
Answer:
The average case is Theta 1 because the running time for the average case is dependent on the load
factor, which in this case is assumed to be constant
Question:
code for adding the string table into the cloud.
Answer:
do one for loop going thru the indexes of the array, then for each loop going thru each record in b[i].
then call insert for other record but use the new number of buckets for to index
Question:
run time to get everything from a table into a cloud.
Answer:
The running time would be Theta n because under the assumption of simple uniform hashing, the
elements are evenly distributed so there would be an even distribution among each list. This means
the length of the lists are insignificant in comparison to the total number of elements, so the find
method would take constant time (and therefore insert and remove are also constant because they
use find). But, we call the insert n times for the n number of elements to be inserted into the table, so
the running time would be n.
Question:
when to allocate a new table for the cloud.
Answer:
, We would allocate a new table once the load factor becomes greater than L.
Question:
size of the table when it runs out of space in cloud.
Answer:
double the size
Question:
purpose of hashcode generation.
Answer:
-map integers in some range object that are equal() must have the same hashcode objects that are
notEqual() should have distinct hashcodes (but this might not be possible bc of pigeonhole
principle)
Question:
should hash codes be spread uniformly across range w/o obvious correlations?
Answer:
2 arguments: no 2nd step (index generation) is responsible for ensuring unequal hash codes mapped
to uniform uncorrelated indices yes index generator is not responsible for fixing bad hashcode
generator. even if index generator scrambles hashcode, if universe is much greater than # of possible
hashcodes, there is a greater likelihood that the objects map to the same hashcode. gonna have
collisions so bucket might not help
Question:
hashcodes for 32 bit integers.
Answer:
use unchanged
Question:
average case for a string table.
Answer:
The average case is Theta 1 because the running time for the average case is dependent on the load
factor, which in this case is assumed to be constant
Question:
code for adding the string table into the cloud.
Answer:
do one for loop going thru the indexes of the array, then for each loop going thru each record in b[i].
then call insert for other record but use the new number of buckets for to index
Question:
run time to get everything from a table into a cloud.
Answer:
The running time would be Theta n because under the assumption of simple uniform hashing, the
elements are evenly distributed so there would be an even distribution among each list. This means
the length of the lists are insignificant in comparison to the total number of elements, so the find
method would take constant time (and therefore insert and remove are also constant because they
use find). But, we call the insert n times for the n number of elements to be inserted into the table, so
the running time would be n.
Question:
when to allocate a new table for the cloud.
Answer:
, We would allocate a new table once the load factor becomes greater than L.
Question:
size of the table when it runs out of space in cloud.
Answer:
double the size
Question:
purpose of hashcode generation.
Answer:
-map integers in some range object that are equal() must have the same hashcode objects that are
notEqual() should have distinct hashcodes (but this might not be possible bc of pigeonhole
principle)
Question:
should hash codes be spread uniformly across range w/o obvious correlations?
Answer:
2 arguments: no 2nd step (index generation) is responsible for ensuring unequal hash codes mapped
to uniform uncorrelated indices yes index generator is not responsible for fixing bad hashcode
generator. even if index generator scrambles hashcode, if universe is much greater than # of possible
hashcodes, there is a greater likelihood that the objects map to the same hashcode. gonna have
collisions so bucket might not help
Question:
hashcodes for 32 bit integers.
Answer:
use unchanged
