Dark Mode

Recent questions tagged tifr2013

33 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

makhdoom ghaya asked in Algorithms Nov 8, 2015

by makhdoom ghaya

2.5k views

26 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

makhdoom ghaya asked in Databases Nov 8, 2015

by makhdoom ghaya

2.6k views

17 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|)$

makhdoom ghaya asked in Algorithms Nov 8, 2015

by makhdoom ghaya

2.0k views

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}$

makhdoom ghaya asked in Algorithms Nov 8, 2015

by makhdoom ghaya

1.5k views

12 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

makhdoom ghaya asked in Set Theory & Algebra Nov 8, 2015

by makhdoom ghaya

1.1k views

7 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 property ... $O \left(\sqrt{n}\right)$ but not $O (\log n)$ $O (n)$ but not $O \left(\sqrt{n}\right)$

makhdoom ghaya asked in Algorithms Nov 7, 2015

by makhdoom ghaya

1.1k views

23 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

makhdoom ghaya asked in Operating System Nov 7, 2015

by makhdoom ghaya

2.2k views

38 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.

makhdoom ghaya asked in DS Nov 7, 2015

by makhdoom ghaya

2.9k views

24 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)$

makhdoom ghaya asked in Algorithms Nov 7, 2015

by makhdoom ghaya

2.6k views

16 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.

makhdoom ghaya asked in Theory of Computation Nov 7, 2015

by makhdoom ghaya

2.2k views

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$.

makhdoom ghaya asked in Probability Nov 7, 2015

by makhdoom ghaya

622 views

8 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.

makhdoom ghaya asked in Quantitative Aptitude Nov 6, 2015

by makhdoom ghaya

1.1k views

17 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 \}$

makhdoom ghaya asked in Theory of Computation Nov 6, 2015

by makhdoom ghaya

3.1k views

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.

makhdoom ghaya asked in Algorithms Nov 6, 2015

by makhdoom ghaya

1.3k views

25 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\}$ Which of the following is true? If $L/L'$ ... $L$ is regular. $L/L'$ is a subset of $L$. If $L/L'$ and $L'$ are regular, then $L$ is regular.

makhdoom ghaya asked in Theory of Computation Nov 6, 2015

by makhdoom ghaya

2.7k views

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})$

makhdoom ghaya asked in Algorithms Nov 6, 2015

by makhdoom ghaya

3.7k views

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.

makhdoom ghaya asked in Set Theory & Algebra Nov 6, 2015

by makhdoom ghaya

2.2k views

23 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$

makhdoom ghaya asked in Linear Algebra Nov 6, 2015

by makhdoom ghaya

3.7k views

2 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.

makhdoom ghaya asked in Quantitative Aptitude Nov 6, 2015

by makhdoom ghaya

502 views

24 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

makhdoom ghaya asked in Graph Theory Nov 5, 2015

by makhdoom ghaya

3.6k views

8 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

makhdoom ghaya asked in Quantitative Aptitude Nov 5, 2015

by makhdoom ghaya

1.3k views

5 votes

2 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.

makhdoom ghaya asked in Quantitative Aptitude Nov 5, 2015

by makhdoom ghaya

946 views

5 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)$.

makhdoom ghaya asked in Probability Nov 5, 2015

by makhdoom ghaya

1.1k views

8 votes

4 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$

makhdoom ghaya asked in Probability Nov 5, 2015

by makhdoom ghaya

1.5k views

7 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

makhdoom ghaya asked in Calculus Nov 5, 2015

by makhdoom ghaya

1.2k views

3 votes

2 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$

makhdoom ghaya asked in Quantitative Aptitude Nov 4, 2015

by makhdoom ghaya

683 views

17 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

makhdoom ghaya asked in Probability Nov 4, 2015

by makhdoom ghaya

1.3k views

11 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.

makhdoom ghaya asked in Probability Nov 4, 2015

by makhdoom ghaya

1.1k views

8 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

makhdoom ghaya asked in Quantitative Aptitude Nov 4, 2015

by makhdoom ghaya

741 views

9 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

makhdoom ghaya asked in Analytical Aptitude Nov 4, 2015

by makhdoom ghaya

877 views

Page:

Recent questions tagged tifr2013