Name Row
Show your work
on this exam, NOT on the scratch paper.
Transfer what you want graded to this sheet.
1.
Consider
the set A = { a, b, c } and the set B = { 1, 2, 3, 4, 5 }?
(a)
How
many functions are there from A to B?
(b)
How
many functions are there from A to B that are injective?
(c)
How
many functions are there from A to B that are surjective?
(d)
How
many functions are there from set B to set A (from B = { 1, 2, 3, 4, 5 } to A = { a,
b, c }?
(e)
How
many functions are there from B to A that are not surjective?
2.
Let
the domain set for f and g be A = {1, 2, 3}. The three functions f and g and h are:
(a)
What
is the range of f o g
?
(b)
What
is the range of g o f
?
(c)
What
is the value of 
?
3.
What
properties does a POSET (partially ordered set) have?
4.
What
is the range of the hash function
f(x) = x mod 8 when the domain of the function is the following set of
values: {14, 7,
12, 21, 29,
80, 8}?
5.
Draw
the hash table for the above data and resolve collisions by the standard linear
probing with a step size of one. Assume
that the data arrives in the order shown, i.e. 14 was placed in the table 1st
and 8 was the last value inserted into the hash table.
6.
What
is the average successful search performance for your hash table? Please show your work.
7.
What
is the average unsuccessful search performance for your hash table? Please show your work.
8.
Draw
the graph of the following binary
relation on the set A = {2, 3, 4, 5, 6, 7}.
9.
What
properties does the above binary relation have? reflexive symmetric transitive antisymmetric
Circle all that it apply or that it satisfies.
10.
Let
R be a subset of the cross product (Cartesian product) of set A = {2, 3, 4, 5,
6, 7, 8, 9, 10, 11, 12}. The xRy definition is that x is related in
the R fashion to y means 2x = y. What
is the cardinality of R o R? The o in R o R is the composition operator.
11.
Draw
the binary search tree that would be created by inserting the same set of
numbers starting with 14 and ending with 80 and then 8: {14,
7, 12, 21, 29, 80,
8}?
12.
Calculate
the average successful search performance average for the binary search tree
that you drew above. Please show your
work there and/or here.