t n be a positive integer. We are given as input two words n and 2. of the same

Question

t n be a positive integer. We are given as input two words n and 2. of the same length n. We want to create a word of length 2n that comes from alternating the letters of each word, starting with the first word. For example, on an input of hello, world the algorithm should produce the output hweolrillod. Here is a recursive algorithm to solve this problem. procedure RecAlternate(s12n . . Un) 1, if n = 1 then 2. return s u 3. result := RecAlternate(s182 . . . sn-1, u1u2 . . .un-1) 4. Append sn to the end of result. 5. Append un to the end of result. 6. return result a) Prove the Correctness of the algorithm (use induction on n)

Explanation / Answer

1.
We shall verify the algo using method of induction

for n = 1,
return s1u1 is correct

for n =2
RecAlternate(s1s2, u1u2)
       +----RecAlternate(s1, u1) --> result= s1u1
          result = s1u1s2 (append sn)
          result = s1u1s2u2 (append un)
hence the algorithm is also true for n = 2

let us consider that the algorithm is true for n = m, so
   RecAlternate(s1s2...sm, u1u2...um) --> s1u1s2u2s3u3...smum (asumtion)

we shall verify if the algo still holds on n = m+1,

RecAlternate(s1s2...smsm+1, u1u2...umum+1)
       +----RecAlternate(s1s2...um, u1u2...um) --> result= s1u1s2u2s3u3...smum
          result = s1u1s2 (append sn) // result <- s1u1s2u2s3u3...smumsm+1
          result = s1u1s2u2 (append un) // result <- s1u1s2u2s3u3...smumsm+1um+1

So we have proved by induction that this algorithm holds

b
exactruntime:

   operation:
   T(1) = 2
           T(n) = T(n-1) + 1 + 1
                 = T(n-2) + 2 + 1 + 1
                ...
       = T(n-i) + 2*i
                ...
               = 2*n

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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