Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Recent questions tagged tifr2013
34
votes
4
answers
1
TIFR CSE 2013 | Part B | Question: 20
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 ... $n^2$ steps $n$ steps $n^{1.5}$ steps The algorithm is not guaranteed to sort
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...
makhdoom ghaya
3.1k
views
makhdoom ghaya
asked
Nov 8, 2015
Algorithms
tifr2013
algorithms
sorting
+
–
27
votes
3
answers
2
TIFR CSE 2013 | Part B | Question: 19
In a relational database there are three relations: $Customers = C\textsf{(CName)}$, $Shops = S \textsf{(SName)}$, $Buys = B\textsf{(CName, SName)}$ ... $S - \Pi _{\textsf{SName}}((C \times S) - B)$ None of the above
In a relational database there are three relations:$Customers = C\textsf{(CName)}$,$Shops = S \textsf{(SName)}$,$Buys = B\textsf{(CName, SName)}$.Which of the following r...
makhdoom ghaya
3.2k
views
makhdoom ghaya
asked
Nov 8, 2015
Databases
tifr2013
databases
relational-algebra
+
–
18
votes
6
answers
3
TIFR CSE 2013 | Part B | Question: 18
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 $\textsf{Select}(S, r)$ takes a set $S$ of numbers and a rank $r\left(1 \leq r \leq |S|\right)$ and returns the ... $|S|$ constant · $|S||R|$ constant · $|R| \log |S|$ constant · $|S|(1 + \log |R|)$
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 $\textsf{Select}(S, r)$ tak...
makhdoom ghaya
2.4k
views
makhdoom ghaya
asked
Nov 8, 2015
Algorithms
tifr2013
algorithms
quick-sort
time-complexity
+
–
15
votes
2
answers
4
TIFR CSE 2013 | Part B | Question: 17
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}$
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 gr...
makhdoom ghaya
1.8k
views
makhdoom ghaya
asked
Nov 8, 2015
Algorithms
tifr2013
algorithms
minimum-spanning-tree
+
–
13
votes
4
answers
5
TIFR CSE 2013 | Part B | Question: 16
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}$ ... $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
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)...
makhdoom ghaya
1.4k
views
makhdoom ghaya
asked
Nov 8, 2015
Set Theory & Algebra
tifr2013
set-theory&algebra
functions
+
–
8
votes
2
answers
6
TIFR CSE 2013 | Part B | Question: 15
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 ... $O \left(\sqrt{n}\right)$ but not $O (\log n)$ $O (n)$ but not $O \left(\sqrt{n}\right)$
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'$ t...
makhdoom ghaya
1.4k
views
makhdoom ghaya
asked
Nov 7, 2015
Algorithms
tifr2013
graph-algorithms
time-complexity
+
–
24
votes
3
answers
7
TIFR CSE 2013 | Part B | Question: 14
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 ... $1,1,1,2$ times, respectively $1,1,1,1$ times, respectively $2,1,2,2$ times, respectively None of the above
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 ...
makhdoom ghaya
2.6k
views
makhdoom ghaya
asked
Nov 7, 2015
Operating System
tifr2013
operating-system
page-replacement
+
–
39
votes
2
answers
8
TIFR CSE 2013 | Part B | Question: 13
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.
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)$...
makhdoom ghaya
3.4k
views
makhdoom ghaya
asked
Nov 7, 2015
DS
tifr2013
binary-tree
data-structures
+
–
25
votes
2
answers
9
TIFR CSE 2013 | Part B | Question: 12
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 ... $O (n)$ but not $O (\sqrt{n})$ $O \left(n \log n\right)$ but not $O (n)$
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 ...
makhdoom ghaya
3.2k
views
makhdoom ghaya
asked
Nov 7, 2015
Algorithms
tifr2013
algorithms
sorting
time-complexity
+
–
17
votes
4
answers
10
TIFR CSE 2013 | Part B | Question: 11
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 ... language is context free. The intersection of a regular language and the complement of a regular language is regular.
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 i...
makhdoom ghaya
2.4k
views
makhdoom ghaya
asked
Nov 7, 2015
Theory of Computation
tifr2013
theory-of-computation
easy
closure-property
+
–
5
votes
1
answer
11
TIFR CSE 2013 | Part B | Question: 10
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$ ... $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$.
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...
makhdoom ghaya
803
views
makhdoom ghaya
asked
Nov 7, 2015
Probability
tifr2013
probability
conditional-probability
+
–
9
votes
2
answers
12
TIFR CSE 2013 | Part B | Question: 9
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 produced, but they need not all be convex. All regions are convex but there may be exponentially many of them.
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 s...
makhdoom ghaya
1.4k
views
makhdoom ghaya
asked
Nov 6, 2015
Quantitative Aptitude
tifr2013
quantitative-aptitude
geometry
cartesian-coordinates
+
–
19
votes
3
answers
13
TIFR CSE 2013 | Part B | Question: 8
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$ that read the same from left to right as well as right to ... $(c)$ above. $\left \{ 0^{m} 1^{n} | 1 \leq m \leq n\right \}$
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 lang...
makhdoom ghaya
4.0k
views
makhdoom ghaya
asked
Nov 6, 2015
Theory of Computation
tifr2013
theory-of-computation
regular-language
+
–
4
votes
1
answer
14
TIFR CSE 2013 | Part B | Question: 7
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.
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 polyno...
makhdoom ghaya
1.7k
views
makhdoom ghaya
asked
Nov 6, 2015
Algorithms
tifr2013
algorithms
p-np-npc-nph
+
–
27
votes
2
answers
15
TIFR CSE 2013 | Part B | Question: 6
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\}$ ... then $L$ is regular. $L/L'$ is a subset of $L$. If $L/L'$ and $L'$ are regular, then $L$ is regular.
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 \...
makhdoom ghaya
2.9k
views
makhdoom ghaya
asked
Nov 6, 2015
Theory of Computation
tifr2013
theory-of-computation
regular-language
+
–
29
votes
3
answers
16
TIFR CSE 2013 | Part B | Question: 5
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})$
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 ...
makhdoom ghaya
4.4k
views
makhdoom ghaya
asked
Nov 6, 2015
Algorithms
tifr2013
algorithms
graph-algorithms
time-complexity
+
–
17
votes
5
answers
17
TIFR CSE 2013 | Part B | Question: 4
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$. ... $2^{24}$ words. $W$ is not a partial order. $W$ is a partial order but not a well order. $W$ is a well order.
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 elemen...
makhdoom ghaya
3.1k
views
makhdoom ghaya
asked
Nov 6, 2015
Set Theory & Algebra
tifr2013
set-theory&algebra
partial-order
+
–
24
votes
3
answers
18
TIFR CSE 2013 | Part B | Question: 3
How many $4 \times 4$ matrices with entries from ${0, 1}$ have odd determinant? Hint: Use modulo $2$ arithmetic. $20160$ $32767$ $49152$ $57343$ $65520$
How many $4 \times 4$ matrices with entries from ${0, 1}$ have odd determinant?Hint: Use modulo $2$ arithmetic.$20160$$32767$$49152$$57343$$65520$
makhdoom ghaya
4.5k
views
makhdoom ghaya
asked
Nov 6, 2015
Linear Algebra
tifr2013
linear-algebra
matrix
+
–
3
votes
1
answer
19
TIFR CSE 2013 | Part B | Question: 2
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 ... $d$ At most $n - d$ Between $d$ and $n - d$ At least $n - d$ None of the above.
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 \...
makhdoom ghaya
632
views
makhdoom ghaya
asked
Nov 6, 2015
Quantitative Aptitude
tifr2013
polynomials
non-gate
+
–
26
votes
4
answers
20
TIFR CSE 2013 | Part B | Question: 1
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 ... $a\left(G\right)\leq \frac{n}{\chi \left(G\right)}$ None of the above
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 di...
makhdoom ghaya
4.2k
views
makhdoom ghaya
asked
Nov 5, 2015
Graph Theory
tifr2013
graph-theory
graph-coloring
+
–
9
votes
5
answers
21
TIFR CSE 2013 | Part A | Question: 20
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 ... of $1/60$ th of the circumference. $144$ minutes $66$ minutes $96$ minutes $72$ minutes $132$ minutes
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 ah...
makhdoom ghaya
1.7k
views
makhdoom ghaya
asked
Nov 5, 2015
Quantitative Aptitude
tifr2013
quantitative-aptitude
clock-time
+
–
6
votes
3
answers
22
TIFR CSE 2013 | Part A | Question: 19
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 ... $\large (\epsilon _{n}: n= 1, 2,...)$ is decreasing and then increasing. Finally it converges to $1.$ None of the above.
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}}$fo...
makhdoom ghaya
1.3k
views
makhdoom ghaya
asked
Nov 5, 2015
Quantitative Aptitude
tifr2013
quantitative-aptitude
sequence-series
+
–
6
votes
1
answer
23
TIFR CSE 2013 | Part A | Question: 18
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)$ ... $(1 - b) a (b - a)$ $6 ((b^{2}- a^{2})/ 2 - (b^{3} - a^{3})/3)$.
Consider three independent uniformly distributed (taking values between $0$ and $1$) random variables. What is the probability that the middle of the three values (betwee...
makhdoom ghaya
1.3k
views
makhdoom ghaya
asked
Nov 5, 2015
Probability
tifr2013
probability
random-variable
uniform-distribution
+
–
9
votes
5
answers
24
TIFR CSE 2013 | Part A | Question: 17
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$
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 th...
makhdoom ghaya
1.8k
views
makhdoom ghaya
asked
Nov 5, 2015
Probability
tifr2013
probability
+
–
8
votes
2
answers
25
TIFR CSE 2013 | Part A | Question: 16
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
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
makhdoom ghaya
1.4k
views
makhdoom ghaya
asked
Nov 5, 2015
Calculus
tifr2013
calculus
maxima-minima
+
–
4
votes
3
answers
26
TIFR CSE 2013 | Part A | Question: 15
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$
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...
makhdoom ghaya
898
views
makhdoom ghaya
asked
Nov 4, 2015
Quantitative Aptitude
tifr2013
quantitative-aptitude
number-series
+
–
18
votes
5
answers
27
TIFR CSE 2013 | Part A | Question: 14
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
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 abov...
makhdoom ghaya
1.6k
views
makhdoom ghaya
asked
Nov 4, 2015
Probability
tifr2013
probability
binomial-distribution
+
–
12
votes
3
answers
28
TIFR CSE 2013 | Part A | Question: 13
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 ... 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.
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$...
makhdoom ghaya
1.3k
views
makhdoom ghaya
asked
Nov 4, 2015
Probability
tifr2013
probability
+
–
9
votes
1
answer
29
TIFR CSE 2013 | Part A | Question: 12
Among numbers $1$ to $1000$ how many are divisible by $3$ or $7$? $333$ $142$ $475$ $428$ None of the above
Among numbers $1$ to $1000$ how many are divisible by $3$ or $7$?$333$$142$$475$$428$None of the above
makhdoom ghaya
919
views
makhdoom ghaya
asked
Nov 4, 2015
Quantitative Aptitude
tifr2013
quantitative-aptitude
factors
normal
+
–
10
votes
2
answers
30
TIFR CSE 2013 | Part A | Question: 11
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
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 c...
makhdoom ghaya
1.0k
views
makhdoom ghaya
asked
Nov 4, 2015
Analytical Aptitude
tifr2013
logical-reasoning
+
–
Page:
1
2
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register