For this question answer individual parts. A bit string s is like any other stri

Question

For this question answer individual parts. A bit string s is like any other string except it only has 0’s and 1’s. It is a string of binary numbers. procedure mystery(w: bit string) {A bit string is a string of 0’s and 1’s} n := length(w) if n <= 1 then return w

else return substr(w, n, n)mystery(substr(w, 1, n -1)) {substr(w, a, b) is the substring of w consisting of the bits in the ath through bth positions}

(a) Read the above code and write the output when mystery(1100101) is called? Trace the algorithm and show the result. Answer:

(b) State simply what this algorithm does and the prove that the above recursive algorithm is correct. Answer:

Explanation / Answer

Algorithm:

procedure mystery(w: bit string)

{A bit string is a string of 0’s and 1’s}

n := length(w)

if n <= 1

       then return w

else

       return substr(w, n, n)mystery(substr(w, 1, n -1))

Now, mystery(1100101) is called

n=7 so if condition is false in else

return substr(1100101,7,7)mystry(substr(1100101,1,n-1))

substr(1100101,7,7) will be 1

and substr(1100101,1,n-1)=110010 so mystry(1100101)

This process will continue using n=1

Final result will be 1010011

b) This algorithm is reversing the string.i.e. 1100101 to 1010011.This algoritm is correct because every time it run nth element is returned from string which will eventually reverse the string.

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

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