Download PTU B-Tech CSE-IT 2020 Dec 4th Sem 71106 Discrete Structures Question Paper

Download PTU (I.K.Gujral Punjab Technical University (IKGPTU)) B-Tech (Bachelor of Technology) (CSE-IT)- Computer Science Engineering -Information Technology 2020 December 4th Sem 71106 Discrete Structures Previous Question Paper

Roll No.
Total No. of Pages : 03
Total No. of Questions : 18
B.Tech. (CSE / IT) (2012 to 2017) (Sem.?4)
DISCRETE STRUCTURES
Subject Code : BTCS-402
M.Code : 71106
Time : 3 Hrs. Max. Marks : 60
INST RUCT IONS T O CANDIDAT ES :
1 .
SECT ION-A is COMPULSORY cons is ting of TEN questions carrying TWO marks
each.
2 .
SECT ION-B c ontains F IVE questions c arrying FIVE marks eac h and s tud ents
have to atte mpt any FOUR q ues tions.
3 .
SECT ION-C contains THREE questions carrying T EN marks e ach and s tudents
have to atte mpt any T WO questio ns.
SECTION-A
Answer briefly :
1.
Define Euler graph.
2.
Define ring with example.
3.
What is the minimum number of NOR gate required to construct AND gate? Also
construct it.
4.
Differentiate between graph and tree.
5.
Give an example of a semi group without an identity element.
6.
Give an example of Hamiltonian circuit.
7.
What is the number of vertices in a tree with n edges?
8.
State the principle of inclusion and exclusion.
9.
What are partial order relation?
10. Define graph coloring.
1 | M-71106
(S2)-811

---

SECTION-B
11. 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 ? A = universal relation
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.
12. 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.
13. Let a and b be integers. Find Q(2, 7), Q(5, 3), and Q(15, 2), where Q(a, b) is defined by:
5,
if a < b
Q(a, b) =
Q(a - b, b + 2) + a,
if a b
14. 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.
15. Find the general solution for third-order homogeneous recurrence relation
an = 6an?1? 12an?2 + 8an?3
SECTION-C
16. Show that Kn has H = (n -1)! /2 Hamiltonian circuits. In particular, find the number of
Hamiltonian circuits for the graph K5 in Figure 1.
B
A
C
E
D
Fig.1
2 | M-71106
(S2)-811

---

17. Suppose the preorder and inorder traversals of a binary tree T yield the following
sequences of nodes :
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
18. State and prove Euler's theorem in graph theory.
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.
3 | M-71106
(S2)-811

---