The Hamming distance between two strings of equal length is defined as the numbe

Question

The Hamming distance between two strings of equal length is defined as the
number of positions at which the corresponding symbols are different. It is
named after Richard Hamming (19151998), a prominent American scientist
and engineer, who introduced it in his seminal paper on error-detecting and
error-correcting codes.

a. What is the time efficiency class of the brute-force algorithm for the closestpair
problem if the points in question are strings of m symbols long and the
distance between two of them is measured by the Hamming distance?

Explanation / Answer

(a)

Solution:

Consider two axioms from metric it will satisfy the Hamming distance.

In the case of triangle inequality need to prove.

These can be derived from the mathematical induction on the string length m.

If m = 1 , the inequality dH (S1,S2) dH (S1,S3) + dH (S3,S2) holds for any one character strings S1,S2, and S3.

For the process of mathematical inductive step, need to assume the triangle inequality holds for any three strings of length m.

Consider the three arbitrary strings Si = Si`ci where i =1, 2, 3

Here Si`are strings of length m and ci’s are their last characters.

dH (S1,S2) = dH (S1`,S2`) + dH (c1,c2)

                dH (S1`,S3`) + dH (S3`,S2`) + dH (c1,c3) + dH (c3,c2)

            = [dH (S1`,S3`) + dH (c1,c3)] + [dH (S3`,S2`) + dH (c3,c2)]

               = dH (S1, S3) + dH (S3,S2)     

Hence it is proved.

Thus the satisfied condition for Hamming distance is dH (S1,S2) = dH (S1,S3) + dH (S3,S2)

(b)

From the concept of brute force algorithm’s basic operation is comparing the two characters in the string of length is m.

The worst case time efficiency of brute force algorithm is (mn2)

Thus the efficiency of brute force algorithm is (mn2)

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.