SIT192: Discrete Mathematics Assignment 2 Solution - Trimester 1, 2019

This document presents a comprehensive solution to a Discrete Mathematics assignment (SIT192), addressing various core concepts. The solution begins by analyzing different types of functions, determining whether they are one-to-one and onto, with detailed justifications. It then demonstrates the bubble sort algorithm to arrange a set of numbers in ascending order and calculates the number of comparisons. The solution also includes proofs using witnesses to determine the Big O notation of given functions. Furthermore, the assignment covers prime factorization, calculating greatest common divisors (GCD) and least common multiples (LCM), finding modulo values, converting numbers to different bases, and applying the Euclidean Algorithm. Finally, the solution concludes with matrix operations, including multiplication and transposition, providing a complete and detailed response to the assignment's requirements.

1
Discrete Mathematics
Student Name
Institution Name

2
1. Onto and 1:1 function
i. f : R → R where f ( x )=−3 x +7
1 :1
For any real number x, the image f(x) should be a unique number. Since
f ( x )=ax+ b, the function is 1:1. That is to say
f ( 1 ) =−3 ( 1 ) + 7 and f ( 2 ) =−3 ( 2 ) +7
thisgivesf ( 1 )=f ( 2 ) be 1=2
The function is 1:1
Onto
y=f ( x )
y=−3 x +7
x= 7− y
3
thisequation , foreveryy ∈ R ,thereexistatleastonex ∈ R hence f is onto
The function is thus onto and 1:1
ii. f : Z → Z where f ( x )=2 x−3
1 :1
From all the values of x the image is unique if the function f ( x ) =ax+ b. The
function is thus 1:1
Onto
y=f ( x )
y=2 x−3
x= y +3
2
In this equation there exist y ∈ Z or which x ≠ Z. The function is not onto.
The equation is 1:1 but is not onto
iii. f : R → R where f ( x )=4 x2−1
1:1

3
From a function to be 1:1, different values if x must have unique images, in this
case its evident that x=2 , ∧ x=−2 both have a similar image 15. The function is
therefore not 1:1.
Onto
y=f ( x )
y=4 x2−1 hence x= √ y+ 1
4
forafunctionbeontoforeverynumbery ∈ Rtheremustexistx ∈ R .
If we take an example of y=−10 , x= √−2.25 which is nit a real number. The
function is not onto
The function is therefore not both onto and 1:1
iv. f : A → B where f ( x )=2 x2+ 5
A={−5,0,2,5
B={5,13,55
1 :1
The values x=5 ∧ x=−5 both ave the same image y=55, hence not 1:1
Onto
y=f ( x )
y=2 x2+ 5
x= √ y−5
2
Forallthevaluesofy ∈ Bthereexistx ∈ Aasthedomain ,hencethefunctionisonto
The function is therefore onto but not 1:1
2. Bubble sort
To apply the bubble sort algorithm to arrange the numbers is ascending order we first
arrange the numbers in a table array as shown
91 68 52 77 14 18
0 1 2 3 4 5

4
We thereafter after scan this array rows several times swapping the numbers to make the
bigger number appear of the right side
1st swap
68 91 77 14 18 520
0 1 2 3 4 5
2nd swap
68 77 14 18 91 520
0 1 2 3 4 5
3rd swap
68 14 18 77 91 520
0 1 2 3 4 5
4th swap
14 18 68 77 91 520
0 1 2 3 4 5
Hence the number when arranged into an ascending order we have 14, 18, 68, 77, 91 and
520
The number of comparisons made are given by the formula 2∗n∗( n−1 ). Since n=6
We have 2∗6∗5=60
3. Prove by finding witnesses
Proof of the big Oh is given by
f ( x ) isO ( g ( x ) ) if for a valueC∧n0
We can find the values
f ( x ) ≤Cg ( x ) for all x > x0
lets say for C=1
i. f ( x ) =3 x3 +7 x2 logx+15 x−10

5
x 3 x3+7 x2 logx+15 x−10 x3
0 -10 < 0
Since at x=0 , the function f ( x ) ≤Cg ( x ) holds, we can conclude that by using a
witness the function f ( x )=3 x3 +7 x2 logx+15 x−10 is O( x3).
ii. f ( x )=5 x4 +7 x2−3 x−6 O ( x2 )
x 5 x4 +7 x2−3 x−6 x3
0 -6 < 0
Being that at x=0 , the function ( x ) ≤ Cg ( x ) holds it can be concluded that
f ( x )=5 x4 +7 x2−3 x−6 is O(x3)
4. Prime factorization
i. 637
7∗¿ 13
72∗131
The prime factors are 7,7,13
ii. 767
13∗59
131∗591
hencethevaluesare 13 and 59
iii. 841
29∗29
292
thevaluesare 29,29
iv. 1375
5∗5∗5∗11
53∗111
Thevalues are 5,5,5,11

6
v. 1581
3∗17∗31
31∗171∗311
Whichare3, 17, 31
vi. 10693
17∗17∗37
172∗37
5. GCD and LCM
i. 400 and 500
GCD
The factors of 400 are: 1, 2, 4, 5, 8, 10, 16, 20, 25, 40, 50, 80, 100, 200, 400
The factors of 500 are: 1, 2, 4, 5, 10, 20, 25, 50, 100, 125, 250, 500
Then the greatest common factor is 100
LCM
IS given by the formula
LCM ( a , b ) = ( a .b )
GCD ( a ,b )
for 400 ∧500 it gives 2000
ii. 2023 and 12103
GCD
The factors of 2023 are: 1, 7, 17, 119, 289, 2023
The factors of 12103 are: 1, 7, 13, 19, 49, 91, 133, 247, 637, 931, 1729, 12103
Then the greatest common factor is 7.
LCM
We have 3497767

7
iii. 24∗32∗134∗292 ∧ 2∗3∗13
GDC
13
LCM
2∗3∗13=78
6. Find modulo
Modulo is the remainder when a number is divided by the other
i. 81 mod 7
81
7 =11rem 4
The solution is 4
ii. -81 mod 7
¿− 81
7 =−11rem−4
−4 is therefore the solution
Ans -4
iii. -17 mod 5
¿−17
5 =−3 rem−2
Giving -2
iv. 550 mod 624
¿ 550
624 =1423362852 rem 160
Gives 160
7. Convert to base 10
a)
i. (13614)7
1 3 6 1 4
74 73 72 71 70
2401 343 49 7 1

8
Hence ( 2401∗1 ) + ( 3∗343 ) + ( 6∗49 ) + ( 7∗1 ) + ( 4∗1 ) =¿(3735)10
ii. (1001120302)4
1 0 0 1 1 2 0 3 0 2
49 48 47 46 45 44 43 42 41 40
1262144 4096 1024 256 16 1
Hence, we have
262144+ 0+0+ 4096+1024+ ( 2∗256 ) + ( 3∗16 ) +0+2=2678267
b) (756)10
i. To base 2
23 22 21 20
8 4 2 1
94 1
Thus gives (941)2
ii. To base 3
34 33 32 31 30
81 27 9 3 1
9 1
We therefore have (91)4
iii. To base 6
63 62 61 60
216 36 6 1
3 3
Thus gives (33)6
8. Use the Euclidean Algorithm
i. 1463 and 2737
2723=1463∗q +r

9
146381+1274
1463=1274∗1+189
1274=189∗6+140
189=140∗1+ 49
140=49∗2+ 42
49=42∗1+7
42=7∗6+0
Hence the GCD of 1463 and 2737 is 7
ii. 2277 and 2457
2457=2277∗1+180
2277=180∗12+117
180=117∗1+63
117=63∗1+54
63=54∗1+ 9
54=9∗6+0
The GCD is thus 9
9. Matrix
A=[1 −1 5
3 0 1 ]
B= [ 0 2
−1 −2 ]
i. BA
B∗A
[ 0 2
−1 −2 ]∗
[1 −1 5
3 0 1 ]= [ 6 0 2
−7 1 −7 ]
ii. AB
[ 1 −1 5
3 0 1 ]∗[ 0 2
−1 −2 ]
This matrices are not compatible hence cannot be multiplied.
iii. AT B

10
AT =¿]
Hence=¿]*[ 0 2
−1 −2 ] = [
−3 −4
0 −2
−1 8 ]
iv. B2
[ 0 2
−1 −2 ]∗
[ 0 2
−1 −2 ] =
[ −2 −4
2 2 ]
v. B3=B2∗B
[ −2 −4
2 2 ]*[ 0 2
−1 −2 ] = [ 4 4
−2 0 ]
vi. AAT =[1 −1 5
3 0 1 ]∗
[ 1 3
−1 0
5 1 ]=[27 8
8 10 ]