442
Relations, Functions, and Matrices
14. Explain what problem can arise if an item stored in a hash table is later deleted.
15. A disadvantage of hashing with linear probing for collision resolution is that elements begin to cluster
together in groups of adjacent array locations. Assume that you have a very good hashing function (it distributes elements evenly throughout the hash table). Start with an empty hash table of size t that will store
data using linear probing for collision resolution.
a. What is the probability of hashing the first element to location p (and storing it there, since it is the first
item and there will be no collisions)?
b. Once location p is occupied, what is the probability of storing the second item in location p + 1
(modulo the table size)?
c. Once locations p and p + 1 are occupied, what is the probability of storing the third item in location
p + 2 (modulo the table size)?
16. Generalize the answers to Exercise 15 to explain why using linear probing for collision resolution causes
clustering.
17. Decode the following ciphertext messages that were encoded using a Caesar cipher with the given key.
a. JUUBFNUUCQJCNWMBFNUU, k = 9
b. XAEWFVMPPMKERHXLIWPMXLCXSZIWHMHKCVIERHKMQFPIMRXLIAEFI, k = 4
c. IURSAYZGXJCOZNZNKQTOLKOTZNKROHXGXE, k = 6
18. Using a Caesar cipher, encode the following plaintext messages.
a. ATTACK FROM BEYOND THE RIVER, k = 5
b. WE ARE SHORT OF SUPPLIES, k = 10
c. BADLY NEED AMMUNITION, k = 8
19. The following ciphertext message is intercepted; you suspect it is a Caesar cipher. Find a value of k that
decodes the message, and give the corresponding plaintext.
BUNNYWXFFNVJALQXWAXVNCXVXAAXF
20. The following ciphertext message is intercepted; you suspect it is a Caesar cipher. Find a value of k that
decodes the message, and give the corresponding plaintext.
EQQKAGAZRMOQNAAWPGPQ
21. Use the algorithm of Example 53 to compute the 1-bit circular left shift of the following binary strings
(write the bit strings for x, p, q, and so on).
a. 10011
b. 0011
22. Use the algorithm of Example 53 to compute the 1-bit circular left shift of the following binary strings
(write the bit strings for x, p, q, etc.).
a. 10110
b. 1110
23. Consider a “short form” of DES that uses 16-bit keys. Given the 16-bit key
1101000101110101
as input to a DES round that uses a circular left shift of 2 bits, what would be the key for the next round?
Relations, Functions, and Matrices
14. Explain what problem can arise if an item stored in a hash table is later deleted.
15. A disadvantage of hashing with linear probing for collision resolution is that elements begin to cluster
together in groups of adjacent array locations. Assume that you have a very good hashing function (it distributes elements evenly throughout the hash table). Start with an empty hash table of size t that will store
data using linear probing for collision resolution.
a. What is the probability of hashing the first element to location p (and storing it there, since it is the first
item and there will be no collisions)?
b. Once location p is occupied, what is the probability of storing the second item in location p + 1
(modulo the table size)?
c. Once locations p and p + 1 are occupied, what is the probability of storing the third item in location
p + 2 (modulo the table size)?
16. Generalize the answers to Exercise 15 to explain why using linear probing for collision resolution causes
clustering.
17. Decode the following ciphertext messages that were encoded using a Caesar cipher with the given key.
a. JUUBFNUUCQJCNWMBFNUU, k = 9
b. XAEWFVMPPMKERHXLIWPMXLCXSZIWHMHKCVIERHKMQFPIMRXLIAEFI, k = 4
c. IURSAYZGXJCOZNZNKQTOLKOTZNKROHXGXE, k = 6
18. Using a Caesar cipher, encode the following plaintext messages.
a. ATTACK FROM BEYOND THE RIVER, k = 5
b. WE ARE SHORT OF SUPPLIES, k = 10
c. BADLY NEED AMMUNITION, k = 8
19. The following ciphertext message is intercepted; you suspect it is a Caesar cipher. Find a value of k that
decodes the message, and give the corresponding plaintext.
BUNNYWXFFNVJALQXWAXVNCXVXAAXF
20. The following ciphertext message is intercepted; you suspect it is a Caesar cipher. Find a value of k that
decodes the message, and give the corresponding plaintext.
EQQKAGAZRMOQNAAWPGPQ
21. Use the algorithm of Example 53 to compute the 1-bit circular left shift of the following binary strings
(write the bit strings for x, p, q, and so on).
a. 10011
b. 0011
22. Use the algorithm of Example 53 to compute the 1-bit circular left shift of the following binary strings
(write the bit strings for x, p, q, etc.).
a. 10110
b. 1110
23. Consider a “short form” of DES that uses 16-bit keys. Given the 16-bit key
1101000101110101
as input to a DES round that uses a circular left shift of 2 bits, what would be the key for the next round?