Assignment1 Relation Function PDF

Preview

Summary

Name: NIM: Class: Assignment 1: Relation, Function, and Recurrence Discrete Mathematics - A (MSH1A3) Second Term 2016-2017 Instructions: 1. This assignment is due Thursday February 16 at 5:00 p.m.. Please submit your work at School of Computing academic roster (roster akademik Fakultas Informatika),...

Description

Name:

NIM:

Class:

Assignment 1: Relation, Function, and Recurrence Discrete Mathematics - A (MSH1A3) Second Term 2016-2017 Instructions: 1. This assignment is due Thursday February 16 at 5:00 p.m.. Please submit your work at School of Computing academic roster (roster akademik Fakultas Informatika), room A203A (building A room A203A). Do not forget to write your identity on the space provided. You may submit this assignment as of Monday February 13 at 8:00 a.m.. 2. In order to prevent any academic misconduct, you also need to submit a readable scan or photograph of this assignment to the provided submission slot in IDEA. Please contact your class instructor for more detailed information. The due date of this online submission is the same as the hardcopy. Please make sure that your file size do not exceed the maximum file size allowed. 3. To save paper, you may print and reproduce this assignment double-sided. 4. Your answers should be handwritten. You may use: HB or 2B pencil, or pen with blue or black ink. 5. All problems in this assignment are adapted from the textbooks. The problems are written in English. If you are a student in a regular class, you may answer the problems in Bahasa. However, if you are a student in international class, your answers must be written in English – otherwise your assignment will not be graded. You may ask your class instructor or teaching assistant for helping you understanding the problem, but you should not ask them to give the solution of any problem. 6. Write your solutions on the space provided. If you need more space, you may use additional A4 papers and attach them to your assignment. 7. Be neat and write legibly. You will be graded not only on the correctness of your answers, but also on the clarity with which you express them. 8. This assignment consists of 9 problems, Problems 1, 2, and 5 are worth 12 points each, Problems 3 and 4 are worth 8 points each, Problems 7, 8, and 9 are worth 10 points each, and Problem 6 is worth 18 points. 9. Please retain yourself from copying answers from elsewhere without understanding the steps. This assignment is an individual evaluation. 10. Important: late submission without reasonable explanation will not be graded.

page 1 of 10

Problem 1 (12 points) Suppose R is a relation on the set of all integers where aRb if and only if a b = 0, for a; b 2 Z. Complete the following table for the property of R and provide a relevant reason for each answer. Property Yes/ No (0.5 point) Part a)

Reflexive

b)

Irreflexive

c)

Symmetric

d)

Asymmetric

e)

Anti-symmetric

f)

Transitive

Each justification is worth 1.5 points. A NSWER :

page 2 of 10

Name:

NIM:

Class:

Problem 2 (12 points) Suppose R is the relation on A = f1; 2; 3; 4g represented by the following digraph

Digraph for R. Complete the following table for the property of R and provide a relevant reason for each answer. Part Property Yes/ No (0.5 point) a)

Reflexive

b)

Irreflexive

c)

Symmetric

d) e)

Asymmetric Anti-symmetric

f)

Transitive

Each justification is worth 1.5 points. A NSWER :

page 3 of 10

Problem 3 (8 points) Suppose R and S are two relation defined on A = f1; 2; 3g represented by the following digraph:

Digraph for R

Digraph for S

(a). [2 points] Write the matrices that correspondingly represent the relation R and S (i.e., MR and MS ). (b). [2 points] Write the matrices that correspondingly represent the relation R[S and R\S (i.e., MR[S and MR\S ). (c). [2 points] Write the matrices that correspondingly represent the relation R (or :R) and S MR and MS

1

1

(i.e.,

).

(d). [2 points] Write the matrices that correspondingly represent the relation R S and S R (i.e., MR and MS R ). A NSWER :

page 4 of 10

S

Name:

NIM:

Class:

Problem 4 (8 points) Suppose R and S are two relation on A = f1; 2; 3; 4g defined as follows: aRb if and only if a

2b, for a; b 2 A

aSb if and only if a + b is odd, for a; b 2 A . (a). [2 points] Write the relation R and S in ordered pairs notation (set notation). (b). [2 points] Write the relation R (c). [2 points] Write the relation (S

1

and S R)

1

1

in ordered pairs notation (set notation).

and R

1

S

1

in ordered pairs notation (set notation).

(d). [2 points] Draw the digraph that represent the relation (S

R)

1

and S

R

1

.

A NSWER :

page 5 of 10

Problem 5 (12 points) Suppose g = f(1; b) ; (2; c) ; (3; a) ; (4; b)g is a function from A = f1; 2; 3; 4g to B = fa; b; c; dg and f = f(a; q) ; (b; r) ; (c; p) ; (d; s)g is a function from B = fa; b; c; dg to C = fp; q; r; sg. (a). [3 points] Determine whether g is: (1) injective, (2) surjective, and (3) bijective. Explain your answer! (b). [3 points] Determine whether f is: (1) injective, (2) surjective, and (3) bijective. Explain your answer! (c). [3 points] Write the function f (d). [3 points] Determine whether f answer! A NSWER :

page 6 of 10

g : A ! C in ordered pairs notation. g is: (1) injective, (2) surjective, and (3) bijective. Explain your

Name:

NIM:

Class:

Problem 6 (18 points) Suppose f; g; h : Z ! Z are function defined as follows: f (n) = 2n, g (n) =

jnk 2

, and h (n) = (f

g) (n) .

(a). [6 points] Determine whether f is: (1) injective, (2) surjective, and (3) bijective. Explain your answer! (b). [6 points] Determine whether g is: (1) injective, (2) surjective, and (3) bijective. Explain your answer! (c). [6 points] Determine whether h is: (1) injective, (2) surjective, and (3) bijective. Explain your answer! A NSWER :

page 7 of 10

Problem 7 (10 points) Verify whether each of the following functions is a bijection. If so, determine its inverse. (a). [5 points] f : Z ! Z where f (n) = n + 17, for all n 2 Z. (b). [5 points] g : Q ! Q where g (x) = 12 x A NSWER :

page 8 of 10

3, for all x 2 Q.

Name:

NIM:

Class:

Problem 8 (10 points) The running time of a particular recursive algorithm for an input of size n kB is expressed with the following recurrence Tn = 6Tn

1

8Tn

2,

with T0 = 0 and T1 = 1.

(1)

(a). [3 points] Calculate T2 , T3 , and T4 . (b). [3 points] Write the characteristics polynomial that corresponds to (1) and determine its roots. (c). [3 points] Find the general solution of (1) with initial conditions T0 = 0 and T1 = 1. (d). [1 point] Use the solution in (c) to express T10 . A NSWER :

page 9 of 10

Problem 9 (10 points) The running time of a particular recursive algorithm for an input of size n kB is expressed with the following recurrence Tn = 8Tn

1

16Tn

2,

with T0 = 0 and T1 = 1.

(a). [3 points] Calculate T2 , T3 , and T4 . (b). [3 points] Write the characteristics polynomial that corresponds to (2) and determine its roots. (c). [3 points] Find the general solution of (2) with initial conditions T0 = 0 and T1 = 1. (d). [1 point] Use the solution in (c) to express T10 . A NSWER :

page 10 of 10

(2)...