B.Tech 4th Semester Exam., 2022, Code: 100404
- (a) The statement (~P <->Q) ∧ ~Q is true, when
- (i) P: True, Q: False
- (ii) P: True, Q: True
- (iii) P: False, Q: True
- (iv) P: False, Q: False
- Answer: (iii) P: True, Q: False
- Explanation: Using Biconditional
- (b) Which of the following statements regarding sets is false?
- (i) A ∩ A = A
- (ii) A ∪ A = A
- (iii) A – (B ∩ C) = (A – B) ∪ (A-C)
- (iv) (A ∪ B)’ = A’ ∩ B’
- Answer: (iii) A – (B ∩ C) = (A – B) ∪ (A-C)
- Explanation: DeMorgan’s Law: (A ∪ B)’ = A’ ∩ B’
- (c) What is the induction hypothesis assumption for the inequality m!>2m where m≥ 4?
- (i) For m = k, k+1!>2k holds
- (ii) For m = k, k! > 2k holds
- (iii) For m = k, k! > 3k holds
- (iv) For m = k, k! > 2k+1 holds
- Answer: (ii) For m = k, k! > 2k holds
- Explanation: Induction hypothesis assumption for m! > 2m is m = k , k! > 2k holds
- (d) A simple graph can have
- (i) multiple edges
- (ii) self-loops
- (iii) parallel edges
- (iv) no multiple edges, self-loops and parallel edges
- Answer: (iv) no multiple edges, self-loops and parallel edges
- Explanation: By defination
- (e) An undirected graph has 8 vertices labelled 1, 2,…, 8 and 31 edges. Vertices 1, 3, 5, 7 have degree 8 and vertices 2, 4, 6, 8 have degree 7. What is the degree of vertex 8?
- (i) 15
- (ii) 8
- (iii) 5
- (iv) 23
- Answer: (iii) 5
- Explanation:
- (f) A graph which has the same number of edges as its complement must have number of vertices congruent to… or… modulo 4 (for integral values of number of edges).
- (i) 6k, 6k-1
- (ii) 4k, 4k+1
- (iii) k, k+2
- (iv) 2k+1, k
- Answer: (ii) 4k, 4k+1
- Explanation: Based on Graph Theory
- (g) A graph which consists of disjoint union of trees is called
- (i) bipartite graph
- (ii) forest
- (iii) caterpillar tree
- (iv) labelled tree
- Answer: (ii) forest
- Explanation: forest is graph which consists of disjoint union of trees.
- (h) Which of the following two sets are equal?
- (i) A = {1, 2} and B = {1}
- (ii) A = {1, 2} and B = {1, 2, 3}
- (iii) A = {1, 2, 3} and B = {2, 1, 3}
- (iv) A = {1, 2, 4} and B = {1, 2, 3}
- Answer: (iii) A = {1, 2, 3} and B = {2, 1, 3}
- Explanation: sets have the same elements without regard to order
- (i) If Cn is the nth cyclic graph, where n>3 and n is odd, determine the value of X(Cn)
- (i) 32572
- (ii) 16631
- (iii) 3
- (iv) 310
- Answer: (iii) 3
- Explanation: The chromatic number
- (j) The number of edges in a regular graph of degree 46 and 8 vertices is
- (i) 347
- (ii) 230
- (iii) 184
- (iv) 186
- Answer: (iii) 184
- Explanation:
B.Tech End Semester Examination – 2023, Code: 100404
(a) Let A be the set odd positive integers less than 10. Then cardinality of A, |A| is
- (i) 5
- (ii) 9
- (iii) 6
- (iv) 4
- Answer: (i) 5
- Explanation: A = {1,3,5,7,9}, cardinality of A = 5
(b) If m is the number of objects (pigeons) and n is the number of boxes (pigeonholes), then the function is both one-to one and onto if
- (i) m<n (ii) m=n (iii) m>n (iv) none of these
- Answer: (ii) m=n
- Explanation: This corresponds to the condition required for one-to-one correspondence between a set of pigeons and a set of pigeonholes.
(c) If A x B = B x A, (Where A and B are general matrices) then
- (i) A = d
- (ii) A = B
- (iii) B = A,
- (iv) A’ = B
- Answer: (ii) A = B
- Explanation: If the Cartesian product of A and B in one order is the same as the product in the reverse order, then A and B must be the same set.
(d) A partial ordered relation is transitive, reflexive and
- (i) Anti symmetric (ii) bi symmetric (iii) anti reflexive (iv) asymmetric
- Answer: (i) Anti symmetric
- Explanation: The three basic requirements of partial order are (1) reflexivity (x R x), (2) antisymmetry (if x R y and y R x, then x = y), and (3) transitivity (if x R y and y R z, then x R z)
(e) If B is a Boolean Algebra, then which of the following is true
- i. B is a finite but complemented lattice
- ii. B is a finite, complemented and distributive lattice
- iii. B is a finite, Distributive but not complemented lattice
- iv. B is not distributive lattice
- Answer: ii. B is a finite, complemented and distributive lattice
- Explanation: A Boolean Algebra always possesses complementary elements and distributes over union and intersection operations.
(f) P →q is logically equivalent to
- a) ¬p → q
- b) ¬q → ¬p
- c) ¬p ∧ q
- d) pvq
- Answer: b) ¬q → ¬p
- Explanation: Because the contrapositive of a conditional statement is logically equivalent to the original statement.
(g) if f(x) = cosx and g(x) = x3 then (fog) (x) is
- (i) (cosx)3
- (ii) cos3x
- (iii) x(cosx)
- (iv) cosx3
- Answer: (ii) cos3x
- Explanation: (f ∘ g)(x) = f(g(x)) = cos(x3) = cos(x3)
(h) The number of distinguishable permutations of the letters in the word BANANA are
- (i) 60
- (ii) 36,
- (iii) 20,
- (iv) 10
- Answer: (i) 60
- Explanation: the number of ways to arrange n objects where there are n1 of one kind, n2 of another kind, and so on, is n!/ (n1! * n2! * … * nk!)
(i) Which of the following pair is not congruent modulo 7?
- (i) 10, 24
- (ii) 25, 56
- (iii) -31, -15
- (iv) -64, -15
- Answer: (iv) -64, -15
- Explanation: The two numbers have the same remainders when divided by 7: i.e., a mod 7 = b mod 7.
(j) Let N = {1,2,3,……} be ordered by divisibility, which of the following subset is totally ordered
- (i) (2, 6, 24)
- (ii) (3, 5, 15)
- (iii) (2, 9, 16),
- (iv) (4, 15, 30)
- Answer: (i) (2, 6, 24)
- Explanation: A set N is ordered by divisibility. If subset is totally ordered, then every pair of elements must be divisible.
B.Tech 4th Semester Exam., 2018, Code: 211405
- (a) For any three sets A, B and C, which of the following statements is wrong?
- (i) A ∪ (B ∩ C) = (A ∪ B) ∩ C
- (ii) A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
- (iii) A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
- (iv) None of the above
- Answer: (i) A ∪ (B ∩ C) = (A ∪ B) ∩ C
- Explanation: Distributive Laws of Set Theory. Distributive law A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
- (b) Let A and B be two non-empty sets. Then the set of all ordered pairs (a, b), where a ∈ A and b ∈ B is called
- (i) product set
- (ii) poset
- (iii) binary set
- (iv) None of the above
- Answer: (i) product set
- Explanation: It’s a direct application of the definition of a product set
- (c) If (a, a) ∈ R or equivalently aRa, ∀ a ∈ A, then a relation R on a set A is called
- (i) equivalent
- (ii) reflexive
- (iii) symmetric
- (iv) anti-symmetric
- Answer: (ii) reflexive
- Explanation: As per properties.
- (d) Let A and B be finite sets with |A| = n and |B| = m. How many functions are possible from A to B with A as the domain?
- (i) n
- (ii) m^m
- (iii) m
- (iv) m^n
- Answer: (iv) m^n
- Explanation: Total |A| = n and Total |B| = m. Total numbers of function is = m^n
- (e) For the functions f and g defined by f(x) = x3 and g(x) = x2 + 1 ∀ x ∈ R, the value of (g ◦ f) (x) is
- (i) x2 + 1
- (ii) x3 + 1
- (iii) x6 + 1
- (iv) x5 + 1
- Answer: (iii) x6 + 1
- Explanation: Function Composition (g ◦ f) (x) = (x3)2 + 1 = x6 + 1
- (f) A group G is said to be Abelian (or commutative) if for every
- (i) a ∈ G
- (ii) a * b != b * a
- (iii) Both (i) and (ii)
- (iv) None of the above
- Answer: (iii) Both (i) and (ii)
- Explanation: It is directly from definition of abelian group.
- (g) If f:G→ G’ is a homomorphism, then which of the following it true?
- (i) f (e) = e
- (ii) f (e) = e’
- (iii) f (e) = 1
- (iv) f (e) >=
- Answer: (ii) f (e) = e’
- Explanation: It directly comes from the theorem and definition of homomorphic group.
- (h) For which of the following does there exist a tree satisfying the specified constraints?
- (i) A full binary tree with 31 leaves, each leaf of height 5
- (ii) A rooted tree of height 3 where every vertex has at most 3 children and there are 41 total vertices
- (iii) a full binary tree with 11 vertices and height 6
- (iv) A binary tree with 2 leaves and height 100
- Answer: (i) A full binary tree with 31 leaves, each leaf of height 5
- Explanation: By properties of tree
- (i) For which of the following does there exist a graph G (V, E, 4) satisfying the specified conditions?
- (i) A tree with 9 vertices and the sum of the degrees of all the vertices is 18
- (ii) A graph with 5 components, 12 vertices and 7 edges
- (iii) A graph with 5 components, 30 vertices and 24 edges
- (iv) A graph with 9 vertices, 9 edges and no cycles
- Answer: (i) A tree with 9 vertices and the sum of the degrees of all the vertices is 18
- Explanation: Based on properties of the tree.
- (j) The number of simple digraphs with |V|=3 is
- (i) 29
- (ii) 28
- (iii) 27
- (iv) 26
- (v) 25
- Answer: (ii) 28
- Explanation: Every digraph has two options for the number of simple digraphs with |V|=3 is 28.
B.Tech 4th Semester Exam., 2019
- (a) The statement p → q is logically equivalent to
- (i) p ∨ q
- (ii) p ∨ ¬q
- (iii) ¬ p ∨ q
- (iv) ¬ p → q
- Answer: (iii) ¬ p ∨ q
- Explanation: Based on Logical Equivalence.
- (b) The contrapositive of the conditional statement p → q is
- (i) q → p
- (ii) ¬ p → ¬ q
- (iii) ¬ p → q
- (iv) ¬ q → ¬ p
- Answer: (iv) ¬ q → ¬ p
- Explanation: By Properties
- (c) If A and B are two non-empty sets having n elements in common, then A × B and B × A will have how many elements in common?
- (i) n
- (ii) n^2
- (iii) n^4
- (iv) 2n
- Answer: (i) n
- Explanation: Consider intersection (A ∩ B)
- (d) If a set A has n elements, then how many relations will there on set A?
- (i) n^2
- (ii) 2^n
- (iii) 2^(n^2)
- (iv) 2n
- Answer: (iii) 2^(n^2)
- Explanation: Relations from a set A of n elements to itself is 2^(n^2)
- (e) If P(φ) represents the power set of φ, then n(P(P(P(φ)))) equal to
- (i) 1
- (ii) 2
- (iii) 3
- (iv) 4
- Answer: (iv) 4
- Explanation: power set formula applies
- (f) For the poset ([{3, 5, 9, 15, 24, 45); divisor of] the lub of (3, 5) is
- (i) 3
- (ii) 5
- (iii) 15
- (iv) 45
- Answer: (iii) 15
- Explanation: Based of the LUB properties
- (g) If (S,) is a monoid, where S = {1, 2, 3, 6} and * is defined by ab=lcm (a, b), where a, b ∈ S, then the identity element is
- (i) 1
- (ii) 2
- (iii) 3
- (iv) 6
- Answer: (i) 1
- Explanation: Every element when perform operation with identity, get that element self.
- (h) The total number of subgroups of group G of prime order is
- (i) 1
- (ii) 2
- (iii) 3
- (iv) 4
- Answer: (i) 1
- Explanation: Total number of subgroups =1
- (i) The number of edges in a bipartite graph with n vertices is at most
- (i) n^2/2
- (ii) n^2/4
- (iii) n^2
- (iv) 2n
- Answer: (i) n^2/2
- Explanation: Complete bipartite graph kn/2,n/2 has (n/2)*(n/2) = n^2/4
- (j) The number of pendant vertices of a full-binary tree is
- (i) (n+1)/2
- (ii) (n-1)/2
- (iii) (2n+1)/2
- (iv) (2n-1)/2
- Answer: (i) (n+1)/2
- Explanation: Full binary tree formula based
(2017 Paper)
- (a) The set of all real numbers under the usual multiplication operation is not a group since
- (i) multiplication is not a binary operation
- (ii) multiplication is not associative
- (iii) identity element does not exist
- (iv) zero has inverse no
- Answer: (iv) zero has inverse no
- Explanation: In group theory, each element should have inverse.
- (b) If R= {(1, 2), (2, 3), (3, 3)} be a relation defined on A = {1, 2, 3}, then R.R is
- (i) R itself
- (ii) {(1, 2), (1, 3), (3, 3)}
- (iii){(1, 3), (2, 3), (3, 3)}
- (iv) {(2, 1), (1, 3), (2, 3)}
- Answer: (iii){(1, 3), (2, 3), (3, 3)}
- Explanation: RR = ((1,3),(2,3),(3,3))
- (c) Pick out the correct statement(s):
- (i) The set of all 2 × 2 matrices with rational entries (with the usual operations of matrix addition and matrix multiplication) is a ring which has no nontrivial ideals.
- (ii) Let R = C[0, 1] be considered as a ring with the usual operations of pointwise addition and pointwise multiplication and let I = {f: [0, 1] →R | f(1/2) = 0}
- Then I is a maximal ideal.
- (iii) Let R be a commutative ring and let P be a prime ideal of R. Then R/P is an integral domain.
- (iv) None of the above is correct
- Answer: (ii) and (iii)
- Explanation: By defination
- (d) Let f and be the functions defined by f(x) =2x + 3 and g(x) =3x + 2. Then the composition of f and g is
- (i) 6x + 6
- (ii) 3x + 7
- (iii) 5x + 5
- (iv) 7x + 5
- Answer: (i) 6x + 6
- Explanation: (fog)(x) = f(g(x)) = 2(3x+2)+3 = 6x+7.
- (e) Among 200 people, 150 either swim or jog or both. If 60 swim and 60 swim and jog, then how many people jog?
- (i) 125
- (ii) 225
- (iii) 85
- (iv) 25
- Answer: (i) 125
- Explanation: Use formula of sets.
- (f) If a graph is a tree, then
- (i) it has 2 spanning trees
- (ii) it has only 1 spanning tree
- (iii) it has 4 spanning trees
- (iv) it has 5 spanning trees
- Answer: (ii) it has only 1 spanning tree
- Explanation: by defination tree has only 1 spanning tree
- (g) The relation R on the set of all integers, where (x, y) ∈ R if and only if xy > greater and equal to 1 is
- (i) anti-symmetric
- (ii) transitive
- (iii) symmetric
- (iv) both transitive and symmetric
- Answer: (iii) symmetric
- Explanation: XY =YX.
- (h) How many functions are there from a set with three elements to a set with two elements?
- (i) 6
- (ii) 8
- (iii) 12
- (iv) 7
- Answer: (ii) 8
- Explanation: Use function from a set with A elements to a set with B elements.
- (i) Which one of the following is correct for any simple connected undirected graph with more than 2 vertices?
- (i) No two vertices have the same degree
- (ii) At least two vertices-have-the-same. degree
- (iii) At least three vertices have the same degree
- (iv) All vertices have the same degree
- Answer: (ii) At least two vertices-have-the-same. degree
- Explanation: At least two vertices-have-the-same. degree
- (j) In an unweighted, undirected connected graph, the shortest path from a node S to every other node is computed most efficiently, in terms of time complexity, by
- (i) Dijkstra’s algorithm starting from S
- (ii) Warshall’s algorithm
- (iii) performing a DFS starting from S
- (iv) performing a BFS starting from S
- Answer: (iv) performing a BFS starting from S
- Explanation: Best to compute shortest path is BFS.