MAT 230 EXAM TWO
1
P
ROBLEM
1
This
question
has
2
parts.
Part
1:
Suppose
that
F
and
X
are
events
from
a
common
sample
space
with
P
(F
)
≠
0
and
P
(X)
≠
0.
(a)
Pro
v
e
that
P
(
X
)
b
=
b
P
(
X
|
F
)
P
(
F
)
+
P
(
X
|
F
¯)
P
(
F
¯
).
Hin
t:
b b
Explain
wh
y
P
(
X
|
F
)
P
(
F
)
b
=
P
(X
∩
F
)
is
another
way
of
writing
the
definition
of
conditional
probability,
and
then
use
that
with
the
logic
from
the
proof
of
Theorem
4.1.1.
P
(X
|
F
)P
(F
)
=
P
(X
∩
F
)
is
true
because
we
want
to
get
all
probabilities
of
both
events
occurring
but
want
to
avoid
counting
those
events
that
have
already
been
counted.
When
the
intersection
of
the
probabilities
is
subtracted
we
take
away
those
that
have
been
counted
twice.
Since
all
probabilities
must
add
up
to
1
and
no
more
we
can
say
that
the
addition of the original probabilities and the complements of said probabilities will
give a
value
of
1.
(b)
Explain
why
P
(F
|
X)
=
P
(X
F
|
)P
(F
)/P
(X)
is
another
way
of
stating
Theorem
4.2.1
Bayes’
Theorem.
since
P(x)=
P
(
X
|
F
)
P
(
F
)
+
P
(
X
|
F
¯)
P
(
F
¯)
and
bayes
theorem
is
as
follows:
p
(
X
|
F
)
p
(
F
)
p
(
X
|
F
)
p
(
F
)+
p
(
X
|
F
¯
)
p
(
F
¯
)
we
can
see
that
the
denominator
and
P(x)
are
equal
so
can
substitute.
Part
2:
A
website
reports
that
70%
of
its
users
are
from
outside
a
certain
country.
Out
of
their
users
from
outside
the
country,
60%
of
them
log
on
every
day.
Out
of
their
users
from
inside
the
country,
80%
of
them
log
on
every
day.
(a)
What
percent
of
all
users
log
on
every
day?
Hint:
Use
the
equation
from
Part
1
(a).
O=
OUTSIDE
I=INSIDE
E=EVERYDAY
p(O)=0.7
p(I)=0.8
p(E)=0.6
P(x)=
P
(
X
|
F
)
P
(
F
)
+
P
(
X
|
F
¯)
P
(
F
¯)
P(X)=
(1-
.8)(0.6)+(0.7)(0.8)=0.68
The
probability
is.68
or
68
percent.
(b)
Using
Bayes’
Theorem,
out
of
users
who
log
on
every
day,
what
is
the
probability
that
they
are
from
inside
the
country?
Baye’s
Theorem:
p
(
X
|
F
)
p
(
F
)
p
(
X
|
F
)
p
(
F
)+
p
(
X
|
F
¯
)
p
(
F
¯
)
=
(0.30)(0.8)/((0.3*.6)+(0.7*.4))=0.521
The
probability
is
0.521
or
52.1
percent.
P
ROBLEM
2
This
question
has
2
parts.
Part
1:
The
drawing
below
shows
a
Hasse
diagram
for
a
partial
order
on
the
set:
{
A,
B,
C,
D,
E,
F,
G,
H,
I,
J
}
Figure
1:
A
Hasse
diagram
shows
10
vertices
and
8
edges.
The
vertices,
represented
by
dots,
are
as
follows:
vertex
J
is
upward
of
vertex
H;
vertex
H
is
upward
of
vertex
I;
vertex
B
is
inclined
upward
to
the
left
of
vertex
A;
vertex
C
is
upward
of
vertex
B;
vertex
D
is
inclined
upward
to
the
right
of
vertex
C;
vertex
E
is
inclined
upward
to
the
left
of
vertex
F;
vertex
G
is
inclined
upward
to
the
right
of
vertex
E.
The
edges,
represented
by
line
segments
between
the
vertices
are
as
follows:
3
vertical
edges
connect
the
following
vertices:
B
and
C,
H
and
I,
and
H
and
J;
5
inclined
edges
connect
the
following
vertices:
A
and
B,
C
and
D,
D
and
E,
E
and
F,
and
E
and
G.
Determine the properties of the Hasse diagram based on the following questions:
(a)
What are the minimal elements of the partial order?
Minimal
elements
hold
y
/
=
x
and
y
≤
x.
On
the
diagram
it
would
be
the
points
with
no
connections
below
so,
I,A,F
are
b
the
minimalelements.
(b)
What are the maximal elements of the partial
order?
Maximal
elements
hold:
y
/
≠x
an
y
≥
x.
On
the
diagram
it
is
the
points
with
no
connections
above
them
so,
J,D,G
are
the
maximalelements.
(c)
Which
of
the
following
pairs
are
comparable?
(A,
D),
(J,
F
),
(B,
E),
(G,
F
),
(D,
B),
(C,
F
),
(H,
I),
(C,
E)
Comparable
ordered
pairs
are
pairs
that
can
be
reached
by
travelling
in
a
single
direction.Out
of
the
list
the
following
are
comparable:
(A,D),(D,B),(G,F),(H,I)
Part
2:
Consider
the
partial
order
with
domain
{
3,
5,
6,
7,
10,
14,
20,
30,
60,
70
}
and
with
x
≤
y
if
x
evenly
divides
y.
Select
the
correct
Hasse
diagram
for
the
partial
order.
(a)
Figure
2:
A
b
Hasse
diagram
shows
a
set
of
b
elements
3;
5;
6;
7;
10;
14;
20;
30;
60,
70.
There
are
lines
connecting
3
and
6,
6
and
30,
30
and
60,
5
and
10,
10
and
20,
20
and
60,
10
and
70,
7
and
14,
14
and
70.
This diagram is incorrect because the 10 is not connected to the 30 or the 60.
Also the 5 is not connected to its multiple of 30.
(b)
Figure
3:
A
b
Hasse
diagram
shows
a
set
of
b
elements
3;
5;
6;
7;
10;
14;
20;
30;
60,
70.
There
are
lines
connecting
3
and
6,
6
and
30,
30
and
60,
5
and
10,
10
and
30,
10
and
20,
20
and
60,
10
and
70,
7
and
14,
14
and
70.
This
is
the
correct
Hasse
diagram
because
all
factors
are
connected
to
their
correspondingmultiples.
It
satisfies
the
given
of
x
evenly
dividing
y.
(c)
Figure
4:
A
b
Hasse
diagram
shows
a
set
of
b
elements
3;
5;
6;
7;
10;
14;
20;
30;
60,
70.
There
are
lines
connecting
3
and
6,
6
and
30,
30
and
60,
5
and
10,
10
and
30,
10
and
20,
20
and
60,
20
and
70,
7
and
14,
14
and
70.
This is incorrect because b 70 b b b b is connected to 20 even though 70 cannot
evenly be dividedby 20.Also 5 is not connected to 30 even though 30 can evenly be divided
by 5.
(d)
Figure
5:
A
b
Hasse
diagram
shows
a
set
of
b
elements
3;
5;
6;
7;
10;
14;
20;
30;
60,
70.
There
are
lines
connecting
3
and
6,
6
and
30,
30
and
60,
5
and
10,
10
and
30,
10
and
20,
20
and
30,
20
and
60,
10
and
70,
7
and
14,
14
and
70.
This is incorrect because 20 is connected to b 30. 20 is not a factor of number 30.
P
ROBLEM
3
A
car
dealership
sells
cars
that
were
made
in
2015
through
2020.
Let
the
cars
for
sale
be
the
domain
of
a
relation
R
where
two
cars
are
related
if
they
were
made
in
the
same
year.
(a)
Prove
that
this
relation
is
an
equivalence
relation.
To prove an equivalence relation, we must first define the properties of said relation as
reflexive, symmetry, and transitive.
This
relation
is
reflexive
because
xRx
holds
true.
Since
a
vehicle
can
only
have
1
manufacture
year
it
is
always
related
to
itself.
This
relation
is
symmetric
because
xRy
and
yRx
hold
true.
Since
the
domain
includes
vehicles
m
b b b b
anufactured
in
the
b
same
b
year
and
x
is
related
to
y
then
y
is
b
related
to
b
x.
This
relation
is
transitive
because
xRy,
yRz,
and
xRz
hold
true.
If
x
and
y
are
related
bymanufacture
year
and
y
and
z
are
related
similarly
then
x
and
z
are
related.
This
is
an
equivalence
relation.
(b)
Describe
the
partition
defined
by
the
equivalence
classes.
The
classes
are
divided
by
manufacture
year
of
vehicles.
b
So,
all
vehicles
manufactured
in
2015
would
be
in
the
same
group
as
well
as
all
manufactured
in
2016
would
be
in
one
group
and
so
on.
P
ROBLEM
4
Analyze
each
graph
below
to
determine
whether
it
has
an
Euler
circuit
and/or
an
Euler
trail.
•
If
it
has
an
Euler
circuit,
specify
the
nodes
for
one.
•
If
it
does
not
have
an
Euler
circuit,
justify
why
it
does
not.
•
If
it
has
an
Euler
trail,
specify
the
nodes
for
one.
•
If
it
does
not
have
an
Euler
trail,
justify
why
it
does
not.
(a)
Figure
6:
An
undirected
graph
has
6
vertices,
a
through
f.
There
are
8-line
segments
that
are
between
the
following
vertices:
b
a
and
b,
a
and
c,
a
and
d,
a
and
f,
b
and
c,
b
and
e,
b
and
f,
d
and
e.
An
Euler’s
circuit
is
a
closed
walk
where
all
edges
are
travelled
exactly
once.
An
Euler’s
trail
is
one
where
all
edges
are
travelled
exactly
once
but
it
is
an
open
walk.
This
is
an
Euler’s
Circuit
because
we
b
can
start
at
vertex
b
C
and
b
used
every
edge
just
once
toreturn
back
to
vertex
c.
The
Euler’s
Circuit
is
as
follows:
<c,b,e,d,a,f,b,a,c>
The
edges
used
are
cb,be,ed,da,af,fb,ba,
and
ac.
(b)
Figure
7:
An
undirected
graph
has
6
vertices,
a
through
f.
There
are
9-line
segments
that
are
between
the
following
vertices:
a
and
b,
a
and
c,
a
and
d,
a
and
f,
b
and
e,
b
and
f,
c
and
d,
d
and
e,
d
and
f.
An
Euler’s
circuit
is
a
closed
walk
where
all
edges
are
travelled
exactly
once.
An
Euler’s
trail
is
one
where
all
edges
are
travelled
exactly
once
but
it
is
an
open
walk.
There
is
no
Euler’s
Circuit
because
there
is
an
odd
number
of
edges
and
there
is
no
closedwalk
such
that
every
edge
is
used
exactly
once.
This
is
an
Euler’s
Trail:
<b,a,c,d,e,b,f,a,d,f>
The
edges
used
are:
ba,ac,cd,de,eb,bf,fa,ad,and
df.
(c)
Figure
b
8:
An
undirected
graph
has
5
vertices,
a
through
e.
There
are
4-line
segments
that
are
between
the
following
vertices:
b
and
c,
b
and
e,
c
and
d,
d
and
e.
This
is
neither
an
b
Euler’s
Circuit
b
or
trail
because
the
diagram
is
not
connected
at
vertex
a.
Since
the
definition
for
both
states
all
edges
must
be
used
this
mean
all
vertices
will
be
visitedin
either
option
and
we
cannot
visit
vertex
a
from
any
or
the
other
vertices.
(d)
Figure
9:
An
undirected
graph
has
7
vertices,
a
through
g.
There
are
10-line
segments
that
are
between
the
following
vertices:
a
and
b,
a
and
c,
a
and
f,
b
and
c,
b
and
f,
c
and
d,
c
and
g,
d
and
e,
d
and
f,
f
and
g.
This
diagram
is
not
a
Euler’s
Circuit
because
there
is
a
vertex
of
degree
1.
There
is
no
such
way
to
connect
the
vertices
to
where
all
edges
will
be
used
just
once.
This
diagram
is
not
a
Euler’s
trail
because
there
is
no
such
open
walk
that
all
edges
are
usedonly
once.
So
this
diagram
is
neither.
P
ROBLEM
5
Use
Prim’s
algorithm
to
compute
the
minimum
spanning
tree
for
the
weighted
graph.
Start
the
algorithm
at
vertex
A.
Explain
and
justify
each
step
as
you
add
an
edge
to
the
tree.
Figure
10:
A
weighted
graph
shows
5
vertices,
represented
by
circles,
and
6
edges,
represented
by
line
segments.
Vertices
A,
B,
C,
and
D
are
placed
at
the
corners
of
a
rectangle,
whereas
vertex
E
is
at
the
center
of
the
rectangle.
The
edges,
A
B,
B
D,
A
C,
C
D,
A
E,
and
E
C,
have
the
weights,
7,
3,
2,
4,
5,
and
6,
respectively.
When
using
Prim’s
Algorithm,
one
starts
at
the
1st
vertex,
in
this
case
vertex
A.
We then search out all connected edges for the lowest valued edge to travel to get to our
next
vertex.
We
repeat
this
process
until
all
vertices
have
been
visited.
We
take
the
values
of
the
travelled edgesand add them up to get the minimum spanning tree.
For
this
diagram,
we
will
start
with
A
travel
to
vertex
C
using
edge
AC
(value
of
2),
then
travel
to
vertex
D
using
edge
CD
(value
of
4),
to
vertex
B
using
edge
DB
(value
of
3),
to
vertex
a
using
edge
BA
(value
of
7),
finally
stopping
at
the
last
vertex
E
by
travelling
AE
(value
of
5).
Adding
up
all
the
values
we
get:
2+4+3+7+5=21.
P
ROBLEM
6
A
lake
initially
contains
1000
fish.
Suppose
that
in
the
absence
of
predators
or
other
causes
of
removal,
the
fish
population
increases
by
10%
each
month.
However,
factoring
in
all
causes,
80
fish
are
lost
each
month.
Give
a
recurrence
relation
for
the
population
of
fish
after
n
months.
How
many
fish
are
there
after
5
months?
If
your
fish
model
predicts
a
non-integer
number
of
fish,
round
down
to
the
next
lower
integer.
Given
that
the
population
increases
by
10
percent
each
month,
we
know
that
the
value
of
the
next
month
will
be
1.10
times
the
previous
month
(100
percent
of
the
current
month
plus
the
10
percent
increase)
and
taking
away
80
fish
that
is
lost
each
month.
Using
a
sequence,
we
can
note
that
the
population
of
any
given
month
in
the
future
can
be
modeledby
the
following:
P
n
=
P
n
−
1
+
.10P
n
−
1
−
80
simplifying
this
equation,
we
get
:
P
n
b
=
1.10
∗
b b
Pn
−
1
−
80
To
find
the
population
of
fish
at
the
end
of
the
5
months,
we
first
need
to
find
the
previous
4-month
values
becausethe
5
month
depends
on
its
previous
months.
P
0
=
1000
P1 = 1.10(1000) − 80 =
1020 P2 = 1.10(1020) − 80
= 1042 P3 = 1.10(1042) − 80
= 1066.2
P4 b b = 1.10(1066.2) − 80 = 1092.82
P
5
=
1.10(1092.82)
−
80
=
1122.1
Therefore, there b will b be b 1, 122 fish at the end of the 5th month.
