$30
CS2214
Assignment #5
Submission: on the OWL web site of the course
Problem 1 (Relations) [25 marks]
1. Show that the relation
R = {(x, y)| (x − y) is an even integer}
is an equivalence relation on the set R of real numbers.
Given a set R={(x, y) | x – y is an even number}
To prove equivalence, we need to prove the relation are reflexive,
symmetric and transitive.
1. To prove reflexive, we need to prove:
a) x ∈ A → (x, x) ∈ R
x is belonging to a not empty set therefore x ∈ A
for all x, x – x is always 0, and 0 is an even number
therefore (x, x) ∈ R
The relation is reflexive
2. To prove symmetric, we need to prove:
a) (x, y) ∈ R → (y, x) ∈ R
We know that (x, y) ∈ R therefore:
x – y = a (where a is an even number)
y – x = – a
– a is also an even number, (y, x) ∈ R
The relation is symmetric
3. To prove transitive, we need to prove:
a) (x, y) ∈ R ∧ (y, z) ∈ R → (x, z) ∈ R
By (x, y) ∈ R, we can have:
x – y = k (where k is an even number)
because k is an even number k=2a (where a is an integer)
x – y = 2a
Similarly, by having (y, z) ∈ R, we can have:
y – z = 2b (where b is an integer)
x – z = (y + 2a) – z = (2b + z + 2a) – z = 2(a + b)
2(a + b) is always an even number
Thus, (x, z) ∈ R.
The relation is transitive
Because the relation of set R are reflexive, symmetric and transitive,
it is an equivalence relation.
2. Show that the relation
R = {((x1, y1),(x2, y2)) (x1 < y1) or ((x1 = y1) and (x2 < y1))}
is a total ordering relation on the set R × R.
R = {( (x1, y1), (x2, y2) ) (x1 < y1) or ( (x1 = y1) and (x2 < y1) ) } is a total
ordering relation on the set R × R.
To prove a set is total ordering set, we need to prove that:
every two elements of S are comparable
This is the more readable version of the above question:
R = { (x1, y1), (x2, y2) | (x1 < y1) ∨ (x1 = y1 ∧ x2 < y1) }
In this set, either (x1 < y1) or x1 = y1 and x2 < y1
therefore, this is a comparable set.
To prove it is a total order, we need to prove it is a binary relation set which also
every set element is antisymmetric, transitive and connex relation
(see this https://en.m.wikipedia.org/wiki/Total_order).
4. To prove reflexive, we need to prove:
a) x ∈ A → (x, x) ∈ R
if (x1, y1) == (x2, y2), then it satisfies x1 == x2 and y1 ≤ y2
Therefore, it is reflexive
5. To prove antisymmetric, we need to prove:
a) not (x, y) ∈ R → (y, x) ∈ R
if x1 < x2 then x1 is smaller than x2, x2 is not smaller than x1
Therefore it is antisymmetric
6. To prove connex, we need to prove
a) ∀x∀y (x ∈ X ∧ y ∈ X) ⇒ (xRy ∨ yRx ).
x1 ∈ X and y1 ∈ X and
we can find that x1y1 is in the set R and so yRx
Therefore, the set is connex
Overall the set R is in total order.
Problem 2 (Basic probability calculations) [25 marks] In a roulette,
a wheel with 38 numbers is spun. Of these, 18 are red, and 18 are black.
The other two numbers, which are neither black nor red, are 0 and 00. The
probability that when the wheel is spun it lands on any particular number
is 1/38.
1. What is the probability that the wheel lands on a red number?
2. What is the probability that the wheel lands on a black number twice
in a row?
3. What is the probability that the wheel lands on 0 or 00?
4. What is the probability that in five spins the wheel never lands on
either 0 or 00?
In this sample space S, if we spun only one time,
we can only land on either red, black, 00 or 0.
|S| = 38, |red| = 18, |black| = 18, |00| = 1, |0| = 1
Therefore 1 = P(red) + P(black) + P(00) + P(0) and 38 = 18 + 18 + 1 + 1
1) P(red) = |red| / |S| = 18 / 38 ~= 0.47
2) P(black) = |black| / |S| = 18 / 38 ~= 0.47
a) because it is twice, the answer is (0.47)*0.47
3) P(00 and 0) = |00 and 0| / |S| = 2/ 38 ~= 0.05
4) P(not 00 and 0) = |not 00 and 0| / |S| = 36/38 ~= 0.94
the above is the probability for one spin. the five spin is (36/38)
5 ~=
0.73
Problem 3 (Bayes theorem) [25 marks] Suppose that 8% of all bicycle racers use steroids, that a bicyclist who uses steroids tests positive for
steroids 96% of the time, and that a bicyclist who does not use steroids tests
positive for steroids 9% of the time (this is a “false positive” test result).
1. What is the probability that a randomly selected bicylist who tests
positive for steroids actually uses steroids?
2. What is the probability that a randomly selected bicyclist who tests
negative for steroids did not use steroids?
S denotes that bicyclist use steroid.
T denote test is positive.
By reading the content I gather that:
P(S) = 0.08
P(¬S) = 0.92
P(S∩T) = 0.96
P(S∩¬T) = 0.04
P(¬S∩T) = 0.09
P(¬S∩¬T) = 0.91
1) Already know that the test is positive, how many of them use steroid?
P(S|T) = P(T|S) * P(S) / P(T|S) * P(S) + P(T|¬S) * P(¬S)
P(T|S) = P(T∩S) / P(S) = 0.96/0.08 = 12
P(T|¬S) = P(T∩¬S) / P(¬S) = 0.09/0.92 = 98%
Therefore, P(S|T) is equal to
= 12 * 0.08 / 12 * 0.08 + 0.098 * 0.92 = 91.4%
2) Already know that the test is negative, how many of them did not use
steroid?P(¬S|¬T) = P(¬T |¬S) * P(¬S) / P(¬T |¬S) * P(¬S) + P(¬T |S) *
P(S)P(¬T |¬S) * P(¬S) = P(¬T∩¬S) / P(¬S) * P(¬S) = P(¬T∩¬S) = 0.91
P(¬T |S) * P(S) = P(¬T∩S) / P(S) * P(S) = P(¬T∩S) = 0.04
P(¬S|¬T) = 0.91 / (0.91 + 0.04) = 0.958
Problem 4 (Graphs) [25 marks] For each of the following two graphs,
determine whether or not it has an Euler circuit. Justify your answers. If
the graph has an Euler circuit, use the algorithm described in class to find
it, including drawings of intermediate subgraphs.
If a graph has an Euler circuit then the degree of every
vertex must be even.
Which means:
If the degree of one vertex are not even, then
there will be no Euler circuit exist. This graph satisfy the
condition. Then we can use the algorithm to test it.
Theorem: A connected multigraph with
at least two vertices has an Euler circuit
if and only if each of its vertices has an
even degree
and
it has an Euler path if and only if it has
exactly two vertices of odd degree.
This graph does not have Euler circuit, because not all
deg is even.
but there is a Euler Path exists