Discrete Structures B.ED/BS 3 Semester/Term University Of Sargodha (UOS) 2023

University of Sargodha

BS 3rd Term Examination 2023

Subject: IT Paper: Discrete Structures (CMPC-205)

Time Allowed: 02:30 Hours

Maximum Marks: 60

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

Objective Part (Compulsory)

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

(2*12)

Eing tite conjunction of the propositions p and q where p is the proposition "Today is Friday" and q is

the proposition "It is raining today".

What are the negations of the statements" All goats are mammals"?

Draw Venn diagram for the symmetric difference of Set A - (1, 3,

5) and B - (1, 2, 3).

Define this function f(x) - (x+1)/(x'+2)- anto or one-to-one. Domain consist of all integers.

How many permutations of the letters ASSESSINATION contain the string SES?

How many comparisons are needed for a binary search in a set of 64 elements?

What is pigeonhole principle?

A =

and

0

" = (i !].

Find A0B.

ustadni.com

Find the least integer n such that f(x) is O(x") for each of these functions. f(x) = (x*+5logx) / (x'+1)

Define reflexive closure and symmetric closure.

Difference between tree and graph.

In a certain country, the car number plate is formed by 4 digits from the digits 1, 2, 3, 4, 5, 6, 7, 8 and

9 followed by 3 letters from the alphabet. How many number plates can be formed if neither the digits

nor the letters are repeated?

Q.2.

Q.3.

Q.4.

Q.5.

Subjective Part

(3*12)

Prove that following are logically equivalent by developing a series of logically equivalences.

i) -(p v (-pA

g)) and -p A -q

Use the divide and conquer algorithm to put 1, -1, 3, -7, 13, 31, 22, 4, 3 into ascending order.

How many permutations of the letters ABCDEFG contain?

i) The string BCD?

ii) The string CFGA?

iii) The strings BA and GF?

iv) The strings ABC and DE?

iv) the strings ABC and CDE?

vi) The strings CBA and BED?

Consider the following Wumpus world environment:

4

Player

Stench

3

Breeze

2

Pit

Breeze

Breeze

Wumpus

Stench

Breeze

Stench

Breeze

Pit

Breeze

4

Infer using rules of inference that the highlighted room is safe.

i) Draw a tree for following and run inorder tree traversal 1, 9, 8, 3, 12, 20, 15, 2

Ustadni Make a spanning tree of following graph. With all steps mentioned.

usta

- LK-6491/16-06-23 -

ustadni.com

Scanned with Camscanne

ustadni.com