Reference no: EM13949453

1) Let A = {1, 2, 3, 4} and R be a relation on the set A defined by:

R = {(1,1), (1,2), (1,4), (2,1), (2,2), (3,3), (4,2), (4,4)}.

Determine whether R is reflexive, irreflexive, symmetric, asymmetric, antisymmetric, or transitive. If the relation fails to have a property, give an example showing why it fails in this case.

2) Suppose an online retailer identifies each member with a 6-digit account number. Define the hashing function h, which takes the first 3 digits of an account number as 1 number and the last 3 digits as another number, adds them, and then applies the mod-61 function.

a) How many linked lists does this create?

b) Compute h(158686)

c) Compute h(328981)

3) Let A = {1, 2, 3, 6, 12, 18} and R be defined by xRy if and only if x|y.

a) Draw the digraph of R. Below are images you can use to create the diagraph. You may copy/paste the arrow and alter the directions and length as needed.

b. Draw the Hasse diagram of R. Below are images you can use to create the diagraph. You may copy/paste the images and alter the directions and length as needed.

c. Give a subset of B of A that is linearly ordered with respect to R and contains at least three elements.

4)

a) Construct the tree of the algebraic expression:

8n - 2(m + 1)

b) Perform a preorder search of the tree to write this expression in prefix form.

c) Evaluate the prefix expression when m = 5 and n = 3 and list each step of the solution.

5) Use vertex A as the initial vertex and use Prim's algorithm to find a minimal spanning tree for the following diagram. You do not need to draw the tree, but do list the edges (as an ordered pair) in the order in which they are chosen.

Edges:

6) Use Fleury's algorithm to produce an Euler circuit for the following graph. Start at A and label the edges in the order that you add them.