Download PTU B.Tech 2020 March CSE-IT 4th Sem BTCS 402 Discrete Structures Question Paper

FirstRanker.com

Roll No.

Total No. of Pages : 02

--- Content provided by⁠ FirstRanker.com ---

Total No. of Questions : 18

B.Tech. (CSE/IT) (2012 to 2017) (Sem.-4)

DISCRETE STRUCTURES

Subject Code : BTCS-402

M.Code : 71106

--- Content provided by FirstRanker.com ---

Time : 3 Hrs. Max. Marks : 60

INSTRUCTIONS TO CANDIDATES :

1. SECTION-A is COMPULSORY consisting of TEN questions carrying TWO marks each.
2. SECTION-B contains FIVE questions carrying FIVE marks each and students have to attempt any FOUR questions.
3. SECTION-C contains THREE questions carrying TEN marks each and students have to attempt any TWO questions.

--- Content provided by⁠ FirstRanker.com ---

SECTION-A

Answer briefly :

1. Define Poset.
2. Define Anti-symmetric relation.
3. Write General Inclusion-Exclusion principle.

--- Content provided by‌ FirstRanker.com ---

4. State Involution Law in Boolean algebra.
5. Find the number of distinct permutations that can be formed from all the letters of word ‘PROGRAMMING’.
6. Give an example of graph that has Euler's circuit but Hamiltonian circuit.
7. Define Cyclic Subgroup.
8. Write generating function of S(n) =2.7ⁿ, n > 0.

--- Content provided by⁠ FirstRanker.com ---

9. Define Directed Graph.
10. What is the difference between a graph and a tree?

SECTION-B

1. If R is equivalence relation on a set A, then show that R^-1 is also equivalence relation on A.
2. Reduce the following Boolean expressions to complete sum of products form:
   1. f(x,y,z)=x(y+z)

   --- Content provided by​ FirstRanker.com ---

   2. f(x, y,z) = z(x'+y) + z
3. Show that in group G, (xy)^-1 =y^-1x^-1 ?x,y?G.
4. Prove that in any graph :
   1. There are even number of vertices of odd degree.
   2. Sum of degree of all the vertices is even.

   --- Content provided by‌ FirstRanker.com ---

5. Define and give example of :
   1. Isomorphism
   2. Integral domain.

SECTION-C

--- Content provided by FirstRanker.com ---

1. Solve the recurrence relation by using generating function : S(n) = S(n -1) +S(n-2), where S(0) =1, S(1) = 1.
2. State and prove Euler's theorem in graph theory.
3. If {B,+,.,’} is Boolean Algebra, then :
   1. If x+y=x+z and x'+y=x'+z then y=z.
   2. If xy=xz and x'.y=x'.z then y=z.

--- Content provided by‍ FirstRanker.com ---

NOTE : Disclosure of Identity by writing Mobile No. or Making of passing request on any page of Answer Sheet will lead to UMC against the Student.

FirstRanker.com