- 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).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) union [ [x] union y : y 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. - Recall that the symmetric difference,
*A+B*of two sets*A*and*B*(usually denoted by a circle surrounding a + sign) is defined as*(A union B) - (A intersect B)*(i.e. those elements which are in either*A*or*B*but not in both). Decide if*(A+B)+B = B*or*(A+B)+B=A*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*(A+B)+B*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*,*f(S intersect T)*is equal to*f(S) intersect f(T)*. Then give an example to show that this need not hold if*f*is not 1-1. - Use
*x^3*to denote the cube of*x*. Show that*5x^3 + 8*is*O(x^3/10)*. - 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:

procedure**Horner**(c,a_0,a_1,...,a_n: real numbers)

y:=a_n

for i:=1 to n

y:= y*c + a_(n-i)

{y=a_n*c^n + a_(n-1)*c^(n-1) + ... + a_1*c + a_0}Compute

*y*for*3x^2 + x + 1*for*x=2*. How many multiplications did you perform?