Question

Answer the following questions about the algorithm below, which searches an input string for the substring "ab" and returns where "ab" first appears, or -1 if "ab is not in the string. Note that ] is the floor operator, which rounds its input down to the nearest integer Input: str: a string of length n Input: n the length of str Output: the first index i such that stria and strib, or -1 if str doesn't contain the substring "ab" 1 Algorithm: abSearch 2 if n< 2 then 3return -1 4 else if n 2 then if str= "ab" then 6 return 1 7 else return-1 9end 10 else | midpt=ln/2] 11 12left-abSearch(str[1..midpt]) 13 | center = abSearch(str[midpt..midpt + 11) 14right- abSearch(str[midpt 1..n]) 15if left t-1 then 16 17else if center -1 then 18 19else if right -1 then 20 21 return left return midpt return right +midpt return-1 else 23 24 end

2. Prove that abSearch returns ?1 if str does not contain “ab” as a substring. You may omit the base case for this proof (done in problem 1). Hint: you will need to think carefully about the different cases of the if statement in lines 15–23 to show that abSearch always returns ?1 when str doesn’t contain “ab.”

Answer 1

Solution Weat ohcetunst doesnot Con tuh ab as a sustin b bba #cte neu (lengtんof-the stin! ) Na) let us apply Hufs algonithm to he 2 1 2 34 δ) elx part un" be excuted lept -ab Seasch 2 3 abeac unctior tl ot 2, and check F nc2 again 2

ineut be executa d elx to enlo ไก่ห be enreutad I teun but we got fe So eex uill be eeutad Cente So elx be enuculad rng ut go

-1 tiene is obtained stlu' u Help