Discrete Structures and Optimization – Previous Year Questions
272 questions from past UGC NET Paper 2 – Computer Science papers, each with the correct answer. Open any question for its explanation.
- Let R = {x | x ∈ N, x is a multiple of 3 and x ≤ 100} and S = {x | x ∈ N, x is a multiple of 5 and x < 100}. What is the number of elements in (R ∩ S) × (S ∩ R)?
- There are m points on one straight line AB and n points on another straight line AC, none of them being A. How many triangles can be formed with these points as vertices?
- Let N be the set of natural numbers and R the relation on N × N defined by (a, b) R (c, d) if ad(b + c) = bc(a + d). Then R is
- How many integral solutions are there to x + y + z + w = 29, where x ≥ 1, y ≥ 2, z ≥ 3 and w ≥ 0?
- In a multi-user operating system, on average 20 requests are made to use a particular resource per hour. The probability that no request is made in 45 minutes is
- Let G = R \ {0} (non-zero reals) and H = {−1, 1} be groups under multiplication. Then the map φ : G → H defined by φ(x) = x/|x| is
- Find the sum of all four-digit numbers formed using the digits 1, 2, 4 and 6 (each used once).
- Match List I with List IIList I List II A. A △ B I. (A − B) ∪ (A − C) B. A − (B ∪ C) II. (A − B) ∩ (A − C) C. A − (B ∩ C) III. (A − B) ∪ (B − A) D. A ∩ (B − C) IV. (A ∩ B) − (A ∩ C)
- Consider the following statements: A. The identity is unique in any monoid. B. A monoid is a group if every element of the monoid has an inverse. C. A semigroup has closure, associative and identity properties. D. A qua…
- If A = {4n + 2 | n is a natural number} and B = {3n | n is a natural number}, which of the following is correct for A ∩ B?
- If f(n) = 5f(n/2) + 3 and f(1) = 7 is a recurrence relation, where k is a positive integer, then f(2ᵏ) =
- Which of the following are TRUE if the universe of discourse consists of all integers? A. ∀n ∃m (n² < m) B. ∃n ∀m (n < m²) C. ∃n ∃m (n² + m² = 5) D. ∃n ∃m (n² + m² = 6) E. ∃n ∃m (m + n = 4 ∧ n − m = 1) Choose the correc…
- Which of the following sequences aₙ is a solution of the recurrence relation aₙ = 8aₙ₋₁ − 16aₙ₋₂? A. aₙ = 1 B. aₙ = 2ⁿ C. aₙ = 4ⁿ D. aₙ = n·4ⁿ E. aₙ = (−4)ⁿ Choose the most appropriate answer from the options given belo…
- Arrange the following simple graphs by the number of spanning trees they have (increasing): A. K₃ (complete graph on 3 nodes) B. K₄ (complete graph on 4 nodes) C. K₂,₂ (complete bipartite graph with 2 nodes in each part…
- A bit string of length four is generated at random. What is the probability that it contains at least two consecutive 0s, given that the first bit is 0?
- Arrange the following sets in increasing order of their cardinality: A. A1 = {{1, 2}, {3}} B. A2 = {{1}, {2}, {3}, {4}} C. A3 = {{1, 2, 3, 4, 5, 6}} D. A4 = {{1, 2}, {2, 3, 4}, {5}} E. A5 = {{1}, {2}, {3}, {4}, {5}} Cho…
- The chairs of an auditorium are to be labelled with a letter followed by a positive two-digit integer, starting with A01. What is the maximum number of chairs that can be labelled this way?
- Z is the set of integers. ⟨Z, *⟩ forms a group if * is:
- Arrange the steps of mathematical modelling: A. Solution fitting with data B. Formulation mathematically C. Solve mathematically D. Repeat formulation if it fits poorly with the data E. Interpret results Choose the corr…
- Which of the following are tautologies? A. (p ∨ r) → p B. p → (p ∧ r) C. ~p → (p → r) D. (p ∧ r) → (p → r) E. ~(p → r) → p Choose the correct answer from the options given below:
- Which of the following is NOT a common property of social networks?
- When the LPP is formulated from the passage, which of the following is the objective function of its dual problem?
- Which of the following is the appropriate objective function for the given problem?
- How many unit lengths of cloth A are used when income is maximised (as per the keyed answer)?
- If x unit lengths of type A and y unit lengths of type B cloth are produced, the constraints of the LPP are:
- On the basis of the available material, the maximum total income is:
- Which of the following is NOT logically equivalent to P → Q?
- Seven people enter a lift. The lift stops at only three (unspecified) floors. At each of the three floors no one enters, but at least one person leaves. After the three stops the lift is empty. In how many ways can this…
- The coefficient of x²y³z² in the expansion of (x + y + z)⁷ is
- What is the minimum number of students in a discrete mathematics class to be sure that at least six will receive the same grade, if there are seven possible grades: S, A, B, C, D, P and F?