Discrete Structures BS 1 Semester/Term PU — University of the Punjab 2021

UNIVERSITY OF THE PUNJAB

B.S. in Computer Scionce First Semester: Fall 2021

Subject: Discrete Structures

Paper: CC-111

• Roll No.

s....

Time: 3 Hrs.

Marks: 60

Q.1. Give short answer to the following questions.

Express the following statement using quanti fiery,

"The product of two negative real numbers is not negative."

What is the least common multiple and greatest common divisor of 31835y% and 2431953?

Proof that 7a+2 will always be even if and only if n is even.

[2]

[2]

Let B be the set (1,2,3,4,5), In AXA: Which ordered pairs are in the relation R. = ((x,

b) | b divides [6]

a)? Also determin if the set is symmetric and reflexive. Also define the difference between symmetric,

reflexive and transitive relationships.

24T K659

What is the next term in the sequence: (3, 10, 38, 150, 5981g-117 12

Express above sequence using recurrence relations. Also clearly write initial value

(5]

Evaluate foliowing summations using n~2, m=3, c= 4 and b-5.2

1-［56jl+ze

Pr！

٢ ٤

What is the minimum number of students required in OOP class to be sure that at least five will

receive the same grade, if there are five possible grodes, A, B, C, D, and F?

What are the quotient and remainder when -13 is divided by 37

If (p V q)M-p) is true then evaluste the value of proposition q. also mention the rule of inference

that supports this deductive reasoning.

P٨ (٧V)

(2]

[2]

[2]

5114-［34152175］18

FY

Q.2. Answer the following questions.

15 1 +6خد

Use Mathematical Induction to prove the following formula for non-negative integers

1+2+22+2'+...+2°= 2*+1 - 1 for all non-negative integers n

Draw dual graph corresponding to the following map given as Figure • [13 = 3 + 1 + 1 + 2 + 3 +3]

and determine its chromatic number.

Figure a

Figure b

Then represent graph in Figure b using adjacency list and incidence matrix. Also calculate the degree of

each vertex. Furthermore, determine whether the graph contains Euler circuit/ Euler path, Hamiltonian

circuit/ Hamiltonian path. Cleary highlight the pethi

It if any-

Using counting and probability concepts, answer the following:

[9]

B。

How many different strings can be made by reordering the letters of the word SUCCESSION?

b.

Suppose that there are total of nine runners in a race. The winner receives a gold medal, the,

second place holder receives a silver medal, and the third-place holder receives a bronze medal.

How many different ways are there to award th

medals, if all possible outcomes of the race can

occur and there are no ties?

C.

How many permutations of the letters "ABRACADABRA" contain the string "ABRA"?

d.

A group of 20 people have been trained as physicians to go on a scientific discovery. How many

ways are there to select a crew of five people to go on this mission (assuming that all will have

the same job)?

What is the chance that afler throwing a dice, the value will be less than three?