next up previous
Next: About this document -- Look for grading remarks in italics

  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. tex2html_wrap_inline55 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 tex2html_wrap_inline67 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]
      x:= any element of S
      T:= S with x removed
      Sets(S) := Sets(T) tex2html_wrap_inline71
      tex2html_wrap_inline73 is a member of Sets(T)]
      end tex2html_wrap_inline77 the end of the procedure tex2html_wrap_inline79

    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 tex2html_wrap_inline87.(1 mark here) Something like the following is acceptable:

    (1 more here) displaymath89

    so we need to call Sets with the new argument tex2html_wrap_inline91


    and then we need to compute


    and, of course,


    till finally

    (1 more here) displaymath99

    Now just substitute back: (1 here)


    Hence, letting y take on the only value, tex2html_wrap_inline105 , in tex2html_wrap_inline107 tex2html_wrap_inline109  .

    Similarly tex2html_wrap_inline111 .

    tex2html_wrap_inline113 .

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

  6. Recall that the symmetric difference, tex2html_wrap_inline119 of two sets A and B is defined as tex2html_wrap_inline125 (i.e. those elements which are in either A or B but not in both). Decide if tex2html_wrap_inline131 or tex2html_wrap_inline133 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 tex2html_wrap_inline137 then ... hence x is also in the set ??
  7. Ans: 4 marks We decide, perhaps using Venn diagrams (2/4 for just Venn) , that tex2html_wrap_inline133 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 tex2html_wrap_inline143 considered in your picture)

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

    if tex2html_wrap_inline151 , then tex2html_wrap_inline153 but not in B. But then tex2html_wrap_inline157 or tex2html_wrap_inline159 , hence x must be in A-B since tex2html_wrap_inline165 is impossible.

    if tex2html_wrap_inline167 , then tex2html_wrap_inline169 and x is not in tex2html_wrap_inline119 . Now use the original definition of tex2html_wrap_inline175 to notice that x must be in tex2html_wrap_inline179 since it is certainly in tex2html_wrap_inline181 but not tex2html_wrap_inline119 . Therefore, again, tex2html_wrap_inline147 .

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

  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 , tex2html_wrap_inline231 is equal to tex2html_wrap_inline233 . 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 tex2html_wrap_inline231 , then b is also in tex2html_wrap_inline233 , and conversely. The first (1 here) is easy, I'll just do the second. Suppose that tex2html_wrap_inline257 . By definition (always important) of f(S), there is an tex2html_wrap_inline261 (1 here) such that f(a)=b. Similarly there is an tex2html_wrap_inline265 such that f(a')=b. If we show that a=a', then we know that tex2html_wrap_inline271 , thus tex2html_wrap_inline273 . Well, a does equal a' (1 here) because f is 1-1.

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

  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 tex2html_wrap_inline321 for all values of tex2html_wrap_inline323 . 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 tex2html_wrap_inline329 . Now take any tex2html_wrap_inline323

    displaymath333 (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( tex2html_wrap_inline345 : real numbers)
    for i:=1 to n


    Compute y for tex2html_wrap_inline359 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 tex2html_wrap_inline363 for the value x=c. So we should start up the procedure with


    Well y starts out as tex2html_wrap_inline371 . Then we start the ``for'' loop for i=1 to 2:
    then again with i=2
    tex2html_wrap_inline381 .
    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).

next up previous
Next: About this document

Eli Brettler
Sat Sep 21 22:36:40 EDT 1996