Discrete Structures (URCO-5101/URCO-5102/URCO-5103)- Subject: CS/IT/SE UOS - ADP/BS 1st Semester Examination 2025

Subject: CS/IT/SE

Time Allowed: 02:30 Hours

University of Sargodha

ADP/BS 1" Semester Examination 2025

Paper: Discrete Structures (URCO-5101/URCO-5102/URCO-5103)

Maximum Marks: 60

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

(Illustrate your answer with diagram where needed).

Q.1.

Objective Part

(Compulsory)

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

Find dual of (p V

F) ^ (q V T).

ii.

Show that the conditional statement is tautology without using truth table

(2*12)

iii.

Write applications of minimum spanning tree.

Using laws of logic, show that - (-p^q) ^(p v q) = p.

V.

What is a Satisfiable statement?

vi.

vil.

Differentiate between a Function and a Relation.

viii.

What is complete graph? S

com

What do mean by best case complexity and worst complexity of an algorithm.

ix.

What do mean by necessaries and sufficient condition give an example?

x. - Show that -p®q) and p +> q are logically equivalent.

xi. . State Modus Ponen rule of Inference.

xii. Define depth of a Node in a Tree.

Subjective Part

(3*12)

0.2.

Let S(x) be the predicate "x is a student," F(x) the predicate "X is a faculty member," and A (x, y)

the predicate "x has asked y a question," where the domain consists of all people associated with

your school. Use quantifiers to express each of these statements.

i. Every student has asked Professor Gross a question. Yo (SCx) →

il. Some student has not asked any faculty member a question. 3x (S(x) ^ F(x) A(xsy)

1) → x Aujji, There is a faculty member who has asked every other faculty member a question. 3x (Cx?

Q.3.

Define a Function, describe One-to-one, Onto, Into and Bijective Functions. Give example of each

Q.4.

one with diagram.

How many license plates can be made using either two uppercase English letters followed by four

digits or two digits followed by four uppercase English letters?

Q.5.

0.6.

Encrypt the message HOMEWORK using RSA system with n=55 and e=18.

a) Draw graph with given Adjacency Matrix

3

1

3

0

4

2

1

3

3

4

0

0

1

2

b) Find Incidence Matrix of the Graph given below

ustadni

ustadni.com

LK-5091, 6180/28-04-25

ustadni.com