# MAT2440 Discrete Structures & Algorithms I

Professor Kate Poirier, Spring 2017

# Page 2 of 9

1827 = 16 * 114 + 3

114 = 16 * 7 + 2

7 = 16 * 0 + 7

= (723) base 16

Check: 7 * 16^2 + 2 * 16^1 + 3 * 16^0 = (1827) base 10.

9d. Convert the answer from (c) to its octal expansion.

1827 = 8 * 228 + 3

228 = 8 * 28 + 4

28 = 8 * 3 + 4

3 = 8 * 0 + 3

= (3443) base 8

Check: 3 * 8^3 + 4 * 8^2 + 4 * 8^1 + 3 * 8^0 = (1827) base 10

a. Determine the prime factorization of 1078 and 2541
1078= 1078/2= 539/7 = 77/11 = 7
= 1078 = 11*7^2*2

2541 = 2541/3= 847/7 = 121/11 = 11
= 2541= 11^2*7*3

b)  determne the greatest common divisor

the common divisors are 3,  7, 11,  also 77 because 7*11= 77

77= gcd(1078,2541)

c)  determine the least common multiple

the common denominators 3 , 7, 11

3 = lcm(1078,2541)

9c. Convert the decimal expansion of (1827) base 10 to its binary expansion. Show your work.

1827 = 2 * 913 + 1

913 = 2 *456 + 1

456 = 2 * 228 + 0

228 = 2 *114 + 0

114 = 2 * 57 + 0

57 = 2 * 28 + 1

28 = 2 * 14 + 0

14 = 2 * 7 + 0

7 = 2 * 3 + 1

3 = 2 * 1 + 1

1 = 2 * 0 + 1

Check : (1 * 2^10 + 1 * 2^9 + 1 * 2^8 + 0 * 2^7 + 0 * 2^6 + 1 * 2^5 + 0 * 2^4 + 0 * 2^3 + 0 * 2^2 + 1 * 2^1 + 1*2^0) = (1827) base 10.

(1827) base 10 = (11100100011) base 2.

6. Use the Euclidean algorithm to determine the greatest common divisor of 1078 and 2541.  Show your work.

GCD (1078, 2541)

2541 = 2 * 1078 + 385

1078 = 2 * 385 +308

385 = 1 * 308 + 77

308 = 4 * 77 + 0

GCD (1078, 2541) = GCD (1078, 385) = GCD (385, 308) = GCD (308, 77) = GCD (77, 0) = 77

• Quiz #8 this Thursday will cover material/homework from sections 5.1 and 5.2.
• Test #3 will be given in class next Thursday, May 11. It will cover 4.5, 4.6, 10.1, 10.2, 10.4 , and 5.1-5.5.
• You are still welcome to add Test #2 Solutions posts to the OpenLab for participation credit; don’t forget to tag the “Test #2 Solutions” category.
• One of my homework problems from last Thursday’s class was to prove or disprove Kazi’s formula for 5.1 homework #10(a). I don’t have a record of my own boardwork from Thursday, so I can’t point out exactly where my mistake was. Kazi’s formula was correct. The proof is actually quite straightforward and I’ve attached a photo of my hand-written work to this post. Let me know if you have any questions.

FDQ VRPHRQH SRWHQWLDOOB EUHDN WKLV ?

I hope everyone had a good break!

• Our regular office hours and class hours resume tomorrow (Tuesday).
• Bring the files for your MATLAB assignment with you to class tomorrow.
• Quiz #7 on Thursday will cover material/homework from 4.5, 4.6, 10.1, 10.2, and 10.4.
• There is a forum on campus at 12:45 tomorrow for students with questions/concerns about immigration rights. Information here. If this issue affects you or someone you know, I encourage you to attend the forum.

YIDD ESWUE IAWHT FO?RT PILSM OEUEN OHGGT SEIUS SUSGE

ANSI NEOY SELE INSU LOBG CIKC ERHP

Theme by Anders NorenUp ↑