The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
GATE Overflow
Facebook Login
or
Email or Username
Password
Remember
Login
Register

I forgot my password
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
First time here? Checkout the
FAQ
!
x
×
Close
Use the google search bar on side panel. It searches through all previous GATE/other questions. For hardcopy of previous year questions please see
here
Recent questions and answers in Discrete Mathematics
0
votes
0
answers
1
Rosen example 12 Ch 5.2
Show that every sequence of $n^2$+1 distinct real numbers contains a subsequence of length n+1 that is either strictly increasing or strictly decreasing.
asked
1 hour
ago
in
Combinatory
by
himgta
Active
(
3.6k
points)

10
views
0
votes
1
answer
2
Rosen
S(x): x is a student F(X): x is a faculty member A(x, y): x has asked y a question use quantifiers to express: Some student has asked every faculty member a question
answered
10 hours
ago
in
Mathematical Logic
by
Deepakk Poonia (Dee)
Boss
(
22.8k
points)

21
views
kennethrosen
discretemathematics
propositionallogic
0
votes
1
answer
3
Kenneth Rosen Example 9 Ch.5.2
Suppose that a computer science laboratory has 15 workstations and 10 servers. A cable can be used to directly connect a workstation to a server. For each server, only one direct connection to that server can be active at any time. We ... 't understand this part. How is it concluded that remaining nine servers are insufficient when at most 59 connections are used?
answered
15 hours
ago
in
Combinatory
by
Deepakk Poonia (Dee)
Boss
(
22.8k
points)

28
views
+1
vote
1
answer
4
Strongly Connected, Unilaterally connected and weakly Connected
Hi Guys, Is there any quick way of verifying Graph is Strongly Connected, Unilaterally connected and weakly Connected ? For Example  If 1 dead point then graph is Unilaterally Connected and If 2 dead points then graph is Weakly Connected.
answered
1 day
ago
in
Graph Theory
by
saurav raghaw
Active
(
1k
points)

256
views
graphtheory
discretemathematics
algorithms
+2
votes
1
answer
5
kenneth rosen Ex2.4 Q.46
Show that the set of functions from the positive integers to the set {0,1,2,3,4,5,6,7,8,9} is uncountable.
answered
2 days
ago
in
Set Theory & Algebra
by
Devshree Dubey
Boss
(
13.5k
points)

99
views
0
votes
1
answer
6
UGCNETjune2009ii25
The prepositional formula given by the tree: is: (A) ˄˅x2˅x1¬x1¬x1 (B) (x2˅¬x2)˄(x1˅x2) (C) (¬x1˅x2)˄(¬x1˅x2) (D) None
answered
2 days
ago
in
Mathematical Logic
by
rajatmyname
Active
(
1.3k
points)

94
views
ugcnetjune2009ii
0
votes
1
answer
7
Logic Kenneth Rosen Ex1.4 Q.23
what is the approach of solving this question? Q.Translate in two ways each of these statements into logical expressions using predicates, quantifiers, and logical connectives. First, let the domain consist of the students in your class and second, let it ... in your class has been in a movie. e) No student in your class has taken a course in logic programming.
answered
2 days
ago
in
Mathematical Logic
by
Bhaskar Singh
(
229
points)

54
views
kennethrosen
discretemathematics
propositionallogic
+1
vote
1
answer
8
ISI MMA201527
Let, $cos^{6}\theta = a_{6}cos6\theta + a_{5}cos5\theta + a_{4}cos4\theta + a_{3}cos3\theta + a_{2}cos2\theta + a_{1}cos\theta + a_{0}$ Then $a_{0}$ is (A) $0$ (B) $\frac{1}{32}$ (C) $\frac{15}{32}$ (D) $\frac{10}{32}$ ... 3 equations , I am getting $a_{0} + a_{4} = \frac{1}{2}$ but don't know how to proceed further to get the value of $a_{0}$. Please help.
answered
2 days
ago
in
Set Theory & Algebra
by
venkatesh pagadala
(
415
points)

77
views
engineeringmathematics
userisi2015
usermod
+16
votes
4
answers
9
GATE20005
A multiset is an unordered collection of elements where elements may repeat any number of times. The size of a multiset is the number of elements in it, counting repetitions. What is the number of multisets of size $4$ that can be constructed from n distinct elements so that at least one element occurs exactly twice? How many multisets can be constructed from n distinct elements?
answered
4 days
ago
in
Combinatory
by
Priyadrasta Raut
(
345
points)

1.1k
views
gate2000
permutationsandcombinations
normal
descriptive
0
votes
1
answer
10
Kenneth rosen Q.36 Ex.2.3
Let f be a function from the set A to the set B.Let S and T be subsets of A.Show that $f(S\cup T)=f(S)\cup f(T)$ $f(S\cap T)\subseteq f(S)\cap f(T)$ Show that inclusion in part b can be proper
answered
5 days
ago
in
Set Theory & Algebra
by
prashant jha 1
Active
(
4.1k
points)

40
views
kennethrosen
settheory&algebra
+2
votes
1
answer
11
GATE  2014  1 51 modified
Consider an directed graph G where selfloops are not allowed. The vertex set of G is {(i,j)∣1≤i≤12,1≤j≤12}There is an edge from(a,b) to (c,d) if a−c≤1 and b−d≤1. The number of edges in this graph is______
answered
5 days
ago
in
Graph Theory
by
Priyadrasta Raut
(
345
points)

121
views
0
votes
1
answer
12
kenneth rosen Ex 2.3 Q.29,30
Justify the statements. 1. if f and f o g are one to one,does it follows that g is one to one. 2 if f and f o g are onto,does it follow that g is onto
answered
5 days
ago
in
Set Theory & Algebra
by
Deepakk Poonia (Dee)
Boss
(
22.8k
points)

27
views
–1
vote
0
answers
13
Kenneth Rosen Ex.2.3 Q.3(c)
https://prnt.sc/cncgcv plz explain the c part!
asked
5 days
ago
in
Set Theory & Algebra
by
himgta
Active
(
3.6k
points)

52
views
0
votes
0
answers
14
JEST 2019
A directed graph with n vertices, in which each vertex has exactly 3 outgoing edges. Which one is true? A) All the vertices have indegree = 3 . B) Some vertices will have indegree exactly 3. C)Some vertices have indegree atleast 3. D) Some of the vertices have indegree atmost 3
asked
6 days
ago
in
Graph Theory
by
Sayan Bose
Loyal
(
5.9k
points)

32
views
jest
graphtheory
+1
vote
0
answers
15
JEST 2019
Let ${(0,1)}^n$ set of all binary string of length n. Hamming sphere of radius around a string C in ${(0,1)}^n$ is the set of all strings d$\epsilon$ ${(0,1)}^n$ that differ from C in at most r of n position, S(C,r) for n=2k+1 For C,C’ $\epsilon$ ${(0,1)}^n$ S(C,k) and S(C’,k) are disjoint couldn't remember rest of the options.
asked
6 days
ago
in
Set Theory & Algebra
by
vivek_mishra
(
399
points)

48
views
jest
2019
discretemathematics
0
votes
0
answers
16
JEST 2019 Descriptive Q3 (8 Marks)
Determine the number of functions f:{1,2,3…,n}→{1995,1996} satisfying the condition that f(1)+f(2)+…f(n) is odd.
asked
6 days
ago
in
Set Theory & Algebra
by
dan31
Junior
(
657
points)

68
views
jest2019
discretemathematics
0
votes
0
answers
17
JEST 2019 Descriptive Q2 (8 Marks)
Given a sequence $a_1$, $a_2$ , $a_3$ ... $a_n$ of any different positive integers, exhibit an arrangement of integers between 1 and $n^2$ which has no increasing or decreasing subsequence of length n+1.
asked
6 days
ago
in
Graph Theory
by
dan31
Junior
(
657
points)

29
views
jest
2019
discretemathematics
0
votes
0
answers
18
JEST 2019 Descriptive Q1 (8 Marks)
Suppose that G contains a cycle C, and a path of length at least k between some two vertices of C. Show that G contains a cycle of length at least √k.
asked
6 days
ago
in
Graph Theory
by
dan31
Junior
(
657
points)

24
views
jest
2019
discretemathematics
+1
vote
2
answers
19
TIFR2011MathsA16
The polynomial $x^{4}+7x^{3}13x^{2}+11x$ has exactly one real root.
answered
Feb 16
in
Set Theory & Algebra
by
Sreyasree Mandal
(
117
points)

121
views
tifrmaths2011
polynomials
0
votes
1
answer
20
Kenneth Rosen chapter 5 20 discrete mathematics
A playoff between two teams consists of at most five games . The first team that wins three games wins the playoff. In how many different way playoff occur?
[closed]
answered
Feb 16
in
Combinatory
by
subhrob
(
373
points)

30
views
kennethrosen
discretemathematics
permutationsandcombinations
0
votes
1
answer
21
Linear algebra
The number of different n×n symmetric matrices with each element being 0 or 1 is
answered
Feb 15
in
Mathematical Logic
by
Ananya Jaiswal 1
Active
(
2.2k
points)

35
views

0
votes
1
answer
22
Discrete Maths and Its Applications, 7th Edition, Kenneth Rosen
1. Which of these sentences are propositions? What are the truth values of those that are propositions? a) Boston is the capital of Massachusetts. b) Miami is the capital of Florida. c) 2+3 = 5. d) 5+7 = 10. e) x +2 ... is answer for f) as I am thinking I can answer this question or I will not answer this question is it a proposition?
answered
Feb 15
in
Mathematical Logic
by
prashant jha 1
Active
(
4.1k
points)

25
views
+12
votes
3
answers
23
CMI2013A06
A simple graph is one in which there are no selfloops and each pair of distinct vertices is connected by at most one edge.Let $G$ be a simple graph on $8$ vertices such that there is a vertex of degree $1$, a vertex of degree $2$, a vertex of degree $3$, a vertex of ... degree $6$ and a vertex of degree $7$. Which of the following can be the degree of the last vertex? $3$ $0$ $5$ $4$
answered
Feb 15
in
Graph Theory
by
Satbir
Active
(
5.1k
points)

562
views
cmi2013
graphtheory
normal
degreeofgraph
+2
votes
1
answer
24
JEST Sample Question 1b
When is the following statement true? (A ∪ B) ∩ C = A ∩ C (A) If Ā ∩ B ∩ C = φ (B) If A ∩ B ∩ C = φ (C) always (D) never
answered
Feb 15
in
Set Theory & Algebra
by
Ram Swaroop
Active
(
2.3k
points)

56
views
jest
gate
discretemathematics
settheory&algebra
0
votes
1
answer
25
JEST Sample Question 1a
Let a and b be positive integers such that a > b and a^ 2 − b^ 2 is a prime number. Then a^2 − b^ 2 is equal to (A) a − b (B) a + b (C) a × b (D) none of the above
answered
Feb 15
in
Set Theory & Algebra
by
Naveen Kumar 3
Active
(
3.4k
points)

58
views
jest
gate
discretemathematics
settheory&algebra
permutationsandcombinations
0
votes
1
answer
26
Jest Exam sample question3
How many subsets of even cardinality does an nelement set have ? Justify answer. Please give a proof if possible.This is part of subjective JEST paper.
answered
Feb 15
in
Set Theory & Algebra
by
subhrob
(
373
points)

17
views
jest
settheory&algebra
discretemathematics
gate
0
votes
1
answer
27
For All & There Exist property
is For All V is distributive on AND operator? 1 is ‘’there exist’’ is distributive over OR operator? 2 I have example in which this is true , but is true in general? so logically checking without using any property above four statements are correct. But is 1 and 2 always correct?
answered
Feb 15
in
Mathematical Logic
by
Arko Jyoti Shith
(
37
points)

31
views
0
votes
4
answers
28
GATE201912
Let $G$ be an undirected complete graph on $n$ vertices, where $n > 2$. Then, the number of different Hamiltonian cycles in $G$ is equal to $n!$ $(n1)!$ $1$ $\frac{(n1)!}{2}$
answered
Feb 14
in
Graph Theory
by
OO7
Junior
(
579
points)

2.1k
views
gate2019
engineeringmathematics
discretemathematics
graphtheory
graphconnectivity
0
votes
1
answer
29
Permutation and Combination
The total number of ways in which 5 balls of different color can be distributed among 3 persons so that each person gets at least one ball is:
answered
Feb 14
in
Mathematical Logic
by
Satbir
Active
(
5.1k
points)

56
views
permutationsandcombinations
+2
votes
5
answers
30
GATE201935
Consider the first order predicate formula $\phi$: $\forall x [ ( \forall z \: z \mid x \Rightarrow (( z=x) \vee (z=1))) \rightarrow \exists w ( w > x) \wedge (\forall z \: z \mid w \Rightarrow ((w=z) \vee (z=1)))]$ Here $a \mid b$ denotes ... S2: Set of all positive integers S3: Set of all integers Which of the above sets satisfy $\phi$? S1 and S2 S1 and S3 S2 and S3 S1, S2 and S3
answered
Feb 12
in
Mathematical Logic
by
Tuhin Dutta
Loyal
(
9.1k
points)

1.9k
views
gate2019
engineeringmathematics
discretemathematics
mathematicallogic
0
votes
1
answer
31
Rosen ch1 Ex.1.6 Q10.b
What are relevant conclusion and explain rule of inference used ? "If i work ,it is either Sunny or partly sunny." " I worked last Monday or i worked last friday." " It was not Sunny on Tuesday."" It was not partly sunny on Friday "
answered
Feb 12
in
Mathematical Logic
by
Deepak Kumar 12
Active
(
1.6k
points)

21
views
kennethrosen
0
votes
0
answers
32
Kenneth Rosen Ex.1.3 Q.37
Express each of these statements using predicates and quantifiers. a) A passenger on an airline qualifies as an elite flyer if the passenger flies more than 25,000 miles in a year or takes more than 25 flights during that year.
asked
Feb 10
in
Mathematical Logic
by
himgta
Active
(
3.6k
points)

29
views
+1
vote
4
answers
33
GATE201910
Let $G$ be an arbitrary group. Consider the following relations on $G$: $R_1: \forall a , b \in G, \: a R_1 b \text{ if and only if } \exists g \in G \text{ such that } a = g^{1}bg$ $R_2: \forall a , b \in G, \: a R_2 b \text{ if and only if } a= b^{1}$ Which of the above is/are equivalence relation/relations? $R_1$ and $R_2$ $R_1$ only $R_2$ only Neither $R_1$ nor $R_2$
answered
Feb 10
in
Set Theory & Algebra
by
amangarg
(
63
points)

1.9k
views
gate2019
engineeringmathematics
discretemathematics
settheory&algebra
groups
+6
votes
4
answers
34
TIFR2018A6
What is the minimum number of students needed in a class to guarantee that there are at least $6$ students whose birthdays fall in the same month ? $6$ $23$ $61$ $72$ $91$
answered
Feb 10
in
Combinatory
by
Satbir
Active
(
5.1k
points)

311
views
tifr2018
pigeonholeprinciple
permutationsandcombinations
+17
votes
2
answers
35
TIFR2014A5
The rules for the University of Bombay fiveaside cricket competition specify that the members of each team must have birthdays in the same month. What is the minimum number of mathematics students needed to be enrolled in the department to guarantee that they can raise a team of students? $23$ $91$ $60$ $49$ None of the above.
answered
Feb 10
in
Combinatory
by
Satbir
Active
(
5.1k
points)

769
views
tifr2014
permutationsandcombinations
discretemathematics
normal
pigeonholeprinciple
+15
votes
6
answers
36
TIFR2016A15
In a tournament with $7$ teams, each team plays one match with every other team. For each match, the team earns two points if it wins, one point if it ties, and no points if it loses. At the end of all matches, the teams are ordered in the descending order of their ... total number of points a team must earn in order to be guaranteed a place in the next round? $13$ $12$ $11$ $10$ $9$
answered
Feb 10
in
Combinatory
by
Satbir
Active
(
5.1k
points)

581
views
tifr2016
permutationsandcombinations
discretemathematics
normal
+22
votes
6
answers
37
GATE2004IT35
In how many ways can we distribute $5$ distinct balls, $B_1$, $B_2$, ..., $B_5$ in $5$ distinct cells, $C_1$, $C_2$, ...., $C_5$ such that Ball $B_i$ is not in cell $C_i$, $\forall i= 1,2,...5$ and each cell contains exactly one ball? $44$ $96$ $120$ $3125$
answered
Feb 9
in
Combinatory
by
Satbir
Active
(
5.1k
points)

2.3k
views
gate2004it
permutationsandcombinations
normal
+7
votes
3
answers
38
TIFR2010A4
If the bank receipt is forged, then Mr. M is liable. If Mr. M is liable, he will go bankrupt. If the bank will loan him money, he will not go bankrupt. The bank will loan him money. Which of the following can be concluded from the above statements? Mr. M is liable The receipt is not forged Mr. M will go bankrupt The bank will go bankrupt None of the above
answered
Feb 9
in
Mathematical Logic
by
Ram Swaroop
Active
(
2.3k
points)

433
views
tifr2010
logicalreasoning
mathematicallogic
+13
votes
3
answers
39
CMI2010A02
We need to choose a team of $11$ from a pool of $15$ players and also select a captain. The number of different ways this can be done is $ \begin{pmatrix} 15 \\ 11 \end{pmatrix}$ $11$ . $ \begin{pmatrix} 15 \\ 11 \end{pmatrix}$ $15 . 14 . 13 . 12 . 11 .10 . 9 . 8 . 7 . 6 . 5$ $(15 . 14 . 13 . 12 . 11 .10 . 9 . 8 . 7 . 6 . 5) . 11$
answered
Feb 9
in
Combinatory
by
Satbir
Active
(
5.1k
points)

571
views
cmi2010
permutationsandcombinations
normal
discretemathematics
0
votes
2
answers
40
GATEBOOK2019DM112
Translate the following logic statement to English where, $A(x)$: $x$ is African, $F(x,y)$: x and y are friends. The universe for $x$ and $y$ is all the people in the world. $\forall x \exists y((A(x) \vee (F(x,y)))$ Every African has some African friend Every person who is not African has at least one friend Every person who has friend is not African None of these
answered
Feb 8
in
Mathematical Logic
by
KULDEEP SINGH 2
Junior
(
727
points)

148
views
gb2019dm1
discretemathematics
mathematicallogic
propositionallogic
quantifiers
To see more, click for all the
questions in this category
.
Quick search syntax
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
Recent Posts
Need suggestions for what to do next after Gate ??
For GATECSE Admissions 2019
Challenge to GATE keys: Question 26, If you also want to challenge the same, as I did!
How to follow Standard Textbooks?
Gate contest link is now open
All categories
General Aptitude
1.5k
Engineering Mathematics
7.1k
Discrete Mathematics
4.9k
Mathematical Logic
1.9k
Set Theory & Algebra
1.3k
Combinatory
874
Graph Theory
802
Probability
1k
Linear Algebra
692
Calculus
493
Digital Logic
2.7k
Programming & DS
4.9k
Algorithms
4.2k
Theory of Computation
5.3k
Compiler Design
2.1k
Operating System
4k
Databases
4k
CO & Architecture
3.5k
Computer Networks
4k
Non GATE
1.4k
Others
1.5k
Admissions
559
Exam Queries
555
Tier 1 Placement Questions
23
Job Queries
69
Projects
18
Follow @csegate
Recent questions and answers in Discrete Mathematics
Recent Blog Comments
Congrats Mamta! I saw your interview on...
Well it is quite nostalgic for me as if I have...
See in recent posts "For GATE CSE Admissions 2019"
which ppt are you referring to, can you share the...
I am not a ranker so you might not believe on my...
47,936
questions
52,337
answers
182,395
comments
67,819
users