Hashing Checksums Quiz: Applications in Coding – Hashing, Checksums, and Cyclic Redundancy

A checksum is computed from the data before transmission and sent alongside it. When the receiver gets the data, it recomputes the checksum and compares it to the received value. If the two values differ, an error occurred during transmission. Checksums do not compress, encrypt, or reduce data size. Their sole purpose is integrity verification through error detection.

The checksum equals 9999 % 256. The largest multiple of 256 that does not exceed 9999 is 256 multiplied by 39 equals 9984. Subtracting gives 9999 minus 9984 equals 15. So the checksum is 15. This value fits within a single byte since it is less than 256, which is the purpose of applying modulus 256 in byte-oriented checksum schemes.

The answer is True. In CRC verification, the receiver divides the entire received frame including the appended CRC bits by the same generator polynomial. If the remainder is 0, the data is considered intact. A non-zero remainder indicates corruption. This is probabilistic rather than absolute, since two complementary error patterns could theoretically cancel out, but this is extremely unlikely with well-chosen generator polynomials.

Substituting x equals 9: 5 multiplied by 9 plus 3 equals 48. Then 48 % 11: 11 multiplied by 4 equals 44; 48 minus 44 equals 4. So hash(9) equals 4. This linear hash function of the form (ax + b) % m is common in introductory implementations. The modulus 11 is a prime number, which tends to produce more uniform index distributions than non-prime table sizes.

Two keys collide when they map to the same hash index. Checking option A: 13 % 8 equals 5 and 21 % 8 equals 5. Both map to index 5, confirming a collision. Checking option B: 9 % 8 equals 1 and 18 % 8 equals 2 — no collision. Checking option C: 7 % 8 equals 7 and 18 % 8 equals 2 — no collision. Checking option D: 4 % 8 equals 4 and 13 % 8 equals 5 — no collision. Only option A produces a collision.

Option A is correct: a collision is by definition two distinct keys mapping to the same index. Option B is correct: a larger table reduces collision probability by spreading keys across more buckets, but as long as the key space exceeds the table size, collisions remain possible. Option C is incorrect: a prime modulus reduces clustering and improves distribution, but it does not guarantee zero collisions when more keys than buckets exist. Option D is correct: whenever keys can outnumber buckets, some keys must share a bucket and collision resolution is required.

The total byte sum is 5 multiplied by 255 equals 1275. The checksum is 1275 % 256. The largest multiple of 256 not exceeding 1275 is 256 multiplied by 4 equals 1024. Subtracting gives 1275 minus 1024 equals 251. So the checksum is 251. This result is close to 255 because five bytes of maximum value leave only a small remainder when reduced modulo 256.

The answer is False. A perfect hash function is one that produces no collisions for a specific, predetermined set of keys. It is designed and optimised for that particular key set only. When applied to keys outside that set, a perfect hash function may still produce collisions. Perfect hashing is a technique used when the complete set of keys is known in advance, such as in compiler keyword tables or static lookup structures.

The total byte sum is 200 plus 150 plus 100 plus 50 equals 500. The checksum is 500 % 256. The largest multiple of 256 not exceeding 500 is 256 multiplied by 1 equals 256. Subtracting gives 500 minus 256 equals 244. So the checksum is 244. This value is transmitted alongside the data so the receiver can verify integrity by recomputing the same operation.

The checksum equals 4096 % 255. The largest multiple of 255 not exceeding 4096 is 255 multiplied by 16 equals 4080. Subtracting gives 4096 minus 4080 equals 16. So the checksum is 16. Note that modulus 255 rather than 256 is occasionally used in specific protocol designs. The computation is the same: find the remainder after dividing by the chosen modulus.

Substituting x equals 5: 7 multiplied by 5 plus 2 equals 35 plus 2 equals 37. Then 37 % 13: 13 multiplied by 2 equals 26; 37 minus 26 equals 11. So hash(5) equals 11. The modulus 13 is prime, which helps distribute keys uniformly across the table. The expression 7x plus 2 is a linear probe function that shifts and scales the key before reducing it modulo the table size.

Computing 1000 % 97: the largest multiple of 97 not exceeding 1000 is 97 multiplied by 10 equals 970. Subtracting gives 1000 minus 970 equals 30. So h(1000) equals 30. The number 97 is prime, which is a deliberate choice in the division method. Using a prime table size reduces the clustering of keys and produces a more uniform distribution than composite table sizes.

The answer is True. CRC uses a fixed-length remainder, so by the pigeonhole principle, different messages can produce the same CRC value. However, the probability of an undetected error is extremely low with well-chosen generator polynomials. A 32-bit CRC, for example, has a collision probability of approximately 1 in 4 billion for random errors, making it highly reliable in practice while not being mathematically absolute.

Computing step by step: 0x4A XOR 0x2F. In binary: 01001010 XOR 00101111 equals 01100101, which is 0x65. Then 0x65 XOR 0x11: 01100101 XOR 00010001 equals 01110100, which is 0x74. So the XOR checksum is 0x74. XOR-based checksums are fast to compute and have the useful property that XORing the checksum back into the result produces 0 if no errors occurred.

Option A is correct: (15 x 8) % 7 = 120 % 7 = 1, and (1 x 1) % 7 = 1 — both paths give 1. Option B is correct: (12 x 10) % 6 = 120 % 6 = 0, and (0 x 4) % 6 = 0 — both paths give 0. Option C is incorrect: the final % m step is mandatory. Without it, (A % m) multiplied by (B % m) could exceed m, giving a wrong result. Option D is correct: this property is used in hash computation and cryptography to avoid computing enormous intermediate products.

Split the 16-bit binary number into 4-bit groups from left to right: 1010, 1111, 0011, 0101. Converting each group: 1010 equals A, 1111 equals F, 0011 equals 3, 0101 equals 5. Concatenating gives AF35. This conversion is directly relevant to CRC and checksum work, where remainders are often expressed in hexadecimal for compactness.

The load factor of a hash table is defined as the number of stored keys divided by the total number of buckets. Here that is 75 divided by 100 equals 0.75. The load factor is a key performance metric: a low load factor means few collisions but wasted memory, while a high load factor means better memory usage but more collisions. Most implementations resize the table when the load factor exceeds a threshold such as 0.7 or 0.75.

The answer is False. Increasing table size reduces the load factor and lowers the probability of collisions, but it cannot eliminate them entirely unless the table is at least as large as the entire key space. Since the key space in most applications is enormous (for example all possible strings), a hash table large enough to avoid all collisions is impractical. Collision resolution strategies such as chaining or open addressing are always necessary in real implementations.

Using the modular multiplication property: (15 multiplied by 8) % 7 equals ((15 % 7) multiplied by (8 % 7)) % 7. Computing each remainder: 15 % 7 equals 1 (since 7 multiplied by 2 equals 14 and 15 minus 14 equals 1), and 8 % 7 equals 1 (since 7 multiplied by 1 equals 7 and 8 minus 7 equals 1). So (1 multiplied by 1) % 7 equals 1. Confirming directly: 15 multiplied by 8 equals 120; 120 % 7 equals 1 since 7 multiplied by 17 equals 119 and 120 minus 119 equals 1.

The largest multiple of 17 that does not exceed 5432 is 17 multiplied by 319 equals 5423. Subtracting gives 5432 minus 5423 equals 9. So 5432 % 17 equals 9. In hash computation, reducing a large key value by a prime modulus such as 17 helps distribute keys more uniformly across hash table buckets compared to non-prime moduli.