PTU B.Tech CSE 4th Semester May 2019 71106 DISCRETE STRUCTURES Question Papers

Roll No.

Total No. of Questions : 18 Total No. of Pages : 02

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

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

DISCRETE STRUCTURES

Subject Code : BTCS-402

M.Code: 71106

Time: 3 Hrs. Max. Marks : 60

INSTRUCTIONS TO CANDIDATES :

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

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.

SECTION-A

Answer briefly :

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

1. Demorgan's Law
2. Chromatic number of Kn graph (Complete Graph)
3. Group
4. B-Tree
5. Heaps

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

6. Complexity of binary search
7. Find distinct number permutations formed from all letters of word “ENGINEERING”
8. Simple graph
9. Total order relation
10. Commutative Ring

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

SECTION-B

11. How many bit strings of length 8 either start with 1-bit or ends with two bits 00?
12. Show that the intersection of two left ideals of a ring is again a left ideal of a ring.
13. Solve the recurrence relation an + 5an-1 + 6an-2 = 3n² - 2n + 1
14. Prove that a connected graph G is Eulerian if and only if all vertices are of even degree.

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

15. Prove distributive law for sets.

SECTION-C

16. Describe cut point, spanning tree and bridges each with example
17. Show that union of two subgroups is a subgroup if and only if one is contained in other.
18. Prove that sum of degree of all vertices in a graph is equal to twice the number of edges in G.

--- 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.