Previous Year Questions
Sample Questions
UNIT I LOGIC AND PROOFS
1. What is the negation of the statement "All cats can fly"?
a) No cats can fly
b) Some cats can't fly
c) All cats can't fly
d) Some cats can fly
Answer: c) All cats can't fly
2. Which of the following is a propositional variable?
a) 2+2=4
b) p implies q
c) (x+1)(x-1)=x^2-1
d) There are no unicorns.
Answer: b) p implies q
3. Which of the following is a tautology?
a) p xor q
b) p implies q
c) p and (not p)
d) p or (not p)
Answer: d) p or (not p)
4. What is the contrapositive of the statement "If it rains, then I stay inside"?
a) If I don't stay inside, then it doesn't rain.
b) If I stay inside, then it doesn't rain.
c) If it doesn't rain, then I don't stay inside.
d) If it doesn't rain, then I stay inside.
Answer: b) If I don't stay inside, then it doesn't rain.
5. Which of the following is equivalent to "not (p or q)"?
a) not p and not q
b) not p or not q
c) p and q
d) p or q
Answer: a) not p and not q
6. What is the conclusion of a proof?
a) The statement being proven
b) The assumptions of the proof
c) The logical reasoning used in the proof
d) The definition of key terms in the proof
Answer: a) The statement being proven
7. Which of the following is an example of a vacuous proof?
a) Proving that 2+2=5
b) Proving that all even numbers are divisible by 3
c) Proving that there are no unicorns
d) Proving that all odd numbers are prime
Answer: d) Proving that all odd numbers are prime
8. Which proof strategy involves assuming the negation of the statement being proven and deriving a
contradiction?
a) Direct proof
b) Proof by contraposition
c) Proof by contradiction
d) Proof of equivalence
Answer: c) Proof by contradiction
9. Which of the following is an example of a counterexample?
a) Proving that all prime numbers are odd
b) Proving that all cats have fur
c) Proving that all functions are continuous
d) Showing that 2 is not a solution to the equation x^2=3x
Answer: d) Showing that 2 is not a solution to the equation x^2=3x
10. Which of the following is a valid propositional equivalence?
a) p and q = p or q
b) p implies q = q implies p
c) p xor q = not p
d) p and (not p) = p or (not p)
Answer: d) p and (not p) = p or (not p)
11. Which of the following is a universal quantifier?
a) There exists
b) For all
c) Implies
d) Or
Answer: b) For all
12. Which of the following is a valid existential quantifier?
a) For all
b) There exists
c) Implies
d) Or
Answer: b) There exists
13. What is the converse of the statement "If it is raining, then the streets are wet"?
a) If the streets are wet, then it is raining.
b) If it is not raining, then the streets are not wet.
c) If the streets are not wet, then it is not raining.
d) If it is wet outside, then it is raining.
Answer: a) If the streets are wet, then it is raining.
14. Which of the following is an example of a trivial proof?
a) Proving that 2+2=4
b) Proving that all prime numbers are odd
c) Proving that all even numbers are divisible by 3
d) Proving that all cats have fur
Answer: a) Proving that 2+2=4
15. Which proof strategy involves showing that the statement being proven is false by finding a specific example that contradicts it?
a) Direct proof
b) Proof by contraposition
c) Proof by contradiction
d) Proof by counterexample
Answer: d) Proof by counterexample
16. Which of the following is an example of a mistake in a proof?
a) Starting with false assumptions
b) Using valid logical reasoning
c) Using a proof by contradiction
d) Deriving the correct conclusion
Answer: a) Starting with false assumptions
17. Which of the following is equivalent to "not (p implies q)"?
a) p and not q
b) not p and not q
c) p and q
d) not p or q
Answer: a) p and not q
18. What is the hypothesis of a proof?
a) The statement being proven
b) The assumptions of the proof
c) The logical reasoning used in the proof
d) The definition of key terms in the proof
Answer: b) The assumptions of the proof
19. Which proof strategy involves showing that if the negation of the statement being proven is true, then a contradiction arises?
a) Direct proof
b) Proof by contraposition
c) Proof by contradiction
d) Proof of equivalence
Answer: b) Proof by contraposition
20. Which of the following is a valid propositional equivalence?
a) p and q = q or p
b) p implies q = not p or q
c) p xor q = not p and not q
d) p or (not q) = not (p and q)
Answer: d) p or (not q) = not (p and q)
UNIT II RECURRENCE RELATIONS
21. What is a recurrence relation?
A) A mathematical equation that describes a sequence of numbers
B) A function that maps elements of one set to another set
C) A binary operation on a set that is associative, commutative, and has an identity element
D) A relation between two sets that assigns to each element of the first set a set of elements from the second set
Answer: A
22. Which of the following is an example of a recurrence relation?
A) f(x) = 3x + 2
B) g(x) = x^2 + 1
C) h(n) = h(n-1) + 3
D) i(x) = sin(x)
Answer: C
23. How can recurrence relations be used to model real-world phenomena?
A) By describing the behavior of a system over time
B) By mapping the inputs and outputs of a function
C) By creating a graph of a set of data points
D) By computing the average of a set of numbers
Answer: A
24. What is a homogeneous linear recurrence relation with constant coefficients?
A) A recurrence relation where all the coefficients are equal
B) A recurrence relation where all the terms are of the same degree
C) A recurrence relation where the coefficients are constants and the non-homogeneous term is zero
D) A recurrence relation where the coefficients depend on the previous terms
Answer: C
25. Which of the following is an example of a homogeneous linear recurrence relation with constant coefficients?
A) f(n) = n^2 + 2n + 1
B) g(n) = 2g(n-1) + 3g(n-2)
C) h(n) = 3^n
D) i(n) = sin(n)
Answer: B
26. What is the method of inverse operator used for?
A) To solve a non-homogeneous linear recurrence relation with constant coefficients
B) To find the inverse of a matrix
C) To compute the derivative of a function
D) To determine the limit of a sequence
Answer: A
27. Which of the following is not a step in solving a non-homogeneous linear recurrence relation with constant coefficients using the method of inverse operator?
A) Find the homogeneous solution
B) Find the particular solution
C) Solve for the constants using the initial conditions
D) Substitute the particular solution into the recurrence relation
Answer: A
28. What is a generating function?
A) A function that generates a sequence of numbers
B) A function that generates a set of polynomials
C) A function that generates a set of matrices
D) A function that generates a set of functions
Answer: B
29. How can generating functions be used to solve recurrence relations?
A) By finding the inverse of the generating function
B) By computing the Taylor series of the generating function
C) By manipulating the generating function algebraically
D) By taking the limit of the generating function as n approaches infinity
Answer: C
30. Which of the following is the generating function for the Fibonacci sequence?
A) f(x) = 1/(1-x)
B) g(x) = 1/(1-x-x^2)
C) h(x) = 1/(1-2x)
D) i(x) = x/(1-x-x^2)
Answer: B
31. What is the difference between a linear and a nonlinear recurrence relation?
A) A linear recurrence relation involves a linear combination of the previous terms, while a nonlinear recurrence
relation involves a nonlinear combination of the previous terms
B) A linear recurrence relation involves only one previous term, while a nonlinear recurrence relation involves
multiple previous terms
C) A linear recurrence relation has a closed-form expression, while a nonlinear recurrence relation does not
D) A linear recurrence relation is always homogeneous, while a nonlinear recurrence relation can be nonhomogeneous
Answer: A
32. Which of the following is an example of a nonlinear recurrence relation?
A) f(n) = 2f(n-1)
B) g(n) = g(n-1) + g(n-2)
C) h(n) = h(n-1)^2 + 1
D) i(n) = n^2 + 1
Answer: C
33. What is the solution of the recurrence relation f(n) = 3f(n-1) + 2 with initial condition f(0) = 1, using the
generating function method?
A) f(n) = 3^n + 1
B) f(n) = 3^n - 1
C) f(n) = 3^n + 2
D) f(n) = 3^n - 2
Answer: D
34. What is the characteristic equation of the recurrence relation f(n) = 4f(n-1) - 4f(n-2) with initial conditions f(0) = 0
and f(1) = 1?
A) r^2 + 4r - 4 = 0
B) r^2 - 4r + 4 = 0
C) r^2 + 4r + 4 = 0
D) r^2 - 4r - 4 = 0
Answer: B
35. Which of the following is not an application of recurrence relations?
A) Counting problems
B) Data analysis
C) Time complexity analysis of algorithms
D) Modeling of physical phenomena
Answer: B
36. Which of the following is an example of a non-homogeneous linear recurrence relation with constant
coefficients?
A) f(n) = 2f(n-1) - f(n-2) + n
B) g(n) = g(n-1) + g(n-2) + 1
C) h(n) = h(n-1)^2 + 1
D) i(n) = n^2 + 1
Answer: A
37. What is the order of a recurrence relation?
A) The number of terms in the sequence
B) The degree of the polynomial in the characteristic equation
C) The number of initial conditions required to uniquely determine the sequence
D) The maximum number of previous terms involved in the relation
Answer: D
38. What is the method of undetermined coefficients used for in the solution of non-homogeneous linear recurrence
relations?
A) To find the general solution to the homogeneous recurrence relation
B) To find the particular solution to the non-homogeneous recurrence relation
C) To determine the order of the recurrence relation
D) To find the characteristic equation of the recurrence relation
Answer: B
39. Which of the following is an example of a non-linear non-homogeneous recurrence relation?
A) f(n) = f(n-1) + 2
B) g(n) = g(n-1)g(n-2)
C) h(n) = h(n-1) + n^2
D) i(n) = i(n-1)^2 + 1
Answer: B
40. Which of the following is the generating function for the sequence 1, 2, 4, 8, 16, ... ?
A) f(x) = 1/(1-x)
B) g(x) = 1/(1-2x)
C) h(x) = 1/(1-x^2)
D) i(x) = 1/(1-2x^2)
Answer: B
UNIT III COUNTING PRINCIPLES AND RELATIONS
41. Which principle of counting is used to find the number of elements in the union of two sets A and B
when A and B have some elements in common?
A. Principle of Inclusion-Exclusion
B. Pigeonhole Principle
C. Generalized Pigeonhole Principle
D. None of the above
Answer: A. Principle of Inclusion-Exclusion
42. In how many ways can 5 books be arranged on a shelf if 2 of the books must always be together?
A. 60
B. 120
C. 240
D. 480
Answer: B. 120
43. What is the maximum number of pigeons that can be placed in 4 pigeonholes if each hole can hold at most 2 pigeons?
A. 4
B. 6
C. 8
D. 10
Answer: C. 8
44. Which principle is used when there are more pigeons than pigeonholes?
A. Principle of Inclusion-Exclusion
B. Pigeonhole Principle
C. Generalized Pigeonhole Principle
D. None of the above
Answer: C. Generalized Pigeonhole Principle
45. What is the minimum number of colors needed to color a map with 9 regions so that no two adjacent regions have the same color?
A. 2
B. 3
C. 4
D. 5
Answer: B. 3
46. Which of the following is a reflexive relation?
A. {(1,1), (2,2), (3,2)}
B. {(1,2), (2,3), (3,1)}
C. {(1,1), (1,2), (2,1)}
D. {(1,2), (2,1), (3,3)}
Answer: A. {(1,1), (2,2), (3,2)}
47. Which of the following is a transitive relation?
A. {(1,2), (2,3), (3,1)}
B. {(1,2), (2,3), (3,2)}
C. {(1,1), (1,2), (2,1)}
D. {(1,2), (2,1), (3,3)}
Answer: B. {(1,2), (2,3), (3,2)}
48. What is the composition of relations R = {(1,2), (2,3)} and S = {(2,4), (3,5)}?
A. {(1,4), (2,5)}
B. {(2,4), (2,5)}
C. {(2,2), (2,3), (3,4), (3,5)}
D. {(1,4), (3,5)}
Answer: D. {(1,4), (3,5)}
49. What is the matrix representation of the relation R = {(1,2), (2,3), (3,1)}?
A.
0 1 0
0 0 1
1 0 0
B.
1 0 0
0 1 0
0 0 1
C.
0 0 1
1 0 0
0 1 0
D.
1 1 0
0 1 1
1 0 1
Answer: C.
50. Which of the following is an example of an equivalence relation?
A. {(1,2), (2,3), (3,4)}
B. {(1,2), (2,3), (1,3)}
C. {(1,2), (2,3), (3,1)}
D. {(1,2), (3,4), (5,6)}
Answer: B. {(1,2), (2,3), (1,3)}
51. Which of the following is a partially ordered set?
A. {(1,2), (2,1), (2,3)}
B. {(1,2), (2,3), (3,4)}
C. {(1,1), (2,2), (3,3)}
D. {(1,2), (2,3), (3,1)}
Answer: B. {(1,2), (2,3), (3,4)}
52. Which of the following is a total ordering relation?
A. {(1,2), (2,1), (2,3)}
B. {(1,2), (2,3), (3,4)}
C. {(1,1), (2,2), (3,3)}
D. {(1,2), (2,1), (3,4)}
Answer: D. {(1,2), (2,1), (3,4)}
53. What is the Hasse diagram for the partially ordered set {(1,2), (2,3), (3,4)}?
A.
1 --- 2 --- 3 --- 4
B.
1 --- 2
|
3 --- 4
C.
1 --- 2 --- 3
|
4
D.
1 --- 2 --- 3
|
3
Answer: C.
1 --- 2 --- 3
|
4
54. What is the transitive closure of the relation R = {(1,2), (2,3)}?
A. {(1,2), (2,3)}
B. {(1,3), (1,2), (2,3)}
C. {(1,2), (2,3), (1,3)}
D. {(1,3)}
Answer: C. {(1,2), (2,3), (1,3)}
55. What is the reflexive closure of the relation R = {(1,2), (2,3)}?
A. {(1,2), (2,3)}
B. {(1,1), (2,2), (3,3), (1,2), (2,3)}
C. {(1,2), (2,3), (2,2)}
D. {(1,2), (2,3), (1,1), (3,3)}
Answer: B. {(1,1), (2,2), (3,3), (1,2), (2,3)}
56. Which of the following is an example of a sublattice of the lattice {(0,0), (0,1), (1,0), (1,1)}?
A. {(0,0), (0,1)}
B. {(0,0), (1,0)}
C. {(0,0), (1,1)}
D. {(1,0), (1,1)}
Answer: A. {(0,0), (0,1)}
57. Which of the following is a valid Hasse diagram for the lattice {(1,1), (1,2), (1,3), (2,3), (3,3)}?
A.
(1,1) --- (1,2) --- (1,3)
| |
(2,3) (3,3)
B.
(1,1) --- (1,2) --- (1,3)
|
(2,3)
|
(3,3)
C.
(1,1) --- (1,2) --- (1,3) --- (2,3) --- (3,3)
D.
(1,1) --- (1,2) --- (2,3) --- (1,3) --- (3,3)
Answer: A.
(1,1) --- (1,2) --- (1,3)
| |
(2,3) (3,3)
58. Which of the following is an example of a function that is not injective?
A. f(x) = x^2
B. f(x) = 2x + 1
C. f(x) = sin(x)
D. f(x) = |x|
Answer: A. f(x) = x^2
59. Which of the following is an example of a function that is not surjective?
A. f(x) = x^2
B. f(x) = 2x + 1
C. f(x) = sin(x)
D. f(x) = |x|
Answer: D. f(x) = |x|
60. Which of the following is true for a symmetric relation R?
A. R is always reflexive.
B. R is always transitive.
C. R is always irreflexive.
D. R is always antisymmetric.
Answer: B. R is always transitive.
Also Check: MTH-401 MTE Study Material