Recent questions tagged tifr2015 / GATE Overflow for GATE CSE

25 votes

5 answers

1

TIFR CSE 2015 | Part B | Question: 15
Consider the following grammar (the start symbol is $E$) for generating expressions. $E \rightarrow T - E \mid T + E \mid T$ $T \rightarrow T * F \mid F$ $F \rightarrow 0 \mid1\mid 2\mid 3\mid 4\mid 5\mid 6\mid 7\mid 8\mid 9$ With respect to this grammar, which of the following trees is the valid evaluation tree for the expression $2*3*4 - 5*6+7$?

Consider the following grammar (the start symbol is $E$) for generating expressions.$E \rightarrow T - E \mid T + E \mid T$$T \rightarrow T * F \mid F$$F \rightarrow 0 \m...

makhdoom ghaya

3.1k views

makhdoom ghaya asked Dec 8, 2015

15 votes

3 answers

2

TIFR CSE 2015 | Part B | Question: 14
Consider the following concurrent program (where statements separated by | | with-in cobegin-coend are executed concurrently). x:=1 cobegin x:= x + 1 || x:= x + 1 || x:= x + 1 coend Reading and writing of variables is atomic but evaluation of expressions is not atomic. The ... $\left \{2, 4 \right \}$ $\left \{ 2, 3 \right \}$ $\left \{2 \right \}$

Consider the following concurrent program (where statements separated by | | with-in cobegin-coend are executed concurrently).x:=1 cobegin x:= x + 1 || x:= x + 1 || x:=...

makhdoom ghaya

2.2k views

makhdoom ghaya asked Dec 8, 2015

5 votes

2 answers

3

TIFR CSE 2015 | Part B | Question: 13
Two undirected graphs $G_{1}=(V_{1}, E_{1})$ and $G_{2}= (V_{2}, E_{2})$ are said to be isomorphic if there exist a bijection $\pi: V_{1} \rightarrow V_{2}$ such that for all $u, v \in V_{1}, (u, v) \in E_{1}$ ... $L$ is $NP$- hard. $L$ is undecidable. Only $(i)$ Only $(ii)$ Only $(iii)$ $(i)$ and $(ii)$ $(ii)$ and $(iii)$

Two undirected graphs $G_{1}=(V_{1}, E_{1})$ and $G_{2}= (V_{2}, E_{2})$ are said to be isomorphic if there exist a bijection $\pi: V_{1} \rightarrow V_{2}$ such that for...

makhdoom ghaya

1.0k views

makhdoom ghaya asked Dec 8, 2015

9 votes

2 answers

4

TIFR CSE 2015 | Part B | Question: 12
Let $t_{n}$ be the sum of the first $n$ natural numbers, for $n > 0$. A number is called triangular if it is equal to $t_{n}$ for some $n$. Which of the following statements are true: There exists three successive triangular numbers whose product is a ... $\text{(i)}$ only $\text{(ii)}$ only $\text{(iii)}$ only All of the above None of the above

Let $t_{n}$ be the sum of the first $n$ natural numbers, for $n 0$. A number is called triangular if it is equal to $t_{n}$ for some $n$. Which of the following statemen...

makhdoom ghaya

1.2k views

makhdoom ghaya asked Dec 8, 2015

20 votes

2 answers

5

TIFR CSE 2015 | Part B | Question: 11
Let $K_{n}$ be the complete graph on $n$ vertices labeled $\left\{1, 2,\dots ,n\right\}$ with $m=\frac{n (n - 1)}{2}$ edges. What is the number of spanning trees of $K_{n}$? $\frac{m}{n - 1}$ $m^{n - 1}$ $n^{n - 2}$ $n^{n - 1}$ None of the above

Let $K_{n}$ be the complete graph on $n$ vertices labeled $\left\{1, 2,\dots ,n\right\}$ with $m=\frac{n (n - 1)}{2}$ edges. What is the number of spanning trees of $K_{n...

makhdoom ghaya

2.2k views

makhdoom ghaya asked Dec 8, 2015

21 votes

2 answers

6

TIFR CSE 2015 | Part B | Question: 10
Consider the languages $L_{1}= \left\{a^{m}b^{n}c^{p} \mid (m = n \vee n = p) \wedge m + n + p \geq 10\right\}$ $L_{2}= \left\{a^{m}b^{n}c^{p} \mid (m = n \vee n = p) \wedge m + n + p \leq 10\right\}$ State which of the ... $L_{1}$ is regular and $L_{2}$ is not regular. $L_{1}$ is not regular and $L_{2}$ is regular. Both $L_{1}$ and $L_{2}$ are infinite.

Consider the languages $L_{1}= \left\{a^{m}b^{n}c^{p} \mid (m = n \vee n = p) \wedge m + n + p \geq 10\right\}$$L_{2}= \left\{a^{m}b^{n}c^{p} \mid (m = n \vee n = p) \wed...

makhdoom ghaya

3.0k views

makhdoom ghaya asked Dec 8, 2015

27 votes

2 answers

7

TIFR CSE 2015 | Part B | Question: 9
A Boolean expression is an expression made out of propositional letters (such as $p, q, r$) and operators $\wedge$, $\vee$ and $\neg$; e.g. $p\wedge \neg (q \vee \neg r)$. An expression is said to be ... Boolean expression is equivalent to an expression without $\wedge$ operator. Every Boolean expression is equivalent to an expression without $\neg$ operator.

A Boolean expression is an expression made out of propositional letters (such as $p, q, r$) and operators $\wedge$, $\vee$ and $\neg$; e.g. $p\wedge \neg (q \vee \neg r)$...

makhdoom ghaya

2.3k views

makhdoom ghaya asked Dec 8, 2015

25 votes

6 answers

8

TIFR CSE 2015 | Part B | Question: 8
Let $\sum_{1}= \left\{a\right\}$ be a one letter alphabet and $\sum_{2}= \left\{a, b\right\}$ be a two letter alphabet. A language over an alphabet is a set of finite length words comprising letters of the alphabet. Let $L_{1}$ and $L_{2}$ be the ... $L_{1}$ is countable but $L_{2}$ is not. $L_{2}$ is countable but $L_{1}$ is not. Neither of them is countable.

Let $\sum_{1}= \left\{a\right\}$ be a one letter alphabet and $\sum_{2}= \left\{a, b\right\}$ be a two letter alphabet. A language over an alphabet is a set of finite len...

makhdoom ghaya

4.6k views

makhdoom ghaya asked Dec 7, 2015

18 votes

4 answers

9

TIFR CSE 2015 | Part B | Question: 7
Let $a, b, c$ be regular expressions. Which of the following identities is correct? $(a + b)^{*} = a^{*}b^{*}$ $a(b + c) = ab + c$ $(a + b)^{*} = a^{*} + b^{*}$ $(ab + a)^{*}a = a(ba + a)^{*}$ None of the above.

Let $a, b, c$ be regular expressions. Which of the following identities is correct?$(a + b)^{*} = a^{*}b^{*}$$a(b + c) = ab + c$$(a + b)^{*} = a^{*} + b^{*}$$(ab + a)^{*}...

makhdoom ghaya

2.4k views

makhdoom ghaya asked Dec 7, 2015

15 votes

3 answers

10

TIFR CSE 2015 | Part B | Question: 6
Let $B$ consist of all binary strings beginning with a $1$ whose value when converted to decimal is divisible by $7$. $B$ can be recognized by a deterministic finite state automaton. $B$ can be recognized by a non-deterministic ... not by a deterministic push-down automaton. $B$ cannot be recognized by any push down automaton, deterministic or non-deterministic.

Let $B$ consist of all binary strings beginning with a $1$ whose value when converted to decimal is divisible by $7$.$B$ can be recognized by a deterministic finite state...

makhdoom ghaya

2.0k views

makhdoom ghaya asked Dec 7, 2015

28 votes

7 answers

11

TIFR CSE 2015 | Part B | Question: 5
Suppose $\begin{pmatrix} 0&1 &0&0&0&1 \\ 1&0&1&0&0&0 \\ 0&1&0&1&0&1 \\ 0&0&1&0&1&0 \\ 0&0&0&1&0&1 \\ 1&0&1&0&1&0 \end{pmatrix}$ is the adjacency ... the above adjacency matrix? Only $(i)$ Only $(ii)$ Only $(iii)$ Only $(iv)$ $(i)$ and $(ii)$

Suppose $\begin{pmatrix}0&1 &0&0&0&1 \\1&0&1&0&0&0 \\0&1&0&1&0&1 \\0&0&1&0&1&0 \\0&0&0&1&0&1 \\1&0&1&0&1&0\end{pmatrix}$is the adjacency matrix of an undirected graph...

makhdoom ghaya

4.3k views

makhdoom ghaya asked Dec 7, 2015

43 votes

4 answers

12

TIFR CSE 2015 | Part B | Question: 4
First, consider the tree on the left. On the right, the nine nodes of the tree have been assigned numbers from the set $\left\{1, 2,\ldots,9\right\}$ so that for every node, the numbers in its left subtree and right subtree lie in disjoint intervals (that is, all numbers in one subtree ... $2^{4}.3^{2}.5.9=6480$ $2^{3}.3.5.9=1080$ $2^{4}=16$ $2^{3}.3^{3}=216$

First, consider the tree on the left. On the right, the nine nodes of the tree have been assigned numbers from the set $\left\{1, 2,\ldots,9\right\}$ so that for every ...

makhdoom ghaya

4.2k views

makhdoom ghaya asked Dec 7, 2015

17 votes

2 answers

13

TIFR CSE 2015 | Part B | Question: 3
Consider the following code fragment in the $C$ programming language when run on a non-negative integer $n$. int f (int n) { if (n==0 || n==1) return 1; else return f (n - 1) + f(n - 2); } Assuming a typical implementation ... $n$. This algorithm runs in polynomial time in $n$ and the optimal running time is polynomial in $n$. The algorithm does not terminate.

Consider the following code fragment in the $C$ programming language when run on a non-negative integer $n$.int f (int n) { if (n==0 || n==1) return 1; else return f (n -...

makhdoom ghaya

1.9k views

makhdoom ghaya asked Dec 7, 2015

29 votes

2 answers

14

TIFR CSE 2015 | Part B | Question: 2
Consider the following undirected connected graph $G$ with weights on its edges as given in the figure below. A minimum spanning tree is a spanning tree of least weight and a maximum spanning tree is one with largest weight. A second best ... tree here. There is unique minimum spanning tree, however there is more than one second-best minimum spanning tree here.

Consider the following undirected connected graph $G$ with weights on its edges as given in the figure below. A minimum spanning tree is a spanning tree of least weight a...

makhdoom ghaya

3.6k views

makhdoom ghaya asked Dec 7, 2015

22 votes

3 answers

15

TIFR CSE 2015 | Part B | Question: 1
Consider the following recurrence relation: $T(n) = \begin{cases} 2T (\lfloor\sqrt{n}\rfloor)+ \log n & \text{if }n \geq 2 \\ 1& \text{if }n = 1 \end{cases}$ Which of the following statements is TRUE? $T(n)$ is $O(\log n)$. $T(n)$ ... but not $O(\log^{3/2} n)$. $T(n)$ is $O(\log^{2} n \cdot \log \log n)$ but not $O(\log^{2} n)$.

Consider the following recurrence relation:$T(n)= \begin{cases}2T (\lfloor\sqrt{n}\rfloor)+ \log n & \text{if }n \geq 2 \\ 1& \text{if }n = 1 \end{cases}$Which of the...

makhdoom ghaya

3.1k views

makhdoom ghaya asked Dec 5, 2015

7 votes

2 answers

16

TIFR CSE 2015 | Part A | Question: 15
Let $A$ and $B$ be non-empty disjoint sets of real numbers. Suppose that the average of the numbers in the first set is $\mu_{A}$ and the average of the numbers in the second set is $\mu_{B}$; let the corresponding variances be $v_{A}$ and $v_{B}$ respectively. If the average of the ... $p.v_{A}+ (1 - p). v_{B} + (\mu_{A}- \mu_{B})^{2}$

Let $A$ and $B$ be non-empty disjoint sets of real numbers. Suppose that the average of the numbers in the first set is $\mu_{A}$ and the average of the numbers in the se...

makhdoom ghaya

1.1k views

makhdoom ghaya asked Dec 5, 2015

14 votes

1 answer

17

TIFR CSE 2015 | Part A | Question: 14
Consider the following $3 \times 3$ matrices. $M_{1}=\begin{pmatrix} 0&1&1 \\ 1&0&1 \\ 1&1&0 \end{pmatrix} $ $M_{2}=\begin{pmatrix} 1&0&1 \\ 0&0&0 \\ 1&0&1 \end{pmatrix} $ How may $0-1$ column vectors of the ... are done modulo $2$, i.e, $3 = 1$ (modulo $2$), $4 = 0$ (modulo $2$)). None Two Three Four Eight

Consider the following $3 \times 3$ matrices.$M_{1}=\begin{pmatrix} 0&1&1 \\1&0&1 \\1&1&0 \end{pmatrix} $$M_{2}=\begin{pmatrix} 1&0&1 \\0&0&0 \\1&0&1 \end{pmatrix} ...

makhdoom ghaya

1.6k views

makhdoom ghaya asked Dec 5, 2015

12 votes

2 answers

18

TIFR CSE 2015 | Part A | Question: 13
Imagine the first quadrant of the real plane as consisting of unit squares. A typical square has $4$ corners: $(i, j), (i+1, j), (i+1, j+1),$and $(i, j+1)$, where $(i, j)$ is a pair of non-negative integers. Suppose a line segment $l$ ... point in the interior of the square. How many unit squares does $l$ pass through? $98,990$ $9,900$ $1,190$ $1,180$ $1,010$

Imagine the first quadrant of the real plane as consisting of unit squares. A typical square has $4$ corners: $(i, j), (i+1, j), (i+1, j+1),$and $(i, j+1)$, where $(i, j)...

makhdoom ghaya

1.9k views

makhdoom ghaya asked Dec 5, 2015

7 votes

2 answers

19

TIFR CSE 2015 | Part A | Question: 12
Consider two independent and identically distributed random variables $X$ and $Y$ uniformly distributed in $[0, 1]$. For $\alpha \in \left[0, 1\right]$, the probability that $\alpha$ max $(X, Y) < XY$ is $1/ (2\alpha)$ exp $(1 - \alpha)$ $1 - \alpha$ $(1 - \alpha)^{2}$ $1 - \alpha^{2}$

Consider two independent and identically distributed random variables $X$ and $Y$ uniformly distributed in $[0, 1]$. For $\alpha \in \left[0, 1\right]$, the probability t...

makhdoom ghaya

1.9k views

makhdoom ghaya asked Dec 5, 2015

15 votes

5 answers

20

TIFR CSE 2015 | Part A | Question: 11
Suppose that $f(x)$ is a continuous function such that $0.4 \leq f(x) \leq 0.6$ for $0 \leq x \leq 1$. Which of the following is always true? $f(0.5) = 0.5$. There exists $x$ between $0$ and $1$ such that $f(x) = 0.8x$. There exists $x$ between $0$ and $0.5$ such that $f(x) = x$. $f(0.5) > 0.5$. None of the above statements are always true.

Suppose that $f(x)$ is a continuous function such that $0.4 \leq f(x) \leq 0.6$ for $0 \leq x \leq 1$. Which of the following is always true?$f(0.5) = 0.5$.There exists $...

makhdoom ghaya

2.8k views

makhdoom ghaya asked Dec 5, 2015

5 votes

0 answers

21

TIFR CSE 2015 | Part A | Question: 10
Let $f(x), x\in \left[0, 1\right]$, be any positive real valued continuous function. Then $\displaystyle \lim_{n \rightarrow \infty} (n + 1) \int_{0}^{1} x^{n} f(x) \text{d}x$ equals. $\max_{x \in \left[0, 1\right]} f(x)$ $\min_{x \in \left[0, 1\right]} f(x)$ $f(0)$ $f(1)$ $\infty$

Let $f(x), x\in \left[0, 1\right]$, be any positive real valued continuous function. Then $\displaystyle \lim_{n \rightarrow \infty} (n + 1) \int_{0}^{1} x^{n} f(...

makhdoom ghaya

710 views

makhdoom ghaya asked Dec 5, 2015

3 votes

2 answers

22

TIFR CSE 2015 | Part A | Question: 9
Consider a square of side length $2$. We throw five points into the square. Consider the following statements: There will always be three points that lie on a straight line. There will always be a line connecting a pair of points such that two points lie on one side of ... $\text{(ii)}$ only $\text{(iii)}$ only $\text{(ii)}$ and $\text{(iii)}$ None of the above

Consider a square of side length $2$. We throw five points into the square. Consider the following statements:There will always be three points that lie on a straight lin...

makhdoom ghaya

1.0k views

makhdoom ghaya asked Dec 5, 2015

32 votes

4 answers

23

TIFR CSE 2015 | Part A | Question: 8
There is a set of $2n$ people: $n$ male and $n$ female. A good party is one with equal number of males and females (including the one where none are invited). The total number of good parties is. $2^{n}$ $n^{2}$ $\binom{n}{⌊n/2⌋}^{2}$ $\binom{2n}{n}$ None of the above

There is a set of $2n$ people: $n$ male and $n$ female. A good party is one with equal number of males and females (including the one where none are invited). The total n...

makhdoom ghaya

4.1k views

makhdoom ghaya asked Dec 5, 2015

20 votes

8 answers

24

TIFR CSE 2015 | Part A | Question: 7
A $1 \times 1$ chessboard has one square, a $2 \times 2$ chessboard has five squares. Continuing along this fashion, what is the number of squares on the regular $8 \times 8$ chessboard? $64$ $65$ $204$ $144$ $256$

A $1 \times 1$ chessboard has one square, a $2 \times 2$ chessboard has five squares. Continuing along this fashion, what is the number of squares on the regular $8 \time...

makhdoom ghaya

3.2k views

makhdoom ghaya asked Dec 5, 2015

20 votes

5 answers

25

TIFR CSE 2015 | Part A | Question: 6
Ram has a fair coin, i.e., a toss of the coin results in either head or tail and each event happens with probability exactly half $(1/2)$. He repeatedly tosses the coin until he gets heads in two consecutive tosses. The expected number of coin tosses that Ram does is. $2$ $4$ $6$ $8$ None of the above

Ram has a fair coin, i.e., a toss of the coin results in either head or tail and each event happens with probability exactly half $(1/2)$. He repeatedly tosses the coin u...

makhdoom ghaya

5.1k views

makhdoom ghaya asked Dec 5, 2015

18 votes

4 answers

26

TIFR CSE 2015 | Part A | Question: 5
What is logically equivalent to "If Kareena and Parineeti go to the shopping mall then it is raining": If Kareena and Parineeti do not go to the shopping mall then it is not raining. If Kareena and Parineeti do not go to the shopping ... shopping mall. If it is not raining then Kareena and Parineeti do not go to the shopping mall. None of the above.

What is logically equivalent to "If Kareena and Parineeti go to the shopping mall then it is raining":If Kareena and Parineeti do not go to the shopping mall then it is n...

makhdoom ghaya

2.2k views

makhdoom ghaya asked Dec 4, 2015

13 votes

1 answer

27

TIFR CSE 2015 | Part A | Question: 4
The Boolean function obtained by adding an inverter to each and every input of an $\text{AND}$ gate is: $\text{OR}$ $\text{XOR}$ $\text{NAND}$ $\text{NOR}$ None of the above

The Boolean function obtained by adding an inverter to each and every input of an $\text{AND}$ gate is:$\text{OR}$$\text{XOR}$$\text{NAND}$$\text{NOR}$None of the above

makhdoom ghaya

2.4k views

makhdoom ghaya asked Dec 2, 2015

5 votes

2 answers

28

TIFR CSE 2015 | Part A | Question: 3
Let $|z| < 1$. Define $M_{n}(z)= \sum_{i=1}^{10} z^{10^{n}(i - 1)}?$ what is $\prod\limits_{i=0}^{\infty} M_{i}(z)= M_{0}(z)\times M_{1}(z) \times M_{2}(z) \times ...?$ Can't be determined $1/ (1 - z)$ $1/ (1 + z)$ $1 - z^{9}$ None of the above

Let $|z| < 1$. Define $M_{n}(z)= \sum_{i=1}^{10} z^{10^{n}(i - 1)}?$ what is $\prod\limits_{i=0}^{\infty} M_{i}(z)= M_{0}(z)\times M_{1}(z) \times M_{2}(z) \t...

makhdoom ghaya

1.2k views

makhdoom ghaya asked Dec 2, 2015

9 votes

1 answer

29

TIFR CSE 2015 | Part A | Question: 2
Consider a circle with a circumference of one unit length. Let $d< \dfrac{1}{6}$. Suppose that we independently throw two arcs, each of length $d$, randomly on this circumference so that each arc is uniformly distributed along the circle circumference. The arc attaches itself exactly ... $(1 - 2d)$ It equals $1$ It equals $(1 - d)$ $(1 - d)$

Consider a circle with a circumference of one unit length. Let $d< \dfrac{1}{6}$. Suppose that we independently throw two arcs, each of length $d$, randomly on this circu...

makhdoom ghaya

1.1k views

makhdoom ghaya asked Dec 2, 2015

14 votes

5 answers

30

TIFR CSE 2015 | Part A | Question: 1
Consider a $6$-sided die with all sides not necessarily equally likely such that probability of an even number is $P (\left \{2, 4, 6 \right \}) =\dfrac{1}{2}$, probability of a multiple of $3$ is $P (\left \{3, 6 \right \}) = 1/3$ and probability of $1$ is ... $P(\left \{ 5 \right \}) \leq \dfrac{1}{3}$ None of the above

Consider a $6$-sided die with all sides not necessarily equally likely such that probability of an even number is $P (\left \{2, 4, 6 \right \}) =\dfrac{1}{2}$, probabil...

makhdoom ghaya

2.1k views

makhdoom ghaya asked Dec 2, 2015

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