1) (24pts)
A binary relation R is defined on the
set A = {0, 1, 2, 3, 4}.
R = {(0, 0), (0, 1), (0, 2), (1, 1),
(1, 2), (2, 2), (3, 1), (3, 2), (3, 3), (4, 4)}.
a) 
Draw
a digraph representing R.
b) Complete
the below adjacency matrix for R.
c) Determine
whether the relation is reflexive. _______
d) Determine
whether the relation is symmetric. _______
e) Determine
whether the relation is transitive. _______
f)
Determine whether the relation is antisymmetric.
_______
g) Determine
whether the relation is an equivalence relation. _______
h) Determine
whether the relation is a partial order relation. _______
i)
If applicable, determine the transitive closure of R.
2) (15pts)
Consider a binary relation S on the set A from
problem 1.
For all x, y Î A, xSy Û x<
y.
a) What
is the cardinality of the domain of S? ________
b) What
is the cardinality of S? _______
c) Determine
whether the relation is an equivalence relation. _______
d) Determine
whether the relation is a partial order relation. _______
e) If
applicable, determine the equivalence classes of S.
3) (5pts)
The formula 1+2+3+…+n = n(n+1)/2
is true for all integers n > 1. Use this fact to find a
formula for:
3 + 3*2 + 3*3 +… + 3*n + n, where n is an integer and n
> 1.
4) (18pts)
define big-O, Reflexive, AntiSymmetric, Symmetric, Transitive.
5) Place
the following functions in order from slowest growing (quickest to execute) to
fastest growing (slowest to execute): nlgn,
n3, en, 10n, n2,
n.
a) (4pts)
Ordered list:
b) (3pts)
Is nen O(n2)?
________
c) (3pts)
Is 223n2 + 15n + 7.5 O(n2)?
________
6) A
= {0, 1, 2, 3, 4}
R = {(0,0), (0,2), (0,4), (1,1), (1,3), (2,0), (2,2), (3,1), (3,3), (4,0),
(4,4)}
Is R reflexive? __ __
Is R symmetric? _ __
Is R transitive? __ __, If not find the transitive closure of R: {(2, 4), (4, 2)}
List the distinct equivalence classes of R (union the transitive closure elements if needed). Include all the members
in each class:
7) Either draw a graph with the given specifications or
explain why no such graph exists:
Full Binary Tree with height 4, 16 internal vertices.
8) Are these two graphs isomorphic? If so label their
vertices so that the isomorphism is apparent. If not, list an isomorphic
invariant that is violated.
9) Use either Kruskal's or Prim's Algorithm to find a minimum spanning tree. Specify
the algorithm you use and show your work. What is the weight of your spanning
tree?
10) Given the following tree determine its
pre-order and post-order traversals:
Pre-order traversal:
Post order traversal:
11) Draw a tree with 6 vertices and 6 edges or
justify why one can't be drawn:
12) Draw a tree to represent the in-order
algebraic expression (2 * 3) + (24 / (6 - 2)) then write the expression in
Pre-order:
Post-order:
Binary Tree:
13)
Given the set H = {1, 2, 3}, Determine which
of the following relations exhibit reflexive, symmetric, and/or transitive
properties. Which are equivalence/partial order relations?
|
R
|
1
|
2
|
3
|
|
1
|
0
|
1
|
1
|
|
2
|
1
|
1
|
0
|
|
3
|
0
|
0
|
0
|
|
|
|
S
|
1
|
2
|
3
|
|
1
|
1
|
1
|
1
|
|
2
|
0
|
1
|
0
|
|
3
|
1
|
1
|
1
|
|
|
|
T
|
1
|
2
|
3
|
|
1
|
1
|
0
|
1
|
|
2
|
0
|
1
|
0
|
|
3
|
1
|
0
|
1
|
|
|
|
|
V
|
1
|
2
|
3
|
|
1
|
0
|
0
|
1
|
|
2
|
0
|
1
|
0
|
|
3
|
1
|
0
|
0
|
|
|
|
W
|
1
|
2
|
3
|
|
1
|
0
|
1
|
0
|
|
2
|
1
|
0
|
1
|
|
3
|
0
|
1
|
0
|
|
|