QuestionQuestion

Transcribed TextTranscribed Text

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

Solution PreviewSolution Preview

This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.

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.
Reflexive: R is not reflexive since if it were (3,3) should be in R and it is not
Irreflexive: R is not irreflexive: (1,1) is in R.
Symmetric: R is symmetric, since for every pair (x,y) also (y,x) is in R
Assymetric: R is not asymmetric since (2,1) and (1,2) are in R
Antisymmetric: R is not antisymmetric for the same reason: both (2,1) and (1,2) are in R
Transitive: R is transitive since if (x,y) and (y,z) are in R, then also (x,z) is in R.
For example: (4,1) and (1,4) are in R. So is (4,4). Checked for all other cases.

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? This creates 67 linked lists.
b) Compute h(5716379). 5716+379= 6095=65 (mod 67)
c) Computer h(3842137)= 3842+137= 3979=26 (mod 67)...
$2.00 for this solution

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

Find A Tutor

View available Discrete Math Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.

Decision:
Upload a file
Continue without uploading

SUBMIT YOUR HOMEWORK
We couldn't find that subject.
Please select the best match from the list below.

We'll send you an email right away. If it's not in your inbox, check your spam folder.

  • 1
  • 2
  • 3
Live Chats