**Next:** About
this document -- *Look for grading remarks in italics *

- Read sections 1.1-5 and Appendix 2.
- 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? - 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). - 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 ?? - 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. - Use
to denote the cube of
*x*. Show that is . - 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*. - Horner's method for evaluating a polynomial:

**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) := [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 .

**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 , hencexmust be inA-Bsince is impossible.

if , then and

xis not in . Now use the original definition of to notice thatxmust 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
, then
, hence
.

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

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

Sat Sep 21 22:36:40 EDT 1996