Discrete Structures University Of Sargodha (UOS) 2025

>, ie Te YE a { Cor A

Ci REY HR NEE RRA | ii

~~ Yaper: Discrete Structures (CVir€ -2u5) : ade

NES aS ERS STIR Ta Fo pod

ap BERL EE fa Maximum Marks: 60

SER, 5 Cai ger Evry % ; 3 Ba 8 : Hy,

Note: Objective part i ‘compulsory. Attempt any three questions from subjective part. ~~

$4 gy ustrate your answer with diagram where needed): S00 ia

fess NC

3 Objects par (Compulsory) ot

Q.1. Write short answers of the following in 2-3 lines each on your answer sheet. 20 (2%12)

4

i. Give an example graph that has an Euler path and not an Euler cycles, ;

ii. Give an example graph that has a Hamiltonian circuit.

iii. Define “premise.”

iv. What is a vacuous proof?

i v. What is a bijection?

¢

vi. Give an example of a recurrence relation.

vii. What do you understand by “brute force”?

d

viii. What is the computational complexity of binary search algorithm?

ER

ix. Give an example of Mersenne prime.

Q.2.

n| ulsory. Attempt any three questions from subjective part.

‘answer with diagram where needed).

A CP

Object art (Compulsory) o®

Write short answers of the following in 2-3 lines each on your answer sheet. RN (2%12)

i. Give an example graph that has an Euler path and not an Euler cycler

v. What is a bijection?

vi. Give an example of a recurrence relation.

viii. What is the computational complexity of binary search algorithm?

ix. Give an example of Mersenne prime.

X. What is the inverse of 17 modulo 77

xi. Give a primitive root of a

7. 1 -~

xii. Define loop invari

bd

' Subjective Part (3*12)

The function f from {a, b, c, d} to itself is f(a) = b, f(b) = a, f(c) = d, f(d) = c. Discuss the

followings briefly.

a) Is f a surjection?

b) Is f an injection?

Give a “good” big-O estimate for the following;

log(2n1ogm)

Prove or disprove that, “For all integers », and all prime numbers p, if »* is divisible by p, then n is

divisible by p.”

gorithm to color an undirected graph G(V,E) with two colors.

t A is a nonempty set, and fis a function that has 4 as its domain. Let R be the relation

consisting of all ordered pairs (x, y) such thak{ (x) = f(»). Show that R is an equivalence

ion on

4. rr

a

Rod

LK-6491/03-06-25