Use Psuedocode: Algorithm Design: Recursive Divide & Conquer Turn the recursive
ID: 3890476 • 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
Character-Count-Recursive(arr[l,r] char, X char)
//If the only character in the array is X, return 1, else return 0
if(len(arr)==1)
if(arr[0]==X)
return 1
return 0
//Calculate the mid
mid = (l+r)/2
//Invoke the method for the two subarrays
return Character-Count-Recursive(arr[l,mid], X)+ Character-Count-Recursive(arr[mid+1,r], X)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.