Testing Your Program

All programs must be thoroughly tested before they are released to users. Create some sample input files of a small size and manually figure out what the outputs should be. Run your program and make sure that your output matches the one you manually computed.

Question 1: On the first page of your assignment, write

• your name,
• your student number, and
• the tutorial (T1, T2, or T3) in which you are registered.

Question 2: In this question, we consider finite bit strings that do not contain 00. Examples of such bitstrings are 0101010101 and 11110111.

For any integer n ≥ 2, let Bn be the number of bitstrings of length n that do not contain 00.

1.  Determine B2 and B3.

2.  Prove that Bn = Bn1 + Bn2 for each n ≥ 4.

3.  For each n ≥ 2, express Bn in terms of a Fibonacci number.

Question 3: Let S be the set of ordered triples of integers that are defined in the following way:

• (20; 7; 449) 2 S.
• If (a; b; c) 2 S then (a + 3; b + 4; 6a + 8b + c + 25) 2 S.

Prove the following:

For every element (a; b; c) in S, we have a2 + b2 = c.

Question 4: Recall that N = f0; 1; 2; 3; : : :g. The function f : N3 ! N is defined as follows:

1.  f(x; n; 0) = x + n for x _ 0 and n _ 0,

2.  f(x; 0; 1) = 0 for x _ 0,

3.  f(x; 0; 2) = 1 for x _ 0,

4.  f(x; 0; i) = x for i _ 3,

5.  f(x; n; i) = f(x; f(x; n = 1; i); i =1) for i _ 1 and n _ 1.

Determine f(2; 3; 2).