Recent questions tagged tifr2014 / GATE Overflow for GATE CSE

40 votes

4 answers

1

TIFR CSE 2014 | Part B | Question: 20
Consider the following game. There is a list of distinct numbers. At any round, a player arbitrarily chooses two numbers $a, b$ from the list and generates a new number $c$ by subtracting the smaller number from the larger one. The numbers $a$ and $b$ are put ... $273$. What is the score of the best player for this game? $40$ $16$ $33$ $91$ $123$

Consider the following game. There is a list of distinct numbers. At any round, a player arbitrarily chooses two numbers $a, b$ from the list and generates a new number $...

makhdoom ghaya

3.3k views

makhdoom ghaya asked Nov 20, 2015

42 votes

4 answers

2

TIFR CSE 2014 | Part B | Question: 19
Consider the following tree with $13$ nodes. Suppose the nodes of the tree are randomly assigned distinct labels from $\left\{1, 2,\ldots,13\right\}$, each permutation being equally likely. What is the probability that the labels form a min-heap (i.e., every node receives the ... $\frac{2}{13}$ $\frac{1}{2^{13}}$

Consider the following tree with $13$ nodes.Suppose the nodes of the tree are randomly assigned distinct labels from $\left\{1, 2,\ldots,13\right\}$, each permutation bei...

makhdoom ghaya

5.6k views

makhdoom ghaya asked Nov 20, 2015

20 votes

3 answers

3

TIFR CSE 2014 | Part B | Question: 18
Let $k$ be an integer at least $4$ and let $\left[k\right]= \left\{1, 2,...,k\right\}$. Let $f:\left[k\right]^{4}\rightarrow \left\{0, 1\right\}$ be defined as follows: $f(y_{1}, y_{2}, y_{3}, y_{4}) = 1$ if an only if the $y_{i} 's$ are ... $2^{\left(\frac{k}{3}\right)}$ $\left(\frac{k}{3}\right)$ $\left(\frac{k}{3}\right)+1$ $4 \left(\frac{k}{3}\right)$

Let $k$ be an integer at least $4$ and let $\left[k\right]= \left\{1, 2,...,k\right\}$. Let $f:\left[k\right]^{4}\rightarrow \left\{0, 1\right\}$ be defined as follows: $...

makhdoom ghaya

2.3k views

makhdoom ghaya asked Nov 20, 2015

12 votes

3 answers

4

TIFR CSE 2014 | Part B | Question: 17
Let $f: \left\{0, 1\right\}^{n} \rightarrow \left\{0, 1\right\}$ ... $f$ is the MAJORITY function. $f$ is the PARITY function. $f$ outputs $1$ at exactly one assignment of the input bits.

Let $f: \left\{0, 1\right\}^{n} \rightarrow \left\{0, 1\right\}$ be a boolean function computed by a logical circuit comprising just binary AND and binary OR gates (assum...

makhdoom ghaya

3.2k views

makhdoom ghaya asked Nov 20, 2015

17 votes

5 answers

5

TIFR CSE 2014 | Part B | Question: 16
Consider the ordering relation $x\mid y \subseteq N \times N$ over natural numbers $N$ such that $x \mid y$ if there exists $z \in N$ such that $x ∙ z = y$. A set is called lattice if every finite subset has a least upper bound and greatest lower ... $(N, \mid)$ is a complete lattice. $(N, \mid)$ is a lattice but not a complete lattice.

Consider the ordering relation $x\mid y \subseteq N \times N$ over natural numbers $N$ such that $x \mid y$ if there exists $z \in N$ such that $x ∙ z = y$. A set is ca...

makhdoom ghaya

5.3k views

makhdoom ghaya asked Nov 20, 2015

18 votes

4 answers

6

TIFR CSE 2014 | Part B | Question: 15
Consider the set $N^{*}$ of finite sequences of natural numbers with $x \leq_{p}y$ denoting that sequence $x$ is a prefix of sequence $y$. Then, which of the following is true? $N^{*}$ is uncountable. $\leq_{p}$ is a total order. Every non ... -empty subset of $N^{*}$ has a greatest lower bound. Every non-empty finite subset of $N^{*}$ has a least upper bound.

Consider the set $N^{*}$ of finite sequences of natural numbers with $x \leq_{p}y$ denoting that sequence $x$ is a prefix of sequence $y$. Then, which of the following is...

makhdoom ghaya

3.6k views

makhdoom ghaya asked Nov 20, 2015

25 votes

2 answers

7

TIFR CSE 2014 | Part B | Question: 14
Which the following is FALSE? Complement of a recursive language is recursive. A language recognized by a non-deterministic Turing machine can also be recognized by a deterministic Turing machine. Complement of a context free language can ... enumerable then it is recursive. Complement of a non-recursive language can never be recognized by any Turing machine.

Which the following is FALSE?Complement of a recursive language is recursive.A language recognized by a non-deterministic Turing machine can also be recognized by a deter...

makhdoom ghaya

7.6k views

makhdoom ghaya asked Nov 20, 2015

28 votes

2 answers

8

TIFR CSE 2014 | Part B | Question: 13
Let $L$ be a given context-free language over the alphabet $\left\{a, b\right\}$. Construct $L_{1},L_{2}$ as follows. Let $L_{1}= L - \left\{xyx\mid x, y \in \left\{a, b\right\}^*\right\}$, and $L_{2} = L \cdot L$. Then, Both $L_{1}$ ... $L_{1}$ and $L_{2}$ both may not be context free. $L_{1}$ is regular but $L_{2}$ may not be context free.

Let $L$ be a given context-free language over the alphabet $\left\{a, b\right\}$. Construct $L_{1},L_{2}$ as follows. Let $L_{1}= L - \left\{xyx\mid x, y \in \left\{a, b\...

makhdoom ghaya

3.6k views

makhdoom ghaya asked Nov 20, 2015

22 votes

3 answers

9

TIFR CSE 2014 | Part B | Question: 12
Consider the following three statements: Intersection of infinitely many regular languages must be regular. Every subset of a regular language is regular. If $L$ is regular and $M$ is not regular then $L ∙ M$ is necessarily not regular. Which of the ... above? true, false, true. false, false, true. true, false, true. false, false, false. true, true, true.

Consider the following three statements:Intersection of infinitely many regular languages must be regular.Every subset of a regular language is regular.If $L$ is regular ...

makhdoom ghaya

5.0k views

makhdoom ghaya asked Nov 20, 2015

32 votes

4 answers

10

TIFR CSE 2014 | Part B | Question: 11
Consider the following recurrence relation: $T\left(n\right)= \begin{cases} T\left(\frac{n}{k}\right)+ T\left(\frac{3n}{4}\right)+ n & \text{if } n \geq 2 \\ 1& \text{if } n=1 \end{cases}$ Which of the following statements is FALSE? $T(n)$ is $O(n^{3/2})$ ... $k=4$. $T(n)$ is $O(n \log n)$ when $k=5$. $T(n)$ is $O(n)$ when $k=5$.

Consider the following recurrence relation:$T\left(n\right)=\begin{cases}T\left(\frac{n}{k}\right)+ T\left(\frac{3n}{4}\right)+ n & \text{if } n \geq 2 \\ 1& \text{if }...

makhdoom ghaya

5.7k views

makhdoom ghaya asked Nov 20, 2015

23 votes

2 answers

11

TIFR CSE 2014 | Part B | Question: 10
Given a set of $n$ distinct numbers, we would like to determine both the smallest and the largest number. Which of the following statements is TRUE? These two elements can be determined using $O\left(\log^{100}n\right)$ ... comparisons do not suffice, however these two elements can be determined using $2(n - 1)$ comparisons. None of the above.

Given a set of $n$ distinct numbers, we would like to determine both the smallest and the largest number. Which of the following statements is TRUE?These two elements can...

makhdoom ghaya

5.4k views

makhdoom ghaya asked Nov 19, 2015

49 votes

7 answers

12

TIFR CSE 2014 | Part B | Question: 9
Given a set of $n$ distinct numbers, we would like to determine the smallest three numbers in this set using comparisons. Which of the following statements is TRUE? These three elements can be determined using $O\left(\log^{2}n\right)$ ... $O(n)$ comparisons. None of the above.

Given a set of $n$ distinct numbers, we would like to determine the smallest three numbers in this set using comparisons. Which of the following statements is TRUE?These ...

makhdoom ghaya

10.1k views

makhdoom ghaya asked Nov 19, 2015

28 votes

3 answers

13

TIFR CSE 2014 | Part B | Question: 8
Which of these functions grows fastest with $n$? $e^{n}/n$. $e^{n-0.9 \log n}$. $2^{n}$. $\left(\log n\right)^{n-1}$. None of the above.

Which of these functions grows fastest with $n$?$e^{n}/n$.$e^{n-0.9 \log n}$.$2^{n}$.$\left(\log n\right)^{n-1}$.None of the above.

makhdoom ghaya

4.6k views

makhdoom ghaya asked Nov 19, 2015

19 votes

5 answers

14

TIFR CSE 2014 | Part B | Question: 7
Which of the following statements is TRUE for all sufficiently large $n$? $\displaystyle \left(\log n\right)^{\log\log n} < 2^{\sqrt{\log n}} < n^{1/4}$ $\displaystyle 2^{\sqrt{\log n}} < n^{1/4} < \left(\log n\right)^{\log\log n}$ ... $\displaystyle 2^{\sqrt{\log n}} < \left(\log n\right)^{\log\log n} < n^{1/4}$

Which of the following statements is TRUE for all sufficiently large $n$?$\displaystyle \left(\log n\right)^{\log\log n} < 2^{\sqrt{\log n}} < n^{1/4}$ $\displaystyle 2^{...

makhdoom ghaya

4.0k views

makhdoom ghaya asked Nov 19, 2015

31 votes

3 answers

15

TIFR CSE 2014 | Part B | Question: 6
Consider the problem of computing the minimum of a set of $n$ distinct numbers. We choose a permutation uniformly at random (i.e., each of the n! permutations of $\left \langle 1,....,n \right \rangle$ is chosen with probability $(1/n!)$ and we inspect the numbers in the order ... of times MIN is updated? $O (1)$ $H_{n}=\sum ^{n}_{i=1} 1/i$ $\sqrt{n}$ $n/2$ $n$

Consider the problem of computing the minimum of a set of $n$ distinct numbers. We choose a permutation uniformly at random (i.e., each of the n! permutations of $\left \...

makhdoom ghaya

2.7k views

makhdoom ghaya asked Nov 19, 2015

31 votes

1 answer

16

TIFR CSE 2014 | Part B | Question: 5
Let $G = (V,E)$ be an undirected connected simple (i.e., no parallel edges or self-loops) graph with the weight function $w: E \rightarrow \mathbb{R}$ on its edge set. Let $w(e_{1}) < w(e_{2}) < · · · < w(e_{m})$ ... $w_{i} = w(e_{i})$ by its square $w^{2}_{i}$ , then $T$ must still be a minimum spanning tree of this new instance.

Let $G = (V,E)$ be an undirected connected simple (i.e., no parallel edges or self-loops) graph with the weight function $w: E \rightarrow \mathbb{R}$ on its edge set. Le...

makhdoom ghaya

3.3k views

makhdoom ghaya asked Nov 19, 2015

35 votes

4 answers

17

TIFR CSE 2014 | Part B | Question: 4
Consider the following undirected graph with some edge costs missing. Suppose the wavy edges form a Minimum Cost Spanning Tree for $G$. Then, which of the following inequalities NEED NOT hold? cost$(a, b) \geq 6$. cost$(b, e) \geq 5$. cost$(e, f) \geq 5$. cost$(a, d) \geq 4$. cost$(b, c) \geq 4$.

Consider the following undirected graph with some edge costs missing.Suppose the wavy edges form a Minimum Cost Spanning Tree for $G$. Then, which of the following inequa...

makhdoom ghaya

5.1k views

makhdoom ghaya asked Nov 19, 2015

29 votes

2 answers

18

TIFR CSE 2014 | Part B | Question: 3
Consider the following directed graph. Suppose a depth-first traversal of this graph is performed, assuming that whenever there is a choice, the vertex earlier in the alphabetical order is to be chosen. Suppose the number of tree edges is $T$, the number of back edges is $B$ and the number of ... $B = 1$, $C = 2$, and $T = 3$. $B = 2$, $C = 2$, and $T = 1$.

Consider the following directed graph.Suppose a depth-first traversal of this graph is performed, assuming that whenever there is a choice, the vertex earlier in the alph...

makhdoom ghaya

5.4k views

makhdoom ghaya asked Nov 19, 2015

8 votes

3 answers

19

TIFR CSE 2014 | Part B | Question: 2
Consider the following code. def brian(n): count = 0 while ( n ! = 0 ) n = n & ( n-1 ) count = count + 1 return count Here $n$ is meant to be an unsigned integer. The operator & considers its arguments in binary and ... $n$. The result depends on the number of bits used to store unsigned integers.

Consider the following code.def brian(n): count = 0 while ( n ! = 0 ) n = n & ( n-1 ) count = count + 1 return countHere $n$ is meant to be an unsigned integer. The opera...

makhdoom ghaya

2.3k views

makhdoom ghaya asked Nov 19, 2015

10 votes

2 answers

20

TIFR CSE 2014 | Part B | Question: 1
Let $T$ be a rooted binary tree whose vertices are labelled with symbols $a, b, c, d, e, f, g, h, i, j, k$. Suppose the in-order (visit left subtree, visit root, visit right subtree) and post-order (visit left subtree, visit right ... How many leaves does the tree have? THREE. FOUR. FIVE. SIX. Cannot be determined uniquely from the given information.

Let $T$ be a rooted binary tree whose vertices are labelled with symbols $a, b, c, d, e, f, g, h, i, j, k$. Suppose the in-order (visit left subtree, visit root, visit ri...

makhdoom ghaya

2.3k views

makhdoom ghaya asked Nov 19, 2015

3 votes

1 answer

21

TIFR CSE 2014 | Part A | Question: 20
Consider the equation $x^{2}+y^{2}-3z^{2}-3t^{2}=0$. The total number of integral solutions of this equation in the range of the first $10000$ numbers, i.e., $1 \leq x, y, z, t \leq 10000$, is $200$ $55$ $100$ $1$ None of the above

Consider the equation $x^{2}+y^{2}-3z^{2}-3t^{2}=0$. The total number of integral solutions of this equation in the range of the first $10000$ numbers, i.e., $1 \leq x, y...

makhdoom ghaya

1.0k views

makhdoom ghaya asked Nov 19, 2015

8 votes

2 answers

22

TIFR CSE 2014 | Part A | Question: 19
Consider the following random function of $x$ $F(x) = 1 + Ux + Vx^{2} \bmod 5$, where $U$ and $V$ are independent random variables uniformly distributed over $\left\{0, 1, 2, 3, 4\right\}$. Which of the following is FALSE? $F(1)$ ... $F(1), F(2), F(3)$ are independent and identically distributed random variables. All of the above. None of the above.

Consider the following random function of $x$$F(x) = 1 + Ux + Vx^{2} \bmod 5$,where $U$ and $V$ are independent random variables uniformly distributed over $\left\{0, 1, ...

makhdoom ghaya

1.6k views

makhdoom ghaya asked Nov 19, 2015

3 votes

2 answers

23

TIFR CSE 2014 | Part A | Question: 18
We are given a collection of real numbers where a real number $a_{i}\neq 0$ occurs $n_{i}$ times. Let the collection be enumerated as $\left\{x_{1}, x_{2},...x_{n}\right\}$ so that $x_{1}=x_{2}=...=x_{n_{1}}=a_{1}$ and so on, and $n=\sum _{i}n_{i}$ ... $\min_{i} |a_{i}|$ $\min_{i} \left(n_{i}|a_{i}|\right)$ $\max_{i} |a_{i}|$ None of the above

We are given a collection of real numbers where a real number $a_{i}\neq 0$ occurs $n_{i}$ times. Let the collection be enumerated as $\left\{x_{1}, x_{2},...x_{n}\right\...

makhdoom ghaya

1.0k views

makhdoom ghaya asked Nov 19, 2015

16 votes

3 answers

24

TIFR CSE 2014 | Part A | Question: 17
A fair dice (with faces numbered $1, . . . , 6$) is independently rolled repeatedly. Let $X$ denote the number of rolls till an even number is seen and let $Y$ denote the number of rolls till $3$ is seen. Evaluate $E(Y |X = 2)$. $6\frac{5}{6}$ $6$ $5\frac{1}{2}$ $6\frac{1}{3}$ $5\frac{2}{3}$

A fair dice (with faces numbered $1, . . . , 6$) is independently rolled repeatedly. Let $X$ denote the number of rolls till an even number is seen and let $Y$ denote the...

makhdoom ghaya

4.0k views

makhdoom ghaya asked Nov 19, 2015

6 votes

2 answers

25

TIFR CSE 2014 | Part A | Question: 16
Let $x_{0}=1$ and $x_{n+1}= \frac{3+2x_{n}}{3+x_{n}}, n\geq 0$. $x_{\infty}=\displaystyle \lim_{n\rightarrow \infty}x_{n}$ is $\left(\sqrt{5}-1\right) / 2$ $\left(\sqrt{5}+1\right) / 2$ $\left(\sqrt{13}-1\right) / 2$ $\left(-\sqrt{13}-1\right) / 2$ None of the above

Let $x_{0}=1$ and$x_{n+1}= \frac{3+2x_{n}}{3+x_{n}}, n\geq 0$.$x_{\infty}=\displaystyle \lim_{n\rightarrow \infty}x_{n}$ is$\left(\sqrt{5}-1\right) / 2$$\left(\sqrt{5}+1\...

makhdoom ghaya

1.9k views

makhdoom ghaya asked Nov 19, 2015

3 votes

1 answer

26

TIFR CSE 2014 | Part A | Question: 15
Consider the following statements: $b_{1}= \sqrt{2}$, series with each $b_{i}= \sqrt{b_{i-1}+ \sqrt{2}}, i \geq 2$, converges. $\sum ^{\infty} _{i=1} \frac{\cos (i)}{i^{2}}$ converges. $\sum ^{\infty} _{i=0} b_{i}$ ... $(3)$ but not $(1)$. Statements $(1)$ and $(3)$ but not $(2)$. All the three statements. None of the three statements.

Consider the following statements:$b_{1}= \sqrt{2}$, series with each $b_{i}= \sqrt{b_{i-1}+ \sqrt{2}}, i \geq 2$, converges.$\sum ^{\infty} _{i=1} \frac{\cos (i)}{i^{2}}...

makhdoom ghaya

675 views

makhdoom ghaya asked Nov 14, 2015

5 votes

1 answer

27

TIFR CSE 2014 | Part A | Question: 14
Let $m$ and $n$ be any two positive integers. Then, which of the following is FALSE? $m + 1$ divides $m^{2n} − 1$. For any prime $p$, $m^{p} \equiv m (\mod p)$. If one of $m$, $n$ is prime, then there are integers $x, y$ such that $mx + ny = 1$. If $m < n$, then $m!$ divides $n(n − 1)(n − 2) \ldots (n − m + 1)$. If $2^{n} − 1$ is prime, then $n$ is prime.

Let $m$ and $n$ be any two positive integers. Then, which of the following is FALSE?$m + 1$ divides $m^{2n} − 1$.For any prime $p$, $m^{p} \equiv m (\mod p)$.If one of...

makhdoom ghaya

1.2k views

makhdoom ghaya asked Nov 14, 2015

4 votes

1 answer

28

TIFR CSE 2014 | Part A | Question: 13
Let $L$ be a line on the two dimensional plane. $L'$s intercepts with the $X$ and $Y$ axes are respectively $a$ and $b$. After rotating the co-ordinate system (and leaving $L$ untouched), the new intercepts are $a'$ and $b'$ respectively. Which ... $\frac{b}{a}+\frac{a}{b}=\frac{b'}{a'}+\frac{a'}{b'}$. None of the above.

Let $L$ be a line on the two dimensional plane. $L'$s intercepts with the $X$ and $Y$ axes are respectively $a$ and $b$. After rotating the co-ordinate system (and leavin...

makhdoom ghaya

1.5k views

makhdoom ghaya asked Nov 14, 2015

2 votes

0 answers

29

TIFR CSE 2014 | Part A | Question: 12
Let $f(x)= 2^{x}$. Consider the following inequality for real numbers $a, b$ and $0 < \lambda < 1$: $f(\lambda a + b) \leq \lambda f(a) + (1 - \lambda) f (\frac{b}{1 - \lambda})$. Consider the ... $(2)$. The above inequality holds under all the three conditions. The above inequality holds under none of the three conditions.

Let $f(x)= 2^{x}$. Consider the following inequality for real numbers $a, b$ and $0 < \lambda < 1$:$f(\lambda a + b) \leq \lambda f(a) + (1 - \lambda) f (\frac{b}{1 - \la...

makhdoom ghaya

501 views

makhdoom ghaya asked Nov 14, 2015

13 votes

3 answers

30

TIFR CSE 2014 | Part A | Question: 11
A large community practices birth control in the following peculiar fashion. Each set of parents continues having children until a son is born; then they stop. What is the ratio of boys to girls in the community if, in the absence of birth control, $51\%$ of the babies are born male? $51:49$ $1:1$ $49:51$ $51:98$ $98:51$

A large community practices birth control in the following peculiar fashion. Each set of parents continues having children until a son is born; then they stop. What is th...

makhdoom ghaya

1.6k views

makhdoom ghaya asked Nov 13, 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