s
Section 5.6 The Mighty Mod Function
441
4. Prove that for any integers x and y,
(x + y) mod n = (x mod n + y mod n) mod n
5. 486 = 18 # 27. Show by computing each expression that
486 mod 5 = (18 mod 5 # 27 mod 5) mod 5
6 7067 = 191 # 37. Show by computing each expression that
7067 mod 8 = (191 mod 8 # 37 mod 8) mod 8
7. Prove that for any integers x and y,
(x # y) mod n = (x mod n # y mod n) mod n
8. Prove or disprove: For any positive integer x, (−x) mod n = −(x mod n).
9. Using the hash function of Example 51, which of the following Social Security numbers would cause a
collision with 328356770, the Social Security number of that example?
a. 060357896
b. 896137243
c. 712478993
d. 659027781
10. Find a set of five numbers in the range 30, 2004 that cause 100% collision using the hash function
h(x) = x mod 13
11. Using a hash table of size 11 and the hash function x mod 11, show the results of hashing the following
values into a hash table using linear probing for collision resolution:
1, 13, 12, 34, 38, 33, 27, 22
12. Using the completed hash table from Exercise 11, compute the average number of comparisons needed to
perform a successful search for a value in the table.
13. When a computer program is compiled, the compiler builds a symbol table for storing information about
the identifiers used in the program. A scheme is needed to quickly decide whether a given identifier has
already been stored in the table and, if not, to store the new identifier. A hash function is often used to
locate a position in the table at which to store information about an item.
For simplicity, assume that the items to be stored are integers, that the hash table can hold 17 items in
positions 0–16, and that the hash function h(x) is given by h(x) = x mod 17.
Linear probing is used for collision resolution.
a. Using the hash function and collision resolution scheme described, store the sequence of values 23, 14,
52, 40, 24, 18, 33, 58, 50. Give the location in the table at which each is stored.
b. After the table of part (a) has been filled, describe the process to search for 58 in the table. Describe the
process to search (unsuccessfully) for 41 in the table.
Section 5.6 The Mighty Mod Function
441
4. Prove that for any integers x and y,
(x + y) mod n = (x mod n + y mod n) mod n
5. 486 = 18 # 27. Show by computing each expression that
486 mod 5 = (18 mod 5 # 27 mod 5) mod 5
6 7067 = 191 # 37. Show by computing each expression that
7067 mod 8 = (191 mod 8 # 37 mod 8) mod 8
7. Prove that for any integers x and y,
(x # y) mod n = (x mod n # y mod n) mod n
8. Prove or disprove: For any positive integer x, (−x) mod n = −(x mod n).
9. Using the hash function of Example 51, which of the following Social Security numbers would cause a
collision with 328356770, the Social Security number of that example?
a. 060357896
b. 896137243
c. 712478993
d. 659027781
10. Find a set of five numbers in the range 30, 2004 that cause 100% collision using the hash function
h(x) = x mod 13
11. Using a hash table of size 11 and the hash function x mod 11, show the results of hashing the following
values into a hash table using linear probing for collision resolution:
1, 13, 12, 34, 38, 33, 27, 22
12. Using the completed hash table from Exercise 11, compute the average number of comparisons needed to
perform a successful search for a value in the table.
13. When a computer program is compiled, the compiler builds a symbol table for storing information about
the identifiers used in the program. A scheme is needed to quickly decide whether a given identifier has
already been stored in the table and, if not, to store the new identifier. A hash function is often used to
locate a position in the table at which to store information about an item.
For simplicity, assume that the items to be stored are integers, that the hash table can hold 17 items in
positions 0–16, and that the hash function h(x) is given by h(x) = x mod 17.
Linear probing is used for collision resolution.
a. Using the hash function and collision resolution scheme described, store the sequence of values 23, 14,
52, 40, 24, 18, 33, 58, 50. Give the location in the table at which each is stored.
b. After the table of part (a) has been filled, describe the process to search for 58 in the table. Describe the
process to search (unsuccessfully) for 41 in the table.