Answer can also be NONE

26: S is a set of strings over the alphabet (a, b) and is defined recursively as follows: Basis: ES and bEs Recursive rules: Ifx is in S, then bxa ES and axb S Define the function NumB(x) to be the number of occurrences of the character b in the string x and NumAx) to be the number of occurmences of the character a in the stringx. For example, NumB(bba,-2 and Num Abba)-1 Page 6 of 9 HW-6 Suppose that xes. Select the fact that must be true about x. a. NumB(x) NumA(x)+1 b. NumB(x) NumA) d. O S NumA(x) - NumB(x) s1 8.10 Recursive algorithms 27: The function SuperPower given below receives two inputs, x and n, and should return xa x is a real number and n is positive integer SuperPower(x, n) tf n = 1, then Retum(x2) y SuperPowerx, n-1) Return() What is the correct value for the algorithm to return? 28: The function ComputeSum receives a positive integer n as the input and retums the value Compute Sumn)--+2)2 ComputeSum(n) If n = 1, then Retum(3) Return(?) What is the correct value for the algorithm to return? b. y n ?. (y+2)?2 d. y (n+2)n 8.11 Induction and recursive algorithms 29: The function SuperPower receives two nputs, x and n, and should returne .x is a real number and n is positive integer SuperPower(x, n) If n 1, then Retux) y:# SuperPower(x, n-1) Return() Page 7 of 9 HW-6 The correctness of algonithm SuperPower(x, n) is proven by induction on n. What would be proven in the base case? a. SuperPower(O, n) returms 0 b. SuperPower(1, n) returns C. SuperPower(x, 0) retums x d. SuperPowerx, 1) retums 1