4. (20 points) a. (5 points) A binary expression of a nonnegative integer n is defined to be a sequence (bo, b1, . . , bk) such that each b {0, 1} and -2'bs-i- k n = i=0 Thus, for example, 19 has the binary expression (1,0,0,1,1). Use strong induction to prove that every nonnegative integer n has a binary expression. b. (5 points) You are given a function qln,d) which returns the integer part of the quotient (from the division theorem) when n is divided by d; you are also given a function ISEVEN(m) which returns TRUE if the integer argument m is even, and False if it's odd. The algorithm below is supposed to return a binary expression of a nonnegative integer n given in decimal form. Modify it so that the result has no leading zeros, 4 and fill in what is missing. If you find anything wrong with the algorithm, fix it. Your solution should be a full, written-out algorithm. Give a convincing explanation of why your algorithm returns a binary expression of n. The binary form of n 2: 1: function BINARY(n) Returns a sequence (bo, ..., bk) that is a binary expression of n if IsEven(n) then return BINARY(q(n, 2)) e (0) else if ISEVEN(n) then is concatenation 3: you fill this in 4: else if n=0 then you fill this in 5: end if 6: end function c. (10 points) Prove that the number of calls to BINARY made by this algorithm is at most C log2 n + C2, for some particular C1, C2 > 0 that you tell us. (Your bound does not have to be the best possible, but it must be correct.) We suggest using strong induction