Next: About this document -- Look for grading remarks in italics
Ans: 0 marks Easy
Ans: 0 marks.
elements. Yes it works if A or B is empty because in these
cases, A x B is also empty.
procedure Sets (S: a finite set)
if (S is empty) then Sets(S) := 
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,
(1 more here)
Now just substitute back: (1 here)
Hence, letting y take on the only value, , in .
Finally, (1 here)
you can see that
is just the power set of .
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 .
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.
Ans: 3 marks
Just take C=130 and k=1 (many other combinations
of C and k will work as well). If
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
(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.
: 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).