Theory of Computation prerequisite test

Please fill out this form with thought and submit it. You will get 2 exercise points for your trouble, if you try to answer (or explain why you haven't answered) every question. Hopefully your answers will help us to build a better course for you! Thank you.

Your name: (you can be anonymous, but in that case we can't give you additional points :-) )

  1. Let A = {1, 2, 3, 4, 5}, B = {3, 4, 7, 8}, C = {1, 5, 7, 8, 9}. Find:





  2. How would you describe the shaded areas in the following diagrams? You can assume you have 3 operations: UNION, INTERSECTION and COMPLEMENT. You may mark them as U for UNION, I for INTERSECTION and \ for COMPLEMENT. Example: (B U C) \ A




  3. If p is true and q is false, are the following clauses true?





  4. Let p: "Windhoek is the capital city of Namibia" and q: "I study computer science at Joensuu". Express verbally the clauses from task 3. Don't care about how silly they may sound. :)



  5. A Cartesian product of sets A and B is

    in which each (x,y) is an ordered pair. Let A = {1, 2, 3} and B = {a, b, c}. List the items of A x B, B x A and A x A.



  6. Prove that 1 + 3 + 5 + ... + (2n-1) = n^2 is true for all positive integers.



  7. Let A = {1, 2, 3} and B = {a, b, c}. Suppose R is an relation from A to B (A x B). Considering the next arrow diagram which of the following is true:


    a) R = { (1, a), (1, c), (2, a), (3, b) }
    b) R = { (a, 2), (3, b), (c, 1), (1, a) }
    c) R = { (a, 1), (a, 2}, (b, 3), (c, 1) }

  8. Which diagram defines a function from A = {1, 2, 3} to B = {a, b, c}.


    a
    b
    c

  9. Let A be the set of students in UNAM. Determine which of the following assignments defines a function on A.
    a) To each student assign his/her age.
    b) To each student assign his/her teacher.
    c) To each student assign his/her bike

    Explain your selections (as briefly as possible):



  10. Find a5 when a1 = 1, an+1 = an * (n + 1)



  11. The Pigeonhole Principle (aka Dirichlet Drawer Principle, Shoe Box Principle) states that if n pigeons fly into k pigeonholes and k < n, some pigeonhole contains at least two pigeons. Prove this statement is true by arguing by contradiction. Hint: Form an antitheses.



  12. A bus with an infinite number of gentlemen (let's call them "gentleman1", "gentleman2" and so on) arrives at the new Hotel California with an infinite number of rooms (each room is marked with some natural number: 1, 2, 3, ...). How should hotel administration place them, if we don't want to have problems with placement of an infinite number of ladies, who are coming soon (assuming every person occupies one room)?



  13. How difficult this test was for you on a scale from 1 to 10 (1 = easy, 10 = extremely difficult)?



  14. What do you expect and want to learn during the course?



  15. Comments: