Regulation: R-23

P.B.R. VISVODAYA INSTITUTE OF TECHNOLOGY & SCIENCE

(AUTONOMOUS)
(Affiliated to J.N.T.U.A, Approved by AICTE and Accredited by NAAC)
KAVALI – 524201, S.P.S.R Nellore Dist., A.P. India. Ph: 08626-243930
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING (CSE, CSE-AI, AI&ML, IOT)
CSE- IOT)
DISCRETE MATHEMATICS AND GRAPH THEORY (DM&GT)

S.NO CO COURSE OUTCOME

CODE
1 CO1 Apply mathematical logic to solve problems. (K3)
Understand the concepts and perform the operations related to sets, relations
2 CO2 and functions. Gain the conceptual background needed and identify structures
of algebraic nature. (K2)
3 CO3 Apply basic counting techniques to solve combinatorial problems. (K3)

4 CO4 Formulate problems and solve recurrence relations.(K3)

5 CO5 Apply Graph Theory in solving computer science problems.(K3)

QUESTION BANK

UNIT-I
MATHEMATICAL LOGIC
1.Let p, q and r be the prepositions, p: you have the flee
q: you miss the final examination [CO1, K1]
r: you pass the course
write the following prepositions into statement form,
(i) p→q (iv) p ᴠ q ᴠ r
(ii) ~p→r (v) (p → ~r ) v (q → ~r )
(iii) q→~r (vi) (p ᴧ q) ᴠ (~q ᴧ r )

2. a) Construct the truth table for (PQ)  (‫ך‬PQ) (P‫ ך‬Q) (‫ך‬P‫ ך‬Q). [CO1, K3]
b) What is a well- formed formula? what are the rules of the well- formed formula? [CO1, K1]

3.Obtain Principal conjunctive normal form and Principal Disjunctive normal form of the
Formula S is given by (‫ך‬P→R) (QP). [CO1, K2]

4. a) Show that an implication is logically equivalent to its contra positive. [CO1, K2]
b) Show that (‫ך‬PQ) (P‫ ך‬Q) is a tautology. [CO1, K2]

5. a) Prove that r( pq) is a valid conclusion from the set of premises
pq, q→r, p→m, ‫ך‬m. [CO1, K3]
b) Explain Rules of Inference. [CO1, K2]
 Regulation: R-23
6. a) Show that R→S can be derived from the premises P→(Q→S), ‫ך‬RP and Q. [CO1, K2]
b) Explain the term tautology? Show that [(p→(q→r)] →[(p→q) →(p→r)] is tautology? [CO1, K2]

7. a) Derive the following using CP rule, if necessary, P →(Q→R), Q → (R→S) ⇒P→ (Q→ S)
[CO1, K3]
b) Construct a truth table for (p→q) ↔ (~p v q) [CO1, K2]
8. a) Show that the formula Q ᴠ (Pᴧ‫ך‬Q) ᴠ (‫ך‬Pᴧ‫ך‬Q) is a tautology [CO1, K2]
b) Show that ‫(ך‬p v(‫ך‬pᴧq)) and ‫ך‬p ᴧ ‫ך‬q are equivalent. [CO1, K2]

SHORT ANSWER QUESTIONS (2-MARKS)

1. Define Tautology and Contradiction. [CO1, K1]

2. Construct the truth table for the compound statement(pq) ‫ך‬q. [CO1, K3]
3. Translate into symbolic form the statement “Jack and Jill went up the hill”. [CO1, K1]
4. Negate the following statements: (i) Ottawa is a small town.
(ii) Every city in Canada is clean. [CO1, K1]
5. Show that the propositions p → q and ¬𝑝q are logically equivalent. [CO1, K2]

UNIT-2 SET THEORY

1. a) State pigeonhole principle. [CO2,K2]

b) Define Lattice and write its properties. [CO2,K2]

2. a) Let f(x) = x+2, g(x) =x-2, h(x) = 3x for xR. Where R is the set of Real numbers.
Find gof, fog, fof, gog, foh, hog, hof, fohog. [CO2,K2]
b) If A = {,} and B = {1, 2, 3}. What are AB, BA, AA, BB an (AB) (BA). [CO2,K2]

3. a) Define i) Group ii) Semi group iii) subgroup iv) abelian group [CO2, K1]
b) Let f: R→R and g: R→R where R is set of real numbers.
Find fog & gof if f(x) = x²-2 and g(x) = x+4. [CO2, K1]

4. Prove that G= {-1,1, i, -i} is an abelian group under multiplication. [CO2,K2]

5. Show that (R, +) is an Abelian group. [CO2,K2]
6. (a) Describe i) onto function ii) one to one function
iii) bijective function iv) constant function [CO2,K2]
(b) Let f(x): x2 -3x+2. Find f(x2) and f(x+3)? [CO2,K2]

7.a) Show that G is an abelian group if and only if (ab)-1 = a-1b-1 for all a,b belongs to G [CO2, K2]
b) What is inverse function? Let f: R→R be defined by f(x) =3x-5 find f-1 [CO2, K2]

8. a) State and prove distributive inequalities of lattice. [CO2,K2]

b) Show that every chain is distributive lattice. [CO2,K2]
 Regulation: R-23

SHORT ANSWER QUESTIONS (2-MARKS)

1. If f: ZZ→Z is defined by f(x,y) = 2x+3y-6xy, compute f(-2,3) and f(-3,-5). [CO2, K1]
2. If A={1,2,3,4,5,6}, B={3,5,7,9}; Then find AUB& AB. [CO2, K1]
3. Define Recursive function. [CO2, K1]
4. Define Monoid with example. [CO2, K1]
5. Define Homomorphism & Isomorphism of groups. [CO2, K1]

UNIT-3 ELEMENTARY COMBINATORICS

1. a) A multiple-choice test has 15 questions and 4 choices for each answer. How many
ways the 15 questions be answer so that (i) Exactly 3 answers are correct?
(ii) at least 3 answers are correct. [CO3, K3]

b) Enumerate the number of non-negative integral solutions to the inequality

x1+x2+x3+x4+x5 19 [CO3, K3]
2. Find the number of distinguishable permutations of the letters in the following work [CO3, K3]

(i) BASIC (ii) STRUCTURES (iii) ENGINEERING (iv) MATHEMATICS

3. a) In how many ways 23 different books be given to 5 students so that 2 of the students will
have 4 books each and the other 3 will have 5 books each. [CO3, K3]
12 13 25
b) State Binomial theorem What is the coefficient of x y in the expansion (2x-3y) [CO3, K3]

4. Find the term which contains x11 and y4 in the expansion of (2x3-3xy2+z2)6 [CO3, K3]

5.Consider the word “TALLAHASSEE” then how many arrangements are there

(i) all A’s together

(ii) where no two letters A appear together.
(iii) Where the letters ‘S’ are together and the letters ‘E’ are together.
(iv) 4 of letters taken from “TALLAHASSEE”. [CO3, K3]

6.What is the principle of inclusion and exclusion? Determine the number of integers between
1 and 250 that are divisible by any of the integers 2,3,5 and 7 [CO3, K1]
7.a) In how many ways can you select atleast one king, if you choose 5 cards from a deck of
52 cards. [CO3, K3]
2 4.
b) Determine the coefficient of xyz in the expansion of (2x-y-z) [CO3, K3]

8.State the multinomial theorem. Find the coefficient of x5 y10z5w5 in the expansion of (x-7y+3z-w)25

[CO3,K1]

SHORT ANSWER QUESTIONS (2-MARKS)

1. Find the number of five permutations of a set with 9 elements. [CO3,K3]
2. How many different outcomes are possible by tossing 10 similar coins [CO3,K4]
3. How many different strings can be made from the letters “ABRACAPABRA” [CO3,K4]
4. Compute P(8,5) & C(6,3 ) [CO3,K1]
5. In how many ways can five children arrange themselves in a ring. [CO3,K4]
 Regulation: R-23

UNIT-4 RECURRENCE RELATIONS

1. a) Find the first five terms of the sequence defined by an =6an-1, a0=2 [CO4, K3]

b) Solve the recurrence relation 2an -3an-1 = 0, n1, a4 =8 [CO4, K3]

2. Solve the recurrence relation using generating functions

an -6an – 1+12an - 2 -8an - 3 = 0. [CO4, K3]

3. Find the solution to the recurrence relation an = 6an - 1 – 11an - 2 +6an - 3 with the initial conditions
a0 =2, a1=5, a2 =15. [CO4, K3]

4. Find the solution of the recurrence relation an = 6an - 1 - 9 an -2 + 3n [CO4, K3]

5. Solve the recurrence relation an + 5an-1 + 5 an-2 = 0 and a0 = 0 , a1= 2√5

using the characteristic roots. [CO4, K3]
6. Find the generating function of the following sequence
a) (i) 0, 1, -2 ,3 , -4…….. (ii) 0, 2, 6, 12, 20, 30, 42,…… [CO4, K3]

b) Find the sequence generated by (1-x)-1 + 5x3

7. Solve the recurrence relation an + 2 -4 an + 1 + 3an = -200, n0 and a0 =3000, a1=3300. [CO4, K3]

8. a) Solve the recurrence relation an = an - 1 + n where a0=2 by substitution. [CO4, K3]

b) Solve an = 7 an - 1 by recurrence relation given initial condition is a2=98 [CO4, K3]

SHORT ANSWER QUESTIONS (2-MARKS)

1. Explain general solution and particular solution of recurrence relation. [CO4, K3]

2. Differentiate homogeneous recurrence relation with non-homogeneous recurrence

relations [CO4, K2]

3. Solve the recurrence relation an+1 =4an given that a0=3. [CO4, K3]

4. Find the generating function for the sequence 1,1,0,1, 1……. [CO4, K3]

5. Discuss the applications of generating functions. [CO4, K2]

 Regulation: R-23

UNIT-5 GRAPHS

1. a) Define graph Isomorphism. Explain Isomorphism of two graphs with suitable examples. [CO5, K3]
b) Draw the binary tree for the sequence of numbers {2,1,5,6,8,9,7,3,4} [CO5, K3]
2. a) Define (i) Directed graph (ii) undirected graph (iii) Bi-partite graph [CO5, K1]
b) Explain incidence matrices with suitable examples. [CO5, K2]
3. Explain DFS algorithm with an example. [CO5, K2]
4. Explain BFS algorithm with an example. [CO5, K2]
5. Explain Kruskal’s algorithm to find minimal spanning tree with suitable example. [CO5, K2]
6. Explain Prim’s algorithm to find minimal spanning tree with suitable example. [CO5, K2]
7. a) Find how many edges in a graph in which having the 10 vertices and each vertex
having the degree 10. [CO5, K3]
b) Explain Euler and Hamiltonian graphs with example. [CO5, K2]
8. Explain the following a) graph b) simple graph c) degree of vertex
d) order & size e) regular graph f) complete graph [CO5, K2]

SHORT ANSWER QUESTIONS (2-MARKS)

1. Define Euler path and Euler circuit [CO5,K1]
2. Define spanning tree with an example [CO5,K1]
3. Define Multi graph with example [CO5,K1]
4. Define planar Graphs with example. [CO5,K1]
5. Define matrix representation of a graph with a suitable example. [CO5,K1]

*********ALL THE BEST*********