search
Log In

Recent questions tagged tifr2013

29 votes
4 answers
1
Suppose $n$ processors are connected in a linear array as shown below. Each processor has a number. The processors need to exchange numbers so that the numbers eventually appear in ascending order (the processor $\rm P1$ should have the minimum value and the the processor $\rm Pn$ should ... values? $n \log n$ steps $n^2$ steps $n$ steps $n^{1.5}$ steps The algorithm is not guaranteed to sort
asked Nov 8, 2015 in Algorithms makhdoom ghaya 1.2k views
20 votes
3 answers
2
In a relational database there are three relations: Customers = $C$(CName), Shops = $S$(SName), Buys = $B$(CName, SName). Which of the following relational algebra expressions returns the names of shops that have no customers at all? [Here $\Pi$ is the projection operator.] $\Pi _{S Name}B$ $S - B$ $S - \Pi _{S Name}B$ $S - \Pi _{S Name}((C \times S) - B)$ None of the above
asked Nov 8, 2015 in Databases makhdoom ghaya 879 views
15 votes
4 answers
3
Let $S$ be a set of numbers. For $x \in S$, the rank of $x$ is the number of elements in $S$ that are less than or equal to $x$. The procedure Select$(S, r)$ takes a set $S$ of numbers and a rank $r\left(1 \leq r \leq |S|\right)$ and returns the element in $S$ of rank $r$. The ... · $|S| \log |S|$ constant · $|S|$ constant · $|S||R|$ constant · $|R| \log |S|$ constant · $|S|(1 + \log |R|)$
asked Nov 8, 2015 in Algorithms makhdoom ghaya 752 views
12 votes
2 answers
4
In a connected weighted graph with $n$ vertices, all the edges have distinct positive integer weights. Then, the maximum number of minimum weight spanning trees in the graph is $1$ $n$ equal to number of edges in the graph. equal to maximum weight of an edge of the graph. $n^{n-2}$
asked Nov 8, 2015 in Algorithms makhdoom ghaya 616 views
11 votes
4 answers
5
Consider a function $T_{k, n}: \left\{0, 1\right\}^{n}\rightarrow \left\{0, 1\right\}$ which returns $1$ if at least $k$ of its $n$ inputs are $1$. Formally, $T_{k, n}(x)=1$ if $\sum ^{n}_{1} x_{i}\geq k$. Let $y \in \left\{0, 1\right\}^{n}$ be such that $y$ has ... $y_{i}$ is omitted) is equivalent to $T_{k-1}, n(y)$ $T_{k, n}(y)$ $y_{i}$ $\neg y_{i}$ None of the above.
asked Nov 8, 2015 in Set Theory & Algebra makhdoom ghaya 524 views
6 votes
1 answer
6
Let $G$ be an undirected graph with $n$ vertices. For any subset $S$ of vertices, the set of neighbours of $S$ consists of the union of $S$ and the set of vertices $S'$ that are connected to some vertex in $S$ by an edge of $G$. The graph $G$ has the nice property that every subset of ... $O \left(\sqrt{n}\right)$ but not $O (\log n)$ $O (n)$ but not $O \left(\sqrt{n}\right)$
asked Nov 7, 2015 in Algorithms makhdoom ghaya 501 views
21 votes
2 answers
7
Assume a demand paged memory system where ONLY THREE pages can reside in the memory at a time. The following sequence gives the order in which the program references the pages. $1, 3, 1, 3, 4, 2, 2, 4$ Assume that least frequently used page is replaced when necessary. If ... , respectively $1,1,1,2$ times, respectively $1,1,1,1$ times, respectively $2,1,2,2$ times, respectively None of the above
asked Nov 7, 2015 in Operating System makhdoom ghaya 827 views
36 votes
3 answers
8
Given a binary tree of the following form and having $n$ nodes, the height of the tree is $\Theta \left(\log n\right)$ $\Theta \left(n\right)$ $\Theta \left(\sqrt{n}\right)$ $\Theta \left(n / \log n\right)$ None of the above.
asked Nov 7, 2015 in DS makhdoom ghaya 1.3k views
18 votes
1 answer
9
It takes $O(n)$ time to find the median in a list of $n$ elements, which are not necessarily in sorted order while it takes only $O(1)$ time to find the median in a list of $n$ sorted elements. How much time does it take to find the median of $2n$ elements which are given as two lists of $n$ ... not $O \left(\log n\right)$ $O (n)$ but not $O (\sqrt{n})$ $O \left(n \log n\right)$ but not $O (n)$
asked Nov 7, 2015 in Algorithms makhdoom ghaya 970 views
15 votes
3 answers
10
Which of the following statements is FALSE? The intersection of a context free language with a regular language is context free. The intersection of two regular languages is regular. The intersection of two context free languages is context free The intersection of a ... a regular language is context free. The intersection of a regular language and the complement of a regular language is regular.
asked Nov 7, 2015 in Theory of Computation makhdoom ghaya 891 views
3 votes
1 answer
11
Let $m, n$ be positive integers with $m$ a power of $2$. Let $s= 100 n^{2} \log m$. Suppose $S_{1}, S_{2},\dots ,S_{m}$ are subsets of ${1, 2, \dots, s}$ such that $ \mid S_{i} \mid= 10 n \log m$ and $ \mid S_{i} \cap S_{j} \mid \leq \log m$ for all $1 \leq i \lt j \leq m$. Such a ... $0.9$ if $x ∉ T$. $1$ if $x \in T$ and at least $0.9$ if $x ∉ T$. At least $0.9$ if $x \in T$ and $1$ if $x ∉ T$.
asked Nov 7, 2015 in Probability makhdoom ghaya 308 views
6 votes
1 answer
12
Suppose $n$ straight lines are drawn on a plane. When these lines are removed, the plane falls apart into several connected components called regions. $A$ region $R$ is said to be convex if it has the following property: whenever two points are in $R$, then the ... regions are produced, but they need not all be convex. All regions are convex but there may be exponentially many of them.
asked Nov 6, 2015 in Numerical Ability makhdoom ghaya 310 views
14 votes
2 answers
13
Which one of the following languages over the alphabet ${0, 1}$ is regular? The language of balanced parentheses where $0, 1$ are thought of as $(,)$ respectively. The language of palindromes, i.e. bit strings $x$ ... $L^*$, where $L$ is the language in $(c)$ above. $\left \{ 0^{m} 1^{n} | 1 \leq m \leq n\right \}$
asked Nov 6, 2015 in Theory of Computation makhdoom ghaya 1.2k views
4 votes
1 answer
14
Which of the following is not implied by $P=NP$? $3$SAT can be solved in polynomial time. Halting problem can be solved in polynomial time. Factoring can be solved in polynomial time. Graph isomorphism can be solved in polynomial time. Travelling salesman problem can be solved in polynomial time.
asked Nov 6, 2015 in Algorithms makhdoom ghaya 441 views
23 votes
2 answers
15
Let $L$ and $L'$ be languages over the alphabet $\Sigma $. The left quotient of $L$ by $L'$ is $L/L'\overset{{def}}{=} \left\{w \in \Sigma^* : wx ∈ L\text{ for some }x \in L'\right\}$ Which of the following is true? If $L/L'$ is regular then $L'$ is regular. If $L$ is ... . If $L/L'$ is regular then $L$ is regular. $L/L'$ is a subset of $L$. If $L/L'$ and $L'$ are regular, then $L$ is regular.
asked Nov 6, 2015 in Theory of Computation makhdoom ghaya 985 views
25 votes
3 answers
16
Given a weighted directed graph with $n$ vertices where edge weights are integers (positive, zero, or negative), determining whether there are paths of arbitrarily large weight can be performed in time $O(n)$ $O(n . \log(n))$ but not $O (n)$ $O(n^{1.5})$ but not $O (n \log n)$ $O(n^{3})$ but not $O(n^{1.5})$ $O(2^{n})$ but not $O(n^{3})$
asked Nov 6, 2015 in Algorithms makhdoom ghaya 1.6k views
14 votes
4 answers
17
A set $S$ together with partial order $\ll$ is called a well order if it has no infinite descending chains, i.e. there is no infinite sequence $x_1, x_2,\ldots$ of elements from $S$ such that $x_{i+1} \ll x_i$ and $x_{i+1} \neq x_i$ for all $i$. Consider the set of all ... there are only $2^{24}$ words. $W$ is not a partial order. $W$ is a partial order but not a well order. $W$ is a well order.
asked Nov 6, 2015 in Set Theory & Algebra makhdoom ghaya 882 views
17 votes
3 answers
18
How many $4 \times 4$ matrices with entries from ${0, 1}$ have odd determinant? Hint: Use modulo $2$ arithmetic. $20160$ $32767$ $49152$ $57343$ $65520$
asked Nov 6, 2015 in Linear Algebra makhdoom ghaya 1.5k views
2 votes
1 answer
19
Consider polynomials in a single variable $x$ of degree $d$. Suppose $d < n/2$. For such a polynomial $p(x)$, let $C_{p}$ denote the $n$-tuple $(P\left ( i \right ))_{1 \leq i \leq n}$. For any two such distinct polynomials $p, q,$ the number of coordinates where the tuples $C_{p}, C_{q}$ differ is. At most $d$ At most $n - d$ Between $d$ and $n - d$ At least $n - d$ None of the above.
asked Nov 6, 2015 in Numerical Ability makhdoom ghaya 152 views
20 votes
2 answers
20
Let $G= (V, E)$ be a simple undirected graph on $n$ vertices. A colouring of $G$ is an assignment of colours to each vertex such that endpoints of every edge are given different colours. Let $\chi (G)$ denote the chromatic number of $G$, i.e. the minimum numbers of colours needed for ... $a\left(G\right)\leq \frac{n}{\chi \left(G\right)}$ None of the above.
asked Nov 5, 2015 in Graph Theory makhdoom ghaya 1.2k views
7 votes
5 answers
21
Consider a well functioning clock where the hour, minute and the seconds needles are exactly at zero. How much time later will the minutes needle be exactly one minute ahead ($1/60$ th of the circumference) of the hours needle and the seconds needle again exactly at zero? ... an integer multiple of $1/60$ th of the circumference. $144$ minutes $66$ minutes $96$ minutes $72$ minutes $132$ minutes
asked Nov 5, 2015 in Numerical Ability makhdoom ghaya 572 views
5 votes
2 answers
22
Consider a sequence of numbers $\large (\epsilon _{n}: n= 1, 2,...)$, such that $\epsilon _{1}=10$ and $\large \epsilon _{n+1}=\dfrac{20\epsilon _{n}}{20+\epsilon _{n}}$ for $n\geq 1$. Which of the following statements is true? Hint: Consider the sequence of ... $\large (\epsilon _{n}: n= 1, 2,...)$ is decreasing and then increasing. Finally it converges to $1.$ None of the above.
asked Nov 5, 2015 in Numerical Ability makhdoom ghaya 335 views
3 votes
1 answer
23
Consider three independent uniformly distributed (taking values between $0$ and $1$) random variables. What is the probability that the middle of the three values (between the lowest and the highest value) lies between $a$ and $b$ where $0 ≤ a < b ≤ 1$? $3 (1 - b) a (b - a)$ $3 ((b - a) - (b^{2}- a^{2})/2)$ $6 (1 - b) a (b - a)$ $(1 - b) a (b - a)$ $6 ((b^{2}- a^{2})/ 2 - (b^{3} - a^{3})/3)$.
asked Nov 5, 2015 in Probability makhdoom ghaya 347 views
6 votes
4 answers
24
A stick of unit length is broken into two at a point chosen at random. Then, the larger part of the stick is further divided into two parts in the ratio $4:3$. What is the probability that the three sticks that are left CANNOT form a triangle? $1/4$ $1/3$ $5/6$ $1/2$ $\log_{e}(2)/2$
asked Nov 5, 2015 in Probability makhdoom ghaya 588 views
7 votes
2 answers
25
The minimum of the function $f(x) = x \log_{e}(x)$ over the interval $[\frac{1}{2}, \infty )$ is $0$ $-e$ $\frac{-\log_{e}(2)}{2}$ $\frac{-1}{e}$ None of the above
asked Nov 5, 2015 in Calculus makhdoom ghaya 486 views
3 votes
2 answers
26
Let $\DeclareMathOperator{S}{sgn} \S (x)= \begin{cases} +1 & \text{if } x \geq 0 \\ -1 & \text{if } x < 0 \end{cases}$ What is the value of the following summation? $\sum_{i=0}^{50} \S \left ( (2i - 1) (2i - 3) \dots (2i - 99) \right)$ $0$ $-1$ $+1$ $25$ $50$
asked Nov 4, 2015 in Numerical Ability makhdoom ghaya 234 views
14 votes
5 answers
27
An unbiased die is thrown $n$ times. The probability that the product of numbers would be even is $\dfrac{1}{(2n)}$ $\dfrac{1}{[(6n)!]}$ $1 - 6^{-n}$ $6^{-n}$ None of the above.
asked Nov 4, 2015 in Probability makhdoom ghaya 632 views
8 votes
3 answers
28
Doctors $A$ and $B$ perform surgery on patients in stages $III$ and $IV$ of a disease. Doctor $A$ has performed a $100$ surgeries (on $80$ stage $III$ and $20$ stage $IV$ patients) and $80$ out of her $100$ patients have survived ($78$ ... $B$ since she appears to be more successful There is not enough data since the choice depends on the stage of the disease the patient is suffering from.
asked Nov 4, 2015 in Probability makhdoom ghaya 636 views
6 votes
1 answer
29
Among numbers $1$ to $1000$ how many are divisible by $3$ or $7$? $333$ $142$ $475$ $428$ None of the above.
asked Nov 4, 2015 in Numerical Ability makhdoom ghaya 285 views
7 votes
2 answers
30
Let there be a pack of $100$ cards numbered $1$ to $100$. The $i^{th}$ card states: "There are at most $i - 1$ true cards in this pack". Then how many cards of the pack contain TRUE statements? $0$ $1$ $100$ $50$ None of the above.
asked Nov 4, 2015 in Numerical Ability makhdoom ghaya 359 views
...