Search for question
Question

Problem 2 (9 pts.)

Recall the toBinary algorithm from Tutorial 7 problem 3, which finds the binary representation of

a given integer n>0. For example, toBinary (13) = (1,1,0,1), and 1-23 +1-22 +0-2¹ +1-20 =

8 +4+0+1=13.

toBinary (n) :

1: if n 1 then.

2:

return (n)

3:

4:

5:

6:

else

(nd,no)

toBinary ([n/2])

= parity (n)

return (nd, no, I)

In Tutorial 7 we showed by induction that for any n20, if toBinary (n) = (na,....no) for some

d20, then we have n2 = n.

d

Note that toBinary takes in any integer n20 and spits out a binary number, which is an element

of {0,1}* (that is, an element of Uo0,1}). In other words, toBinary is a function from the

domain of Z2" to the codomain of {0, 1}*.

Use the result from Tutorial 7 to prove that toBinary : Z20 {0,1}* is one-to-one via a proof

by contrapositive.

Recall that we did an example of such a proof in the second lecture on functions and on PS3; use

those proofs to help structure your proof.

Grading Notes. While a detailed rubric cannot be provided in advance as it gives away solution

details, the following is a general idea of how points are distributed for this problem. We give

partial credit where we can.

(7) Correctness. If your proof is not correct, this is where you'll get docked. You'll need

(1) a statement that the proof is proceeding by contrapositive,

(1) the definition of one-to-one in its contrapositive form,

(5) other facts to prove f is one-to-one.

(2) Communication. We need to see a mix of notation and intuition, preferably in the "column"

format with the notation on the left, and the reasons on the right. If you skip too many steps

at once, or we cannot follow your proof, or if your solution is overly wordy or confusing, this

is where you'll get docked.