Answer Happy

Q5: Consider a 2" x 2" chessboard, where n is a non-negative integer (i.e. n ≥ 0). This chessboard has information about pieces on the board. Suppose that we check to see if there's a Black Queen on the board. Here is some psuedo-code for a recursive function called black-queen-check that takes in a 2" × 2n chessboard C with piece information and returns a single truth value True or False as output. function black-queen-check (C) if size (C) == 1x1 if C == {black queen} return True; else return False; else return (black-queen-check (top-left-quad (C)) or black-queen-check (top-right-quad (C)) or black-queen-check (bottom-left-quad (C)) or black-queen-check (bottom-right-quad (C)) ); end function; You should think of size as a "black-box" function that in one step returns the size of its input; similarly, you should think of top-left-quad, etc., as black-box functions that in one step return the appropriate quadrant of the chessboard. [4] (a) For n ≥ 0, let an be the number of computational steps it takes to compute black-queen-check (C) when C is a 2" x 2" chessboard including "applying a function", "checking if two things are equal", computing an "or" statement, and "return"ing a value. Find, with justification, a recursive definition for an. [5] (b) Find an explicit formula for an and use induction to prove it. Hint: You won't have something as tidy/easy to work with as in Section 4.9, but it should be almost as nice; one weird term is going to be okay, since it'll still be explicit.