Assignment 1 (Math2320)

  1. Read sections 1.1-5 and Appendix 2.

  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?

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

  4. 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 ??

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

  6. Use x^3 to denote the cube of x. Show that 5x^3 + 8 is O(x^3/10).

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

  8. 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?