search
Log In

Recent questions tagged tifr2014

34 votes
3 answers
1
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 back in the list. If the number ... $273$. What is the score of the best player for this game? $40$ $16$ $33$ $91$ $123$
asked Nov 20, 2015 in Algorithms makhdoom ghaya 1.1k views
29 votes
4 answers
2
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 minimum label in its subtree)? ... $\frac{2}{13}$ $\frac{1}{2^{13}}$
asked Nov 20, 2015 in DS makhdoom ghaya 1.9k views
16 votes
3 answers
3
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$ ... $2^{\left(\frac{k}{3}\right)}$ $\left(\frac{k}{3}\right)$ $\left(\frac{k}{3}\right)+1$ $4 \left(\frac{k}{3}\right)$
asked Nov 20, 2015 in Set Theory & Algebra makhdoom ghaya 956 views
8 votes
3 answers
4
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.
asked Nov 20, 2015 in Digital Logic makhdoom ghaya 919 views
14 votes
4 answers
5
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 bound. It is called a complete ... $|$. $\mid$ is a total order. $(N, \mid)$ is a complete lattice. $(N, \mid)$ is a lattice but not a complete lattice.
asked Nov 20, 2015 in Set Theory & Algebra makhdoom ghaya 1.3k views
13 votes
3 answers
6
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}$ ... bound. Every non-empty subset of $N^{*}$ has a greatest lower bound. Every non-empty finite subset of $N^{*}$ has a least upper bound.
asked Nov 20, 2015 in Set Theory & Algebra makhdoom ghaya 1k views
20 votes
2 answers
7
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 be recognized by a ... both recursively enumerable then it is recursive. Complement of a non-recursive language can never be recognized by any Turing machine.
asked Nov 20, 2015 in Theory of Computation makhdoom ghaya 2.2k views
25 votes
2 answers
8
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}$ and $L_{2}$ are regular. ... and $L_{2}$ is context free. $L_{1}$ and $L_{2}$ both may not be context free. $L_{1}$ is regular but $L_{2}$ may not be context free.
asked Nov 20, 2015 in Theory of Computation makhdoom ghaya 1.2k views
17 votes
3 answers
9
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 following gives the correct true/ ... of the above? true, false, true. false, false, true. true, false, true. false, false, false. true, true, true.
asked Nov 20, 2015 in Theory of Computation makhdoom ghaya 1.8k views
24 votes
3 answers
10
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})$ when $k=3$. $T(n)$ is $O(n \log n)$ ... $T(n)$ is $O(n \log n)$ when $k=4$. $T(n)$ is $O(n \log n)$ when $k=5$. $T(n)$ is $O(n)$ when $k=5$.
asked Nov 20, 2015 in Algorithms makhdoom ghaya 2.3k views
10 votes
2 answers
11
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. $O\left(\log^{100}n\right)$ ... $2(n - 1)$ comparisons. None of the above.
asked Nov 19, 2015 in Algorithms makhdoom ghaya 1.9k views
35 votes
6 answers
12
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.
asked Nov 19, 2015 in Algorithms makhdoom ghaya 3.2k views
24 votes
3 answers
13
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.
asked Nov 19, 2015 in Algorithms makhdoom ghaya 1.5k views
13 votes
5 answers
14
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}$
asked Nov 19, 2015 in Algorithms makhdoom ghaya 1.2k views
26 votes
3 answers
15
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 given by this permutation. ... number of times MIN is updated? $O (1)$ $H_{n}=\sum ^{n}_{i=1} 1/i$ $\sqrt{n}$ $n/2$ $n$
asked Nov 19, 2015 in Algorithms makhdoom ghaya 870 views
27 votes
1 answer
16
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})$ ... we replace each edge weight $w_{i} = w(e_{i})$ by its square $w^{2}_{i}$ , then $T$ must still be a minimum spanning tree of this new instance.
asked Nov 19, 2015 in Algorithms makhdoom ghaya 1.3k views
27 votes
4 answers
17
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$.
asked Nov 19, 2015 in Algorithms makhdoom ghaya 2k views
22 votes
1 answer
18
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 cross edges is $C$ ... $T = 3$. $B = 1$, $C = 2$, and $T = 3$. $B = 2$, $C = 2$, and $T = 1$.
asked Nov 19, 2015 in Algorithms makhdoom ghaya 1.5k views
7 votes
3 answers
19
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 computes their bit wise $AND$. ... of $n$. The code might go into an infinite loop for some $n$. The result depends on the number of bits used to store unsigned integers.
asked Nov 19, 2015 in Algorithms makhdoom ghaya 656 views
7 votes
2 answers
20
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 subtree, visit root) traversals ... How many leaves does the tree have? THREE. FOUR. FIVE. SIX. Cannot be determined uniquely from the given information.
asked Nov 19, 2015 in DS makhdoom ghaya 564 views
2 votes
1 answer
21
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
asked Nov 19, 2015 in Numerical Ability makhdoom ghaya 279 views
5 votes
2 answers
22
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.
asked Nov 19, 2015 in Probability makhdoom ghaya 441 views
2 votes
2 answers
23
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.
asked Nov 19, 2015 in Calculus makhdoom ghaya 283 views
11 votes
2 answers
24
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}$
asked Nov 19, 2015 in Probability makhdoom ghaya 1.6k views
4 votes
2 answers
25
Let $x_{0}=1$ and $x_{n+1}= \frac{3+2x_{n}}{3+x_{n}}, n\geq 0$. $x_{\infty}=\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.
asked Nov 19, 2015 in Calculus makhdoom ghaya 449 views
2 votes
1 answer
26
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}$ ... Statements $(2)$ and $(3)$ but not $(1)$. Statements $(1)$ and $(3)$ but not $(2)$. All the three statements. None of the three statements.
asked Nov 14, 2015 in Calculus makhdoom ghaya 231 views
3 votes
1 answer
27
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.
asked Nov 14, 2015 in Set Theory & Algebra makhdoom ghaya 279 views
3 votes
1 answer
28
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'$ ... $\frac{b}{a}+\frac{a}{b}=\frac{b'}{a'}+\frac{a'}{b'}$. None of the above.
asked Nov 14, 2015 in Numerical Ability makhdoom ghaya 348 views
2 votes
0 answers
29
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 following 3 conditions: $\lambda= 0.5$ ... $(3)$ but not under condition $(2)$. The above inequality holds under all the three conditions. The above inequality holds under none of the three conditions.
asked Nov 14, 2015 in Numerical Ability makhdoom ghaya 141 views
9 votes
1 answer
30
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$
asked Nov 13, 2015 in Numerical Ability makhdoom ghaya 523 views
...