This download link is referred from the post: PTU B.Tech Question Papers 2020 December (All Branches)
FirstRanker.com
Firstranker's choice
B.Tech. (CSE / IT) (2012 to 2017) (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 ---
- SECTION-A is COMPULSORY consisting of TEN questions carrying TWO marks each.
- SECTION-B contains FIVE questions carrying FIVE marks each and students have to attempt any FOUR questions.
- 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 ---
- Define Euler graph.
- Define ring with example.
- What is the minimum number of NOR gate required to construct AND gate? Also construct it.
- Differentiate between graph and tree.
- Give an example of a semi group without an identity element.
- Give an example of Hamiltonian circuit.
- What is the number of vertices in a tree with n edges?
- State the principle of inclusion and exclusion.
- What are partial order relation?
- Define graph coloring.
--- Content provided by FirstRanker.com ---
--- Content provided by FirstRanker.com ---
FirstRanker.com
SECTION-B
- Consider the following five relations on the set A = {1, 2, 3}:
R={(1,1),(1,2),(1,3),(3,3)}, & = empty relation
S={(1,1),(1,2), (2, 1),(2,2),(3,3)}, A x A = universal relation--- Content provided by FirstRanker.com ---
T={(1,1),(1,2),(2,2), (2, 3)}
Determine whether or not each of the above relations on A is : (a) reflexive; (b) symmetric; (c) transitive; (d) antisymmetric. - Consider all integers from 1 up to and including 100. Find the number of them that are:
a) Odd or the square of an integer;
b) Even or the cube of an integer. - Let a and b be integers. Find Q(2, 7), Q(5, 3), and Q(15, 2), where Q(a, b) is defined by:
Q(a,b)=5 & \text{if } a < b \\ Q(a-b,b+2)+a & \text{if } a \geq b \cases> - Let G be any (additive) abelian group. Define a multiplication in G by a * b = 0 for every a, b ∈ G. Show that this makes G into a ring.
- Find the general solution for third order homogeneous recurrence relation
an = 6an-1 - 12an-2 + 8an-3
--- Content provided by FirstRanker.com ---
--- Content provided by FirstRanker.com ---
SECTION-C
- Show that Kn has (n-1)! /2 Hamiltonian circuits. In particular, find the number of Hamiltonian circuits for the graph K5 in Figure 1.
Fig.1 - Suppose the preorder and inorder traversals of a binary tree T yield the following sequences of nodes :
--- Content provided by FirstRanker.com ---
Preorder: G, B, Q, A, C, K, F, P, D, E, R, H
Inorder: Q, B, K, C, F, A, G, P, E, D, H, R
a) Draw the diagram of T.
b) Find depth d of T - State and prove Euler’s theorem in graph theory.
--- 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
--- Content provided by FirstRanker.com ---
This download link is referred from the post: PTU B.Tech Question Papers 2020 December (All Branches)