1. Read sections 1.1-5 and Appendix 2.
2. Ans: 0 marks Easy

3. How many elements does A x B have if A has m elements and B has n elements? Does your formula hold if A or B is empty?
4. Ans: 0 marks. elements. Yes it works if A or B is empty because in these cases, A x B is also empty.

5. Here is a procedure for finding a list of subsets of a finite set S (let 0 denote the empty set and since the text uses for comments in pseudocode, we will use (for this question) [1,2,3] to denote the set 1,2,3 and [ x : x >3 ] for the set builder notation).
1. procedure Sets (S: a finite set)
if (S is empty) then Sets(S) := [0]
else
begin
x:= any element of S
T:= S with x removed
Sets(S) := Sets(T)
is a member of Sets(T)]
end the end of the procedure

Your task is simply to illustrate the steps for computing Sets([1,2,3,4]) and describe in words what the result of Sets(S) is for general sets S.

Ans: 5 marks You would have realized by now that this is a recursive function call. You would also have had no trouble choosing some x in S (we will always choose the maximum for definiteness) and then letting T be .(1 mark here) Something like the following is acceptable:

(1 more here)

so we need to call Sets with the new argument

and then we need to compute

and, of course,

till finally

(1 more here)

Now just substitute back: (1 here)

Hence, letting y take on the only value, , in  .

Similarly .

.

Finally, (1 here) you can see that is just the power set of .

6. Recall that the symmetric difference, of two sets A and B is defined as (i.e. those elements which are in either A or B but not in both). Decide if or is true, and then argue your claim by choosing an element of either side and then explaining why it is in the other side, e.g. if x is a member of then ... hence x is also in the set ??
7. Ans: 4 marks We decide, perhaps using Venn diagrams (2/4 for just Venn) , that is true. Be very careful about using Venn diagrams as ``proofs'' because it is difficult to be sure that you have considered every possible case (e.g. is the case considered in your picture)

Instead, I suggest here that we start with an and then make a case-analysis argument that . Indeed, we can use . So we know that

if , then but not in B. But then or , hence x must be in A-B since is impossible.

if , then and x is not in . Now use the original definition of to notice that x must be in since it is certainly in but not . Therefore, again, .

The opposite direction: that if , then is done similarly. How about a simple two cases: or . x in both A and B says that x is not in . Therefore x is in . Now if , we know that x is in , and again, not in B tells us that .

8. Let f be a function from the set A to the set B . Show that if f is 1-1 then for subsets S,T of A , is equal to . Then give an example to show that this need not hold if f is not 1-1.
9. Ans: 4 marks We suppose that f is any 1-1 function from some set A to B. Let S and T be any subsets of A (special cases is not enough!). Now show (1 here) two things: if b is in , then b is also in , and conversely. The first (1 here) is easy, I'll just do the second. Suppose that . By definition (always important) of f(S), there is an (1 here) such that f(a)=b. Similarly there is an such that f(a')=b. If we show that a=a', then we know that , thus . Well, a does equal a' (1 here) because f is 1-1.

10. Use to denote the cube of x . Show that is .
11. Ans: 3 marks Just take C=130 and k=1 (many other combinations of C and k will work as well). If , then , hence .

12. Suppose that f(n) is a function with domain equal to the positive integers and that n is O(f(n)) . Show that | f(n)| <10 for only finitely many values of n .
13. Ans: 4 marks You may have noticed that I added ``positive'' and absolute values to the question. Work with the definition of ``n is O(f(n))''. There is some C and some k (2 here) so that for all values of . It is very important that you can understand that we can make k larger if we want and this statement will remain true. Therefore we can assume that k is bigger than . Now take any

(1 here)

(just cancel the C's). But this means that the only values of n for which it is possible for |f(n)|<10 are those that are below k. Therefore there (1 here) are at most k such values.

14. Horner's method for evaluating a polynomial:
15. procedure Horner( : real numbers)

for i:=1 to n

Compute y for for x=2 . How many multiplications did you perform?

Ans: No marks By the comment at the end of the procedure, we see that the purpose of this procedure is to evaluate the polynomial for the value x=c. So we should start up the procedure with

Well y starts out as . Then we start the ``for'' loop for i=1 to 2:

then again with i=2
.
Clearly we performed only 2 multiplications. (Whereas if we computed 3*(2*2) + 1*(2) + 1 as usual we would perform 4 multiplications - Okay, Okay, 1*2 isn't a difficult multiplication but the computer wouldn't know that the coefficient was one).