Consider the ab-Search problem, which takes an input string data of length n and

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 data

Explanation / 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.
   

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

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