Recent activity by keshore muralidharan / GATE Overflow for GATE CSE

5 answers

1

GATE CSE 2010 | Question: 26
Consider a company that assembles computers. The probability of a faulty assembly of any computer is $p$. The company therefore subjects each computer to a testing process. This testing process gives the correct result for any computer with a probability of $q$. What is the probability of a computer being declared faulty? $pq + (1 - p)(1 - q)$ $(1 - q)p$ $(1 - p)q$ $pq$

Consider a company that assembles computers. The probability of a faulty assembly of any computer is $p$. The company therefore subjects each computer to a testing proces...

7.7k views

answered Sep 12, 2020

7 answers

2

GATE CSE 2011 | Question: 34
A deck of $5$ cards (each carrying a distinct number from $1$ to $5$) is shuffled thoroughly. Two cards are then removed one at a time from the deck. What is the probability that the two cards are selected with the number on the first card being one higher than the number ... $\left(\dfrac{4}{25}\right)$ $\left(\dfrac{1}{4}\right)$ $\left(\dfrac{2}{5}\right)$

A deck of $5$ cards (each carrying a distinct number from $1$ to $5$) is shuffled thoroughly. Two cards are then removed one at a time from the deck. What is the probabil...

18.3k views

answered Sep 12, 2020

12 answers

3

GATE CSE 2016 Set 2 | Question: 05
Suppose that a shop has an equal number of LED bulbs of two different types. The probability of an LED bulb lasting more than $100$ hours given that it is of Type $1$ is $0.7$, and given that it is of Type $2$ is $0.4$. The probability that an LED bulb chosen uniformly at random lasts more than $100$ hours is _________.

Suppose that a shop has an equal number of LED bulbs of two different types. The probability of an LED bulb lasting more than $100$ hours given that it is of Type $1$ is ...

9.8k views

answered Sep 9, 2020

3 answers

4

GATE CSE 2016 Set 1 | Question: 04
A probability density function on the interval $[a, 1]$ is given by $1/x^{2}$ and outside this interval the value of the function is zero. The value of $a$ is _________.

A probability density function on the interval $[a, 1]$ is given by $1/x^{2}$ and outside this interval the value of the function is zero. The value of $a$ is _________.

9.9k views

answered Sep 9, 2020

6 answers

5

GATE CSE 2017 Set 2 | Question: 26
$P$ and $Q$ are considering to apply for a job. The probability that $P$ applies for the job is $\dfrac{1}{4},$ the probability that $P$ applies for the job given that $Q$ applies for the job is $\dfrac{1}{2},$ and the probability that $Q$ applies for the ... $\left(\dfrac{5}{6}\right)$ $\left(\dfrac{7}{8}\right)$ $\left(\dfrac{11}{12}\right)$

$P$ and $Q$ are considering to apply for a job. The probability that $P$ applies for the job is $\dfrac{1}{4},$ the probability that $P$ applies for the job given that $Q...

12.9k views

answered Sep 9, 2020

7 answers

6

GATE CSE 2017 Set 2 | Question: 31
For any discrete random variable $X$, with probability mass function $P(X=j)=p_j, p_j \geq 0, j \in \{0, \dots , N \}$, and $\Sigma_{j=0}^N \: p_j =1$, define the polynomial function $g_x(z) = \Sigma_{j=0}^N \: p_j \: z^j$. For a certain ... . The expectation of $Y$ is $N \beta(1-\beta)$ $N \beta$ $N (1-\beta)$ Not expressible in terms of $N$ and $\beta$ alone

For any discrete random variable $X$, with probability mass function$P(X=j)=p_j, p_j \geq 0, j \in \{0, \dots , N \}$, and $\Sigma_{j=0}^N \: p_j =1$, define the polynomi...

16.2k views

answered Sep 9, 2020

6 answers

7

GATE CSE 1997 | Question: 6.2
Let $G$ be the graph with $100$ vertices numbered $1$ to $100$. Two vertices $i$ and $j$ are adjacent if $\vert i-j \vert =8$ or $\vert i-j \vert=12$. The number of connected components in $G$ is $8$ $4$ $12$ $25$

Let $G$ be the graph with $100$ vertices numbered $1$ to $100$. Two vertices $i$ and $j$ are adjacent if $\vert i-j \vert =8$ or $\vert i-j \vert=12$. The number of con...

9.1k views

answered Aug 31, 2020

2 answers

8

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$...

13.1k views

answered Aug 29, 2020

11 answers

9

GATE CSE 2009 | Question: 2
What is the chromatic number of an $n$ vertex simple connected graph which does not contain any odd length cycle? Assume $n > 2$. $2$ $3$ $n-1$ $n$

What is the chromatic number of an $n$ vertex simple connected graph which does not contain any odd length cycle? Assume $n 2$.$2$$3$$n-1$ $n$

13.4k views

answered Aug 28, 2020

7 answers

10

GATE CSE 2009 | Question: 3
Which one of the following is TRUE for any simple connected undirected graph with more than $2$ vertices? No two vertices have the same degree. At least two vertices have the same degree. At least three vertices have the same degree. All vertices have the same degree.

Which one of the following is TRUE for any simple connected undirected graph with more than $2$ vertices? No two vertices have the same degree. At least two vertices ...

11.5k views

answered Aug 28, 2020

5 answers

11

GATE CSE 2010 | Question: 1
Let $G=(V, E)$ be a graph. Define $\xi(G) = \sum\limits_d i_d*d$, where $i_d$ is the number of vertices of degree $d$ in $G.$ If $S$ and $T$ are two different trees with $\xi(S) = \xi(T)$, then $| S| = 2| T |$ $| S | = | T | - 1$ $| S| = | T | $ $| S | = | T| + 1$

Let $G=(V, E)$ be a graph. Define $\xi(G) = \sum\limits_d i_d*d$, where $i_d$ is the number of vertices of degree $d$ in $G.$ If $S$ and $T$ are two different trees with ...

11.6k views

answered Aug 28, 2020

4 answers

12

GATE CSE 2015 Set 2 | Question: 50
In a connected graph, a bridge is an edge whose removal disconnects the graph. Which one of the following statements is true? A tree has no bridges A bridge cannot be part of a simple cycle Every edge of a clique with size $\geq 3$ is a bridge (A clique is any complete subgraph of a graph) A graph with bridges cannot have cycle

In a connected graph, a bridge is an edge whose removal disconnects the graph. Which one of the following statements is true?A tree has no bridgesA bridge cannot be part ...

14.8k views

answered Aug 28, 2020

9 answers

13

GATE IT 2005 | Question: 52
Let $G$ be a weighted undirected graph and e be an edge with maximum weight in $G$. Suppose there is a minimum weight spanning tree in $G$ containing the edge $e$. Which of the following statements is always TRUE? There exists a cutset in $G$ having ... $e$ cannot be contained in a cycle. All edges in $G$ have the same weight.

Let $G$ be a weighted undirected graph and e be an edge with maximum weight in $G$. Suppose there is a minimum weight spanning tree in $G$ containing the edge $e$. Which ...

20.9k views

answered Aug 22, 2020

8 answers

14

GATE CSE 2014 Set 2 | Question: 38
Suppose $P, Q, R, S, T$ are sorted sequences having lengths $20, 24, 30, 35, 50$ respectively. They are to be merged into a single sequence by merging together two sequences at a time. The number of comparisons that will be needed in the worst case by the optimal algorithm for doing this is ____.

Suppose $P, Q, R, S, T$ are sorted sequences having lengths $20, 24, 30, 35, 50$ respectively. They are to be merged into a single sequence by merging together two sequen...

25.2k views

answered Aug 21, 2020

7 answers

15

GATE CSE 2015 Set 2 | Question: 45
Suppose you are provided with the following function declaration in the C programming language. int partition(int a[], int n); The function treats the first element of $a[\:]$ as a pivot and rearranges the array so that all elements less than or equal to the pivot is in the ... $(a, $ left_end$, k)$ $(a, n-$left_end$-1, k-$left_end$-1)$ and $(a, $left_end$, k)$

Suppose you are provided with the following function declaration in the C programming language.int partition(int a[], int n);The function treats the first element of $a[\...

16.8k views

answered Aug 21, 2020

7 answers

16

GATE CSE 2017 Set 2 | Question: 38
Consider the following C function int fun(int n) { int i, j; for(i=1; i<=n; i++) { for (j=1; j<n; j+=i) { printf("%d %d", i, j); } } } Time complexity of $fun$ in terms of $\Theta$ notation is $\Theta(n \sqrt{n})$ $\Theta(n^2)$ $\Theta(n \: \log n)$ $\Theta(n^2 \log n)$

Consider the following C functionint fun(int n) { int i, j; for(i=1; i<=n; i++) { for (j=1; j<n; j+=i) { printf("%d %d", i, j); } } }Time complexity of $fun$ in terms of ...

25.1k views

answered Aug 21, 2020

7 answers

17

GATE CSE 2017 Set 2 | Question: 03
Match the algorithms with their time complexities: ... $P\rightarrow (iv) \quad Q \rightarrow(iii)\quad r \rightarrow(ii) \quad S\rightarrow(i)$

Match the algorithms with their time complexities:$$\begin{array}{|l|l|}\hline \textbf{Algorithms} & \textbf{Time Complexity} \\\hline \text{P. Tower of Hanoi with $n$...

7.0k views

answered Aug 21, 2020

7 answers

18

GATE CSE 2019 | Question: 40
Consider the following statements: The smallest element in a max-heap is always at a leaf node The second largest element in a max-heap is always a child of a root node A max-heap can be constructed from a binary search tree in $\Theta(n)$ time A binary search tree ... time Which of the above statements are TRUE? I, II and III I, II and IV I, III and IV II, III and IV

Consider the following statements:The smallest element in a max-heap is always at a leaf nodeThe second largest element in a max-heap is always a child of a root nodeA ma...

20.8k views

answered Aug 21, 2020

4 answers

19

GATE CSE 1997 | Question: 6.6
Which of the following languages over $\left\{a,b,c\right\}$ is accepted by a deterministic pushdown automata? $\left\{ wcw^R \mid w \in \left\{a,b\right\}^*\right\}$ $\left\{ ww^R \mid w \in \{a,b,c\}^*\right\}$ ... $w^R$ is the string obtained by reversing $'w'$.

Which of the following languages over $\left\{a,b,c\right\}$ is accepted by a deterministic pushdown automata?$\left\{ wcw^R \mid w \in \left\{a,b\right\}^*\right\}$$\lef...

10.9k views

answered Aug 17, 2020

4 answers

20

GATE CSE 1997 | Question: 6.5
Which one of the following is not decidable? Given a Turing machine $M$, a string $s$ and an integer $k$, $M$ accepts $s$ within $k$ steps Equivalence of two given Turing machines Language accepted by a given finite state machine is not empty Language generated by a context free grammar is non-empty

Which one of the following is not decidable?Given a Turing machine $M$, a string $s$ and an integer $k$, $M$ accepts $s$ within $k$ stepsEquivalence of two given Turing m...

10.2k views

answered Aug 17, 2020

5 answers

21

GATE CSE 1997 | Question: 3.4
Given $\Sigma=\{a,b\}$, which one of the following sets is not countable? Set of all strings over $\Sigma$ Set of all languages over $\Sigma$ Set of all regular languages over $\Sigma$ Set of all languages over $\Sigma$ accepted by Turing machines

Given $\Sigma=\{a,b\}$, which one of the following sets is not countable?Set of all strings over $\Sigma$Set of all languages over $\Sigma$Set of all regular languages ov...

12.5k views

answered Aug 17, 2020

3 answers

22

GATE CSE 2002 | Question: 2.5
The finite state machine described by the following state diagram with $A$ as starting state, where an arc label is $x/y,$ and $x$ stands for $1$-bit input and $y$ stands for $2$-bit output outputs the sum of the present and the ... the input outputs $01$ whenever the input sequence contains $11$ outputs $00$ whenever the input sequence contains $10$ none of the above

The finite state machine described by the following state diagram with $A$ as starting state, where an arc label is $x/y,$ and $x$ stands for $1$-bit input and $y$ stands...

11.5k views

answered Aug 17, 2020

3 answers

23

GATE CSE 2003 | Question: 52
Consider two languages $L_1$ and $L_2$ each on the alphabet $\Sigma$. Let $f : \Sigma^* \to \Sigma^*$ be a polynomial time computable bijection such that $(\forall x) [ x\in L_1$ iff $f(x) \in L_2]$. Further, let $f^{-1}$ be also polynomial ... $\in NP$ and $L_2$ $\in P$ $L_1$ is undecidable and $L_2$ is decidable $L_1$ is recursively enumerable and $L_2$ is recursive

Consider two languages $L_1$ and $L_2$ each on the alphabet $\Sigma$. Let $f : \Sigma^* \to \Sigma^*$ be a polynomial time computable bijection such that $(\forall x) [ x...

8.5k views

answered Aug 16, 2020

4 answers

24

GATE CSE 2003 | Question: 13
Nobody knows yet if $P=NP$. Consider the language $L$ defined as follows.$L = \begin{cases} (0+1)^* & \text{ if } P = NP \\ \phi & otherwise \end{cases} $Which of the following statements is true? $L$ is recursive $L$ is ... but not recursive $L$ is not recursively enumerable Whether $L$ is recursively enumerable or not will be known after we find out if $P=NP$

Nobody knows yet if $P=NP$. Consider the language $L$ defined as follows.$$L = \begin{cases} (0+1)^* & \text{ if } P = NP \\ \phi & otherwise \end{cases} $$Which of the f...

9.7k views

answered Aug 16, 2020

4 answers

25

GATE CSE 2006 | Question: 32, ISRO2016-35
Consider the following statements about the context free grammar $G = \left \{ S \rightarrow SS, S \rightarrow ab, S \rightarrow ba, S \rightarrow \epsilon \right \} $ $G$ is ambiguous $G$ produces all strings with equal number of $a$'s ... combination below expresses all the true statements about $G$? I only I and III only II and III only I, II and III

Consider the following statements about the context free grammar$$G = \left \{ S \rightarrow SS, S \rightarrow ab, S \rightarrow ba, S \rightarrow \epsilon \right \} $$$G...

28.9k views

answered Aug 15, 2020

8 answers

26

GATE CSE 2006 | Question: 34
Consider the regular language $L=(111+11111)^{*}.$ The minimum number of states in any DFA accepting this languages is: $3$ $5$ $8$ $9$

Consider the regular language $L=(111+11111)^{*}.$ The minimum number of states in any DFA accepting this languages is:$3$$5$$8$$9$

34.7k views

answered Aug 15, 2020

6 answers

27

GATE CSE 2006 | Question: 19
Let $L_1=\{0^{n+m}1^n0^m\mid n,m\geq 0 \}$, $L_2=\{0^{n+m}1^{n+m}0^m\mid n,m\geq 0\}$ and $L_3=\{0^{n+m}1^{n+m}0^{n+m}\mid n,m\geq 0\} $. Which of these languages are NOT context free? $L_1$ only $L_3$ only $L_1$ and $L_2$ $L_2$ and $L_3$

Let$L_1=\{0^{n+m}1^n0^m\mid n,m\geq 0 \}$,$L_2=\{0^{n+m}1^{n+m}0^m\mid n,m\geq 0\}$ and$L_3=\{0^{n+m}1^{n+m}0^{n+m}\mid n,m\geq 0\} $. Which of these languages are NOT c...

15.6k views

answered Aug 15, 2020

2 answers

28

GATE 2006 - 30
For S ∈ (0 + 1) * let d(s) denote the decimal value of s (e.g. d(101) = 5). Let L = {s ∈ (0 + 1)* d(s)mod5 = 2 and d(s)mod7 != 4}. Which one of the following statements is true? A L is recursively enumerable, but not recursive B L is recursive, but not context-free C L is context-free, but not regular D L is regular

For S ∈ (0 + 1) * let d(s) denote the decimal value of s (e.g. d(101) = 5). Let L = {s ∈ (0 + 1)* d(s)mod5 = 2 and d(s)mod7 != 4}. Which one of the following statemen...

1.6k views

answered Aug 15, 2020

3 answers

29

GATE IT 2008 | Question: 35
Which of the following languages is (are) non-regular? $L_1 = \{0^m1^n \mid 0 \leq m \leq n \leq 10000\}$ $L_2 = \{w \mid w $ reads the same forward and backward$\}$ $L_3 = \{w \in \{0, 1\} ^* \mid w$ contains an even number of 0's and an even number of 1's$\}$ $L_2$ and $L_3$ only $L_1$ and $L_2$ only $L_3$ only $L_2$ only

Which of the following languages is (are) non-regular?$L_1 = \{0^m1^n \mid 0 \leq m \leq n \leq 10000\}$$L_2 = \{w \mid w $ reads the same forward and backward$\}$$L_3 = ...

7.4k views

answered Aug 14, 2020

5 answers

30

GATE IT 2008 | Question: 6
Let $N$ be an NFA with $n$ states and let $M$ be the minimized DFA with m states recognizing the same language. Which of the following in NECESSARILY true? $m \leq 2^n$ $n \leq m$ $M$ has one accept state $m = 2^n$

Let $N$ be an NFA with $n$ states and let $M$ be the minimized DFA with m states recognizing the same language. Which of the following in NECESSARILY true?$m \leq 2^n$$...

10.9k views

answered Aug 14, 2020

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