Discrete Structures MS Information Technology/MSc Information Technology/PhD Information Technology 2 Semester/Term University Of Sargodha (UOS) 2022

University of Sargodha

M.So. 2nd Term Examination 2022

Subject Information Technology

Paper: Dincrete Struerure (CMP-21422

Tine Allowed: 02:30 Hours

Maximum Marks: 60

Noter

Objective part is compulsory. Attempt any three questions from subjective part

Objective Part

(Compulsory)

Write short answers of the following in 2-3 lines cach on your answer sheet.

02*12)

Define Propositions

What is the negation of This is i boring course?

What Is

pote the statement "* >

5. What are the truth values of PrS) and PA?

• pigeonhole principle?

Vhat in the difference between binary tree and fell binary tree!

Deline Rooted Trees?

Let 4 be the set of odd positive integets less th

Ix.

What is the level of a vertex?

twistant.com..,

menco lan), whom a. is equal to (n/2)+ In/212

Define the converse and contrapositive of a conditional statement

ustadni.com

Q.2.

03.

Subjective Part

(3*12)

Les A = (0, 1.2. and and deline relations R, S, and Too A as follows

R - (10.00: (0. 1), (0.5), (1, 0), (1, 1), (3, 2), (5, 0), (5. 5),

S - ((0, 0): (0, 2), (0, 5), (2,5)).

T = ((0. 1) (2,5)).

a. leR reflexive? symunetrie? mansitive?

h. leS reflexive? symmetric? transitive?

c. Is T reflexive? symmetric7 transitive7

Define and explain the Kruskal's algorthi. Also Kruskal's algorithm to And a minimum spanning tree for the

weighted graph in following dingram.

DA.

a) Deicribe an algorithm that taki

an inpur a lit of mintegets and produces as output the largest difference obtained

by subtracting in integer in the list from the one following it.

b) Let/be the hoction from (a de) to (1. 2,

3) nuch that /

(a) = 2J/ (8) =3, and f(c) =1. Is /invertible, and if it is,

0.5

ustadni.com

a) Which of the aimple griphs in Figure have a Hanillion circuit or, IEnot, a Hamilton path?

b) Enrypt the mesauge CisCRETEM/Jstadni.com

Encryption function, and then transliting the numbers back into letters.

/m - (14p +

21) mod 26

06. a Use set buider nitation and logics equivalences to establish the fist De Morgan Law,

mates a sting the ter to adri, ling the gien

AN8= AUB.

b) Let /he the function from (w. 202) to 10.1,23) with /00-3/00=1,

Jou =0, and ra) = 2 Is/a bijection?

- EK-7023

visit website: ustadni.com