1. What would be the base case(s) when proving that abSearch is correct? Prove that abSearch is correct for the base case(s).

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 1523 to show that abSearch always returns ?1 when str doesnt contain ab.

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