MUN Computer Science 1002 - Lab 5

Sets

Review:

Vocabulary

 

Individual work

Solve each of the following exercises.

  1. Recall the quotient-remainder theorem from lecture 15 that for every integer $n$ and natural number $d$ there exist integers q and r, where $0 \leq r \leq d-1 $ such that $n = qd+r$. Now, for each of the following pairs of d and n, find $q$ and $r$.
  2. For d=3 and d=4, list all the numbers congruent to 0 mod d that are between -5 and 10. Now, repeat the exercise with the same two values of d and numbers congruent to 1 mod d (so you should have 4 lists of numbers in this exercise).
  3. For each of the following, list all elements in the resulting set.
  4. For each of the following, write a list of elements of the Cartesian product.
  5. Give cardinalities of all sets you described in the previous two questions.

Group exercises

For each of the questions below, create a representation of a set by putting corresponding figures in a plastic bag. For most of the exercises, copies of the same element count as one element, so avoid duplicates.

Exercise 1: Set operations

Use pieces in a bag labeled 1 for this exercise. First, create a representation of a set containing an orange star, a green star and a green circle by picking the corresponding pieces and putting them in a plastic bag. Now, each of the three members of the group should create their own set with 4 elements, by picking 4 pieces each and putting them in their own plastic bags. So together with the original one you have 4 sets. Pick two out of three sets you and your friends made which have at least one element in common. Let's call these sets A and B, and the remaining 4-element set C. Let's call your first set {orangestar, greenstar, greencircle} D.

Exercise 2: Subsets and powersets

Use a bag number 2 for this exercise.

Exercise 3: The law of inclusion/exclusion

Take the bag marked "3". For this exercise, you will treat each piece in this bag individually (so the bag has 9 pieces, rather than 4 types).

Review after the group activity

Let $A = \{0,2, 5\}$ and $B = \{ 5, \{\emptyset\}\}$.

  1. List elements in $A \cup B$, $A \cap B$, $A-B$ and $A \triangle B$. Draw a Venn diagram for each.
  2. Let the universe be $\{0,1,2,3,4,5,\{\emptyset\} \}$. List elements in $\overline{A}$ and in $\overline{B}$.
  3. What are the powerset of A and of the powerset of B? Describe the set as $\{ .... \}$ with the list of elements. Note that the last element in B is a set containing an empty set, not just an empty set (think empty bag inside an empty bag).
  4. Let $|C|=20$ and $|D|=15$ for some sets $C$ and $D$. What are the maximal and minimal values of $|C \cup D|$ and $|C \cap D|$? What is the relationship between C and D when the values are minimal/maximal?
  5. Solve the following problem using inclusion-exclusion.
    Suppose there are 30 people at a party interested in music, 35 interested in mathematics and 40 interested in biology. There are 15 people interested in both math and biology, 20 in math and music and 10 in music and biology; out of them 5 people are interested in all three. How many people are at the party? Draw a Venn diagram, and for each region on it, note how many people are in that region.