1. Hashing Functions

Problem: store customer records so they can be retrieved quickly. Each record has a unique key (e.g. Social Security number). A hashing function assigns memory location .

Most common choice:

Why it’s good:

  • Easy to evaluate — just one remainder.
  • Onto (surjective) — every location can be used.

Surjective: for every in the codomain there is at least one with .

Example:

Collisions

is not one-to-one (more keys than locations), so two keys can map to the same place — a collision.

  • → collision at 14.

Linear probing resolves it: use the first free location after the occupied one,

Location 15 is free, so the second record goes to 15.


2. Pseudorandom Numbers

True randomness is very hard to produce; systematic methods produce pseudorandom numbers — fast to generate, but too predictable for some tasks (e.g. security).

Linear congruential method

Choose: modulus , multiplier , increment , seed with

Generate

For numbers in use .

Example: :

n0123456789
3786120453

, so the sequence repeats with period 9: 3, 7, 8, 6, 1, 2, 0, 4, 5, 3, …

Pure multiplicative generator: . Widely used: , — generates numbers before repeating.


3. Check Digits

Append an extra digit computed from the others; on reading, recompute it to detect errors.

3.1 Parity check bits

For bit string :

  • if the number of 1s is even, if odd.
  • Detects an odd number of bit errors; misses an even number of errors.

Example (last bit = parity bit):

  • 01100101: = parity bit ✓ → accept (may still hide an even number of errors).
  • 11010110: ✗ → reject.

3.2 Universal Product Codes (UPC)

12 digits: 1 product category · 5 manufacturer · 5 product · 1 check digit. Valid iff

(odd positions weighted 3, even positions weighted 1).

(a) First 11 digits 79357343104 → ; ⇒ check digit 2.
(b) 041331021641 → ⇒ not valid.

3.3 ISBN-10

10-digit code (language, publisher, book number, check digit). The check digit may be X (= 10).

(ISBN-13 was later introduced for more titles.)

Example — find the check digit of 007288008:
.

Example — validate 084930149X:
⇒ not valid.

3.4 Error detection with ISBN-10

Common errors: single error (one digit wrong) and transposition (two digits swapped). ISBN-10 detects both.

Single error: with , , all other digits equal:

because , and , (11 is prime).

Transposition of unequal digits in positions (, ):

because and .

Why mod 11 works so well: 11 is prime, so a product of two non-multiples of 11 is never . (Whether UPC detects these errors: Exercises 26–27.)