TAOCP 7.1.4 Exercise 223
Working
Section 7.1.4: Binary Decision Diagrams
Exercise 223. [28] [28] A “median word” is a five-letter word µ = µ1 . . . µ5 that can be obtained from three words α = α1 . . . α5, β = β1 . . . β5, γ = γ1 . . . γ5 by the rule [αi = µi] + [βi = µi] + [γi = µi] = 2 for 1 ≤i ≤5. For example, mixed is a median of the words {fixed, mixer, mound}, and also of {mated, mixup, nixed}. But noted is not a median of {notes, voted, naked}, because each of those words has e in position 4. a) Show that {d(α, µ), d(β, µ), d(γ, µ)} is either {1, 1, 3} or {1, 2, 2} whenever µ is a median of {α, β, γ}. (Here d denotes Hamming distance.) b) How many medians can be obtained from WORDS(n), when n = 100? 1000? 5757? c) How many of those medians belong to WORDS(m), when m = 100? 1000? 5757?
Verified: no
Solve time: 1m40s
Working