Recent questions in Discrete Mathematics / GATE Overflow for GATE CSE

34 votes

2 answers

6241

GATE IT 2004 | Question: 37
What is the number of vertices in an undirected connected graph with $27$ edges, $6$ vertices of degree $2, 3$ vertices of degree $4$ and remaining of degree $3$? $10$ $11$ $18$ $19$

What is the number of vertices in an undirected connected graph with $27$ edges, $6$ vertices of degree $2, 3$ vertices of degree $4$ and remaining of degree $3$?$10$$11$...

Ishrat Jahan

13.0k views

Ishrat Jahan asked Nov 2, 2014

43 votes

11 answers

6242

GATE IT 2004 | Question: 35
In how many ways can we distribute $5$ distinct balls, $B_1, B_2, \ldots, B_5$ in $5$ distinct cells, $C_1, C_2, \ldots, C_5$ such that Ball $B_i$ is not in cell $C_i$, $\forall i= 1,2,\ldots 5$ and each cell contains exactly one ball? $44$ $96$ $120$ $3125$

In how many ways can we distribute $5$ distinct balls, $B_1, B_2, \ldots, B_5$ in $5$ distinct cells, $C_1, C_2, \ldots, C_5$ such that Ball $B_i$ is not in cell $C_i$, $...

Ishrat Jahan

11.5k views

Ishrat Jahan asked Nov 2, 2014

41 votes

1 answer

6243

GATE IT 2004 | Question: 34
Let $H_1, H_2, H_3,$ ... be harmonic numbers. Then, for $n \in Z^+$, $\sum_{j=1}^{n} H_j$ can be expressed as $nH_{n+1} - (n + 1)$ $(n + 1)H_n - n$ $nH_n - n$ $(n + 1) H_{n+1} - (n + 1)$

Let $H_1, H_2, H_3,$ ... be harmonic numbers. Then, for $n \in Z^+$, $\sum_{j=1}^{n} H_j$ can be expressed as$nH_{n+1} - (n + 1)$$(n + 1)H_n - n$$nH_n - n$$(n + 1) H_{n+...

Ishrat Jahan

5.6k views

Ishrat Jahan asked Nov 2, 2014

41 votes

9 answers

6244

GATE IT 2004 | Question: 31
Let $p, q, r$ and $s$ be four primitive statements. Consider the following arguments: $P: [(¬p\vee q) ∧ (r → s) ∧ (p \vee r)] → (¬s → q)$ $Q: [(¬p ∧q) ∧ [q → (p → r)]] → ¬r$ $R: [[(q ∧ r) → p] ∧ (¬q \vee p)] → r$ $S: [p ∧ (p → r) ∧ (q \vee ¬ r)] → q$ Which of the above arguments are valid? $P$ and $Q$ only $P$ and $R$ only $P$ and $S$ only $P, Q, R$ and $S$

Let $p, q, r$ and $s$ be four primitive statements. Consider the following arguments:$P: [(¬p\vee q) ∧ (r → s) ∧ (p \vee r)] → (¬s → q)$$Q: [(¬p ∧q) �...

Ishrat Jahan

11.9k views

Ishrat Jahan asked Nov 2, 2014

25 votes

8 answers

6245

GATE IT 2004 | Question: 5
What is the maximum number of edges in an acyclic undirected graph with $n$ vertices? $n-1$ $n$ $n+1$ $2n-1$

What is the maximum number of edges in an acyclic undirected graph with $n$ vertices?$n-1$$n$$n+1$$2n-1$

Ishrat Jahan

7.1k views

Ishrat Jahan asked Nov 1, 2014

39 votes

3 answers

6246

GATE IT 2004 | Question: 4
Let $R_{1}$ be a relation from $A = \left \{ 1,3,5,7 \right \}$ to $B = \left \{ 2,4,6,8 \right \}$ and $R_{2}$ be another relation from $B$ to $C = \{1, 2, 3, 4\}$ as defined below: An element $x$ in $A$ is related to an element $y$ in $B$ (under $R_{1}$) if $x + y$ is ... $R_{1}R_{2} = \{(3, 2), (3, 4), (5, 1), (5, 3), (7, 1)\} $

Let $R_{1}$ be a relation from $A = \left \{ 1,3,5,7 \right \}$ to $B = \left \{ 2,4,6,8 \right \}$ and $R_{2}$ be another relation from $B$ to $C = \{1, 2, 3, 4\}$ as de...

Ishrat Jahan

10.3k views

Ishrat Jahan asked Nov 1, 2014

28 votes

2 answers

6247

GATE IT 2004 | Question: 3
Let $a(x, y), b(x, y,)$ and $c(x, y)$ be three statements with variables $x$ and $y$ chosen from some universe. Consider the following statement: $\qquad(\exists x)(\forall y)[(a(x, y) \wedge b(x, y)) \wedge \neg c(x, y)]$ ... $\neg (\forall x)(\exists y)[(a(x, y) \vee b(x, y)) \to c(x, y)]$

Let $a(x, y), b(x, y,)$ and $c(x, y)$ be three statements with variables $x$ and $y$ chosen from some universe. Consider the following statement:$\qquad(\exists x)(\foral...

Ishrat Jahan

6.3k views

Ishrat Jahan asked Nov 1, 2014

22 votes

3 answers

6248

GATE IT 2004 | Question: 2
In a class of $200$ students, $125$ students have taken Programming Language course, $85$ students have taken Data Structures course, $65$ students have taken Computer Organization course; $50$ students have taken both Programming Language and Data Structures, $35$ ... all the three courses. How many students have not taken any of the three courses? $15$ $20$ $25$ $30$

In a class of $200$ students, $125$ students have taken Programming Language course, $85$ students have taken Data Structures course, $65$ students have taken Computer Or...

Ishrat Jahan

5.5k views

Ishrat Jahan asked Nov 1, 2014

64 votes

9 answers

6249

GATE IT 2006 | Question: 25
Consider the undirected graph $G$ defined as follows. The vertices of $G$ are bit strings of length $n$. We have an edge between vertex $u$ and vertex $v$ if and only if $u$ and $v$ differ in exactly one bit position (in other words, $v$ can be obtained from $u$ by ... $\left(\frac{1}{n}\right)$ $\left(\frac{2}{n}\right)$ $\left(\frac{3}{n}\right)$

Consider the undirected graph $G$ defined as follows. The vertices of $G$ are bit strings of length $n$. We have an edge between vertex $u$ and vertex $v$ if and only if ...

Ishrat Jahan

13.3k views

Ishrat Jahan asked Oct 31, 2014

26 votes

3 answers

6250

GATE IT 2006 | Question: 24
What is the cardinality of the set of integers $X$ defined below? $X=\{n \mid 1 \leq n ≤ 123, n$ is not divisible by either $2$, $3$ or $5\}$ $28$ $33$ $37$ $44$

What is the cardinality of the set of integers $X$ defined below?$X=\{n \mid 1 \leq n ≤ 123, n$ is not divisible by either $2$, $3$ or $5\}$$28$$33$$37$$44$

Ishrat Jahan

6.5k views

Ishrat Jahan asked Oct 31, 2014

27 votes

4 answers

6251

GATE IT 2006 | Question: 23
Let $P$, $Q$ and $R$ be sets let Δ denote the symmetric difference operator defined as $PΔQ=(P \cup Q) - (P ∩ Q).$ Using Venn diagrams, determine which of the following is/are TRUE? $PΔ (Q ∩ R) = (P Δ Q) ∩ (P Δ R)$ $P ∩ (Q ∩ R) = (P ∩ Q) Δ (P Δ R)$ I only II only Neither I nor II Both I and II

Let $P$, $Q$ and $R$ be sets let Δ denote the symmetric difference operator defined as $PΔQ=(P \cup Q) - (P ∩ Q).$ Using Venn diagrams, determine which of the followi...

Ishrat Jahan

5.8k views

Ishrat Jahan asked Oct 31, 2014

63 votes

7 answers

6252

GATE IT 2006 | Question: 21
Consider the following first order logic formula in which $R$ is a binary relation symbol. $∀x∀y (R(x, y) \implies R(y, x))$ The formula is satisfiable and valid satisfiable and so is its negation unsatisfiable but its negation is valid satisfiable but its negation is unsatisfiable

Consider the following first order logic formula in which $R$ is a binary relation symbol.$∀x∀y (R(x, y) \implies R(y, x))$The formula issatisfiable and validsatisfia...

Ishrat Jahan

13.4k views

Ishrat Jahan asked Oct 31, 2014

37 votes

7 answers

6253

GATE IT 2006 | Question: 11
If all the edge weights of an undirected graph are positive, then any subset of edges that connects all the vertices and has minimum total weight is a Hamiltonian cycle grid hypercube tree

If all the edge weights of an undirected graph are positive, then any subset of edges that connects all the vertices and has minimum total weight is aHamiltonian cyclegri...

Ishrat Jahan

8.9k views

Ishrat Jahan asked Oct 31, 2014

34 votes

5 answers

6254

GATE IT 2006 | Question: 6
Given a boolean function $f (x_1, x_2, \ldots, x_n),$ which of the following equations is NOT true? $f (x_1, x_2, \ldots, x_n) = x_1'f(x_1, x_2, \ldots, x_n) + x_1f(x_1, x_2, \ldots, x_n)$ ... $f (x_1, x_2, \ldots , x_n) = f(0, x_2, , x_n) + f(1, x_2, \ldots, x_n)$

Given a boolean function $f (x_1, x_2, \ldots, x_n),$ which of the following equations is NOT true?$f (x_1, x_2, \ldots, x_n) = x_1'f(x_1, x_2, \ldots, x_n) + x_1f(x_1, x...

Ishrat Jahan

6.3k views

Ishrat Jahan asked Oct 31, 2014

44 votes

4 answers

6255

GATE IT 2006 | Question: 2
For the set $N$ of natural numbers and a binary operation $f : N \times N \to N,$ an element $z \in N$ is called an identity for $f,$ if $f (a, z) = a = f(z, a),$ for all $a \in N.$ Which of the following binary operations have an identity? $f (x, y) = x + y - 3$ $f (x, y) = \max(x, y)$ $f (x, y) = x^y$ I and II only II and III only I and III only None of these

For the set $N$ of natural numbers and a binary operation $f : N \times N \to N,$ an element $z \in N$ is called an identity for $f,$ if $f (a, z) = a = f(z, a),$ for all...

Ishrat Jahan

9.7k views

Ishrat Jahan asked Oct 30, 2014

23 votes

4 answers

6256

GATE IT 2007 | Question: 76
Consider the sequence $\langle x_n \rangle , \: n \geq 0$ defined by the recurrence relation $x_{n+1} = c . x^2_n -2$, where $c > 0$. Suppose there exists a non-empty, open interval $(a, b)$ such that for all $x_0$ satisfying $a < x_0 < b$, the ... sequence converges to the value? $\frac{1+\sqrt{1+8c}}{2c}$ $\frac{1-\sqrt{1+8c}}{2c}$ $2$ $\frac{2}{2c-1}$

Consider the sequence $\langle x_n \rangle , \: n \geq 0$ defined by the recurrence relation $x_{n+1} = c . x^2_n -2$, where $c 0$.Suppose there exists a non-empty, open...

Ishrat Jahan

5.5k views

Ishrat Jahan asked Oct 30, 2014

73 votes

6 answers

6257

GATE IT 2007 | Question: 25
What is the largest integer $m$ such that every simple connected graph with $n$ vertices and $n$ edges contains at least $m$ different spanning trees ? $1$ $2$ $3$ $n$

What is the largest integer $m$ such that every simple connected graph with $n$ vertices and $n$ edges contains at least $m$ different spanning trees ?$1$$2$$3$$n$

Ishrat Jahan

21.6k views

Ishrat Jahan asked Oct 29, 2014

32 votes

7 answers

6258

GATE IT 2007 | Question: 23
A partial order $P$ is defined on the set of natural numbers as follows. Here $\frac{x}{y}$ denotes integer division. $(0, 0) \in P.$ $(a, b) \in P$ if and only if $(a \% 10) \leq (b \% 10$) and $(\frac{a}{10},\frac{b}{10})\in P.$ ... $P$? (i) and (iii) (ii) and (iv) (i) and (iv) (iii) and (iv)

A partial order $P$ is defined on the set of natural numbers as follows. Here $\frac{x}{y}$ denotes integer division.$(0, 0) \in P.$$(a, b) \in P$ if and only if $(a \% 1...

Ishrat Jahan

11.4k views

Ishrat Jahan asked Oct 29, 2014

43 votes

5 answers

6259

GATE IT 2007 | Question: 21
Which one of these first-order logic formulae is valid? $\forall x\left(P\left(x\right) \implies Q\left(x\right)\right) \implies \left(∀xP\left(x\right)\implies \forall xQ\left(x\right)\right)$ ... $\forall x \exists y P\left(x, y\right)\implies \exists y \forall x P\left(x, y\right)$

Which one of these first-order logic formulae is valid?$\forall x\left(P\left(x\right) \implies Q\left(x\right)\right) \implies \left(∀xP\left(x\right)\implies \forall ...

Ishrat Jahan

10.5k views

Ishrat Jahan asked Oct 29, 2014

22 votes

3 answers

6260

GATE IT 2007 | Question: 16
The minimum positive integer $p$ such that $3^{p} \pmod {17} = 1$ is $5$ $8$ $12$ $16$

The minimum positive integer $p$ such that $3^{p} \pmod {17} = 1$ is$5$$8$$12$$16$

Ishrat Jahan

7.6k views

Ishrat Jahan asked Oct 29, 2014

tags	tag:apple
author	user:martin
title	title:apple
content	content:apple
exclude	-tag:apple
force match	+apple
views	views:100
score	score:10
answers	answers:2
is accepted	isaccepted:true
is closed	isclosed:true