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.
- Consider the following statements with respect to duality in LPP : (a) The final simplex table giving optimal solution of the primal also contains optimal solution of its dual in itself. (b) If either the primal or the…
- Consider the poset ({3, 5, 9, 15, 24, 45}, |) under divisibility. Which of the following is correct?
- How many ways are there to place 8 indistinguishable balls into four distinguishable bins?
- How many bit strings of length ten either start with a 1 bit or end with two bits 00 ?
- Suppose that a connected planar graph has six vertices, each of degree four. Into how many regions is the plane divided by a planar representation of this graph?
- For which values of and does the complete k bipartite graph m,n have a Hamilton circuit?
- Which of the following is the principal conjunctive normal form of [(p ∨ q) ∧ ¬p] → ¬q?
- How many cards must be selected from a standard deck of 52 cards to guarantee that at least three hearts are present among them?
- Match List I with List II. List I: (a) p → q, (b) p ∨ q, (c) p ∧ q, (d) ¬(p → q). List II: (i) ¬(q → ¬p), (ii) p ∧ ¬q, (iii) ¬p → q, (iv) ¬p ∨ q.
- Find the zero-one matrix of the transitive closure of the relation with matrix A = [1 0 1; 0 1 0; 1 1 0].
- For the LPP: maximize Z = 2x₁ − x₂ + 2x₃ subject to 2x₁ + x₂ ≤ 10, x₁ + 2x₂ − 2x₃ ≤ 20, x₁ + 2x₃ ≤ 5, x₁, x₂, x₃ ≥ 0, what is the solution after the first simplex iteration?
- How many different Boolean functions of degree n are there?
- Consider the Euler's phi function given by ϕ(n) = n ∏ (1 − 1 ) p p n where runs over all the primes dividing . What ϕ(45) is the value of ?
- Consider the following statements : S n > 1, aϕ(n) ≡ 1(mod n) 1 : For any integer a ∈ Z∗ ϕ(n) for all n , where is Euler's phi function. S p ap ≡ 1(mod p) 2 : If is prime, then for all a ∈ Z∗ p . Which one of the follow…
- In mathematical logic, which of the following are statements? (i) There will be snow in January. (ii) What is the time now ? (iii) Today is Sunday. (iv) You must study Discrete Mathematics. Choose the correct answer fro…
- Match List I with List II and choose the correct answer from the code given below.
- A box contains six red balls and four green balls. Four balls are selected at random from the box. What is the probability that two of the selected balls will be red and two will be green?
- A survey has been conducted on methods of commuter travel. Each respondent was asked to check Bus, Train or Automobile as a major method of travelling to work. More than one answer was permitted. The results reported we…
- Which of the following statements are true? (i) Every logic network is equivalent to one using just NAND gates or just NOR gates. (ii) Boolean expressions and logic networks correspond to labelled acyclic digraphs. (iii…
- The relations ≤ and < on a Boolean algebra are defined as: x ≤ y if and only if x ∨ y = y; x < y means x ≤ y but x ≠ y; x ≥ y means y ≤ x; and x > y means y < x. Considering these definitions, which of the following is…
- In PERT/CPM, the merge event represents ___ of two or more events.
- Use the dual simplex method to solve: Maximize z = −2x₁ − 3x₂ subject to x₁ + x₂ ≥ 2, 2x₁ + x₂ ≤ 10, x₁ + x₂ ≤ 8, x₁, x₂ ≥ 0.
- If a graph G has no loops or parallel edges and has n ≥ 3 vertices, then G is Hamiltonian if (i) deg(v) ≥ n/3 for each vertex v (ii) deg(v) + deg(w) ≥ n whenever v and w are not connected by an edge (iii) |E(G)| ≥ (1/3)…
- Which of the following statements is false about convex minimization problem ?
- The following LPP: Maximize z = 100x₁ + 2x₂ + 5x₃ subject to 14x₁ + x₂ − 6x₃ + 3x₄ = 7, 32x₁ + x₂ − 12x₃ ≤ 10, 3x₁ − x₂ − x₃ ≤ 0, x₁, x₂, x₃, x₄ ≥ 0, has
- Digital data from a sensor can fill 0 to 32 buffers. Let the sample space be S = {0, 1, 2, …, 32}, where j means j buffers are full, and p(i) = (33 − i)/561. Let A be the event that an even number of buffers are full. T…
- The equivalence of ¬∃x Q(x) is
- If Aᵢ = {−i, …, −2, −1, 0, 1, 2, …, i}, then ⋃ᵢ₌₁^∞ Aᵢ is
- Match the following in List - I and List - II, for a function f :
- Which of the relations on {0, 1, 2, 3} is an equivalence relation ?