Consider the ab-Search problem, which takes an input string data of length n and
ID: 3872654 • Letter: C
Question
Consider the ab-Search problem, which takes an input string data of length n and identifies the first instance of the substring ab in data (or -1 if data does not contain ab). Formally: Input: data: array of characters Input: n: length of data Output: minimum index i such that datali and data[i + 1] = b, or-1 if no such i exists a In this assignment, you will produce a divide-and-conquer solution for the ab-search problem. While this algorithm is not faster than the brute-force O(n)- time algorithm, it will illustrate how to apply the general design strategy of ivide-and-conquer. 1. If we take an input array data and divide it in half (data 1..mid and datalmid+1..nj, where mid-Ln/2), ab could be in the left half, it could be in the right half, or it could be between the two halves (e.g., when dividing xxabxx in half). Write 2-3 function calls that represent these three cases. 2. What is (are) the base case(s) for ab-searching? 3. Write a divide-and-conquer algorithm that solves the ab-searching prob- lem. Be sure to consider: 1) how you solve the base case, 2) how you construct the solution of the full problem on the basis of the 2-3 recursive calls, and 3) whether your algorithm is correct. Be sure to cover all three cases listed in problem 1, as well as the case where ab is "missing" from dataExplanation / Answer
1. Function calls are
If n < 2 - Return -1
if (ans = search(data[1,mid])) !=-1 return ans
If data[mid] = 'a' and data[mid+1] = 'b', then return mid
return search(data[mid+1],n)
2. Base case is , if the length of the array is less than 2, return -1
3. FUNCTION AB_SEARCH(DATA[])
//This is the base case, if length of the string is less than 2, return -1
IF LENGTH(DATA)<2
RETURN -1
MID = LENGTH(DATA)/2
//Check if ab is found in the left half
ANSL = AB_SEARCH(DATA[1,MID])
//If found in the left half, return the ans
IF ANSL!=-1
RETURN ANSL
//Check if last char of the first half is 'a' and first char of the second half of 'b'. Return mid, if yes
IF DATA[MID]='a' AND DATA[MID+1] = 'b'
RETURN MID
//If pattern not found so far, return the answer obtained from the second half
RETURN AB_SEARCH(DATA[MID+1,N])
4. We are trying to find the pattern ab. First we are looking for the pattern in the first half. After that we are checking if the middle elements form ab pattern, else we are looking in the right half. So, if pattern exists it must be found.