Discrete Mathematics Questions

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), (4, 1), (4, 4)} Determine whether R is reflexive, irreflexive, symmetric, asymmetric, antisymmetric, or transitive. For each property, either explain why R has that property or give an example showing why it does not. 2) Suppose an online retailer identifies each member with a 7-digit account number. Define the hashing function h, which takes the first 4 digits of an account number as one number and the last 3 digits as another number, adds them, and then applies the mod-67 function. a) How many linked lists does this create? b) Compute h(5716379). c) Computer h(3842137). 3) Let A = {1, 3, 5, 15, 18} and R be defined by xRy if and only if x|y. You may copy/paste/move/resize the images below as needed for your digraph and Hasse diagram. a) Draw the digraph of A. b) Draw the Hasse diagram of A. c) Give a subset of B that is linearly ordered and contains at least three elements. 1 3 5 15 18 1 3 5 15 18 4) Use the following algebraic expression for this problem. You may copy/paste/move/resize the images below as needed for your graph. (30 points) 3(m + 6) – 5(n – 2) 3×m+6–5×n–2() a) Construct the tree of this algebraic expression. b) c) Show the results of performing a postorder search of the tree. Evaluate this postorder search expression when m = 4 and n = 7 and list each step of the solution. 5) With vertex A as the initial vertex, 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 ordered pairs) in the order in which you chose them. What is the total weight of your minimal spanning tree? 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. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16