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).