Use Psuedocode: Algorithm Design: Recursive Divide & Conquer Turn the recursive
ID: 3890698 • Letter: U
Question
Use Psuedocode:
Algorithm Design: Recursive Divide & Conquer
Turn the recursive divide & conquer strategy below to compute the total number of occurrences of a given character in a string of length zero or more represented as a character array into a recursive divide & conquer algorithm. The algorithm’s header is provided; complete the rest.
“The number of occurrences of character X in string S is the sum of the number of occurrences of character X in the left half of string S and the number of occurrences of character X in the right half of string S”
Character-Count-Recursive(S: array [p..r] of char, X: char)
Explanation / Answer
Following is the required algorithm, which divides an array if starting and end index are not same into two parts and run recursively. If starting and ending index are same, which means subarray is of size 1 then it checks whether the subarray contains X or not and return 1 or zero accordingly.
Character-Count_Recursive(S[p,r],X)
{
if p==r: //starting index is same as end index, subarray is of size 1
if S[p]==X:
return 1
else:
return 0
endif
endif
mid = (p+r)/2
return (Character-Count_Recursive(S[p,mid],X)+Character-Count_Recursive(S[mid+1,r],X))
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.