search
Log In

Recent questions tagged tifr2018

23 votes
6 answers
1
How many ways are there to assign colours from range $\left\{1,2,\ldots,r\right\}$ to vertices of the following graph so that adjacent vertices receive distinct colours? $r^{4}$ $r^{4} - 4r^{3}$ $r^{4}-5r^{3}+8r^{2}-4r$ $r^{4}-4r^{3}+9r^{2}-3r$ $r^{4}-5r^{3}+10r^{2}-15r$
asked Dec 10, 2017 in Graph Theory Rohit Gupta 8 1.8k views
6 votes
2 answers
2
Let $A$ be an $n\times n$ invertible matrix with real entries whose row sums are all equal to $c$. Consider the following statements: Every row in the matrix $2A$ sums to $2c$. Every row in the matrix $A^{2}$ sums to $c^{2}$. Every row in the matrix $A^{-1}$ sums ... statement $(1)$ and $(2)$ are correct but not necessarily statement $(3)$ all the three statements $(1), (2),$ and $(3)$ are correct
asked Dec 10, 2017 in Linear Algebra Rohit Gupta 8 887 views
13 votes
2 answers
3
A hacker knows that the password to the TIFR server is 10-letter string consisting of lower-case letters from the English alphabet. He guesses a set of $5$ distinct 10-letter strings (with lower-case letters) uniformly at random. What is the probability that one of the guesses of the hacker is correct ... $ \frac{1}{(26)^{10}}$ None of the above
asked Dec 10, 2017 in Probability Rohit Gupta 8 890 views
12 votes
1 answer
4
Suppose a box contains 20 balls: each ball has a distinct number in $\left\{1,\ldots,20\right\}$ written on it. We pick 10 balls (without replacement) uniformly at random and throw them out of the box. Then we check if the ball with number $``1"$ on it is present in the box. If it is ... that the ball with number $``2"$ on it is present in the box? $9/20$ $9/19$ $1/2$ $10/19$ None of the above
asked Dec 10, 2017 in Probability Rohit Gupta 8 970 views
3 votes
1 answer
5
$G$ respresents an undirected graph and a cycle refers to a simple cycle (no repeated edges or vertices). Define the following two languages. $SCYCLE=\{(G,k)\mid G \text{ contains a cycle of length at most k}\}$ ... $SCYCLE \leq_{p} LCYCLE$ (i.e, there is a polynomial time many-to-one reduction from $SCYCLE$ to $LCYCLE$).
asked Dec 10, 2017 in Algorithms Arjun 365 views
8 votes
3 answers
6
Define the language $\text{INFINITE}_{DFA}\equiv \{(A)\mid A \text{ is a DFA and } L(A) \text{ is an infinite language}\},$ where $(A)$ ... not regular. It is Turing decidable (recursive). It is Turing recognizable but not decidable. Its complement is Turing recognizable but it is not decidable.
asked Dec 10, 2017 in Theory of Computation Arjun 961 views
8 votes
3 answers
7
Let $n\geq 3,$ and let $G$ be a simple, connected, undirected graph with the same number $n$ of vertices and edges. Each edge of $G$ has a distinct real weight associated with it. Let $T$ be the minimum weight spanning tree of $G.$ Which of the following statements is NOT ... maximum weight edge of $C$ is not in $T.$ $T$ can be found in $O(n)$ time from the adjacency list representation of $G.$
asked Dec 10, 2017 in Algorithms Arjun 879 views
6 votes
1 answer
8
Consider the following statements: For every positive integer $n,$ let $\#{n}$ be the product of all primes less than or equal to $n.$ Then, $\# {p}+1$ is a prime, for every prime $p.$ $\large\pi$ ... (i) is correct. Only statement (ii) is correct. Only statement (iii) is correct. Only statement (iv) is correct. None of the statements are correct.
asked Dec 10, 2017 in Theory of Computation Arjun 691 views
9 votes
2 answers
9
Consider the language $L\subseteq \left \{ a,b,c \right \}^{*}$ defined as $L = \left \{ a^{p}b^{q}c^{r} : p=q\quad or\quad q=r \quad or\quad r=p \right \}.$ Which of the following answer is TRUE about the complexity of this language? $L$ is regular but not ... of $L,$ defined as $\overline{L} = \left \{ a,b,c \right \}^{*}\backslash L,$ is regular. $L$ is regular, context-free and decidable
asked Dec 10, 2017 in Theory of Computation Arjun 819 views
12 votes
1 answer
10
Which of the following functions, given by there recurrence, grows the fastest asymptotically? $T(n) = 4T\left ( \frac{n}{2} \right ) + 10n$ $T(n) = 8T\left ( \frac{n}{3} \right ) + 24n^{2}$ $T(n) = 16T\left ( \frac{n}{4} \right ) + 10n^{2}$ $T(n) = 25T\left ( \frac{n}{5} \right ) + 20\left ( n \log n \right )^{1.99}$ They all are asymptotically the same
asked Dec 10, 2017 in Algorithms Arjun 1.1k views
7 votes
1 answer
11
For two $n$ bit strings $x,y \in\{0,1\}^{n},$ define $z=x\oplus y$ to be the bitwise XOR of the two strings (that is, if $x_{i},y_{i},z_{i}$ denote the $i^{th}$ bits of $x,y,z$ respectively, then $z_{i}=x_{i}+y_{i} \bmod 2$). A function $h:\{0,1\}^{n} \to \{0,1\}^{n}$ ... $n \geq 2$ is: $2^{n}$ $2^{n^{2}}$ $\large2^{\frac{n}{2}}$ $2^{4n}$ $2^{n^{2}+n}$
asked Dec 10, 2017 in Set Theory & Algebra Arjun 495 views
9 votes
1 answer
12
Let $G=(V,E)$ be a DIRECTED graph, where each edge $\large e$ has a positive weight $\large\omega(e),$ and all vertices can be reached from vertex $\large s.$ For each vertex $\large v,$ let $\large \phi(v)$ be the length of the shortest path from $\large s$ ... $P$ is NOT a shortest path in $G,$ then $\omega'(P)<2\times \omega(P).$ All of the above options are necessarily TRUE.
asked Dec 10, 2017 in Algorithms Arjun 794 views
20 votes
2 answers
13
In an undirected graph $G$ with $n$ vertices, vertex $1$ has degree $1$, while each vertex $2,\ldots,n-1$ has degree $10$ and the degree of vertex $n$ is unknown, Which of the following statement must be TRUE on the graph $G$? There is a path from vertex $1$ ... $n$ has degree $1$. The diameter of the graph is at most $\frac{n}{10}$ All of the above choices must be TRUE
asked Dec 10, 2017 in Graph Theory Arjun 1.6k views
10 votes
1 answer
14
Consider the recursive quicksort algorithm with "random pivoting". That is, in each recursive call, a pivot is chosen uniformly at random from the sub-array being sorted.When this randomized algorithm is applied to an array of size $n$ all whose elements are distinct, what is the probability that the smallest ... ${O} \left(\dfrac{1}{n^{2}}\right)$ $\Theta\left(\dfrac{1}{n \log^{2} n}\right)$
asked Dec 10, 2017 in Algorithms Arjun 1.1k views
3 votes
2 answers
15
Consider the following implementation of a binary tree data strucrure. The operator $+$ denotes list-concatenation. That is, $[a,b,c]+[d,e]=[a,b,c,d,e].$ struct TreeNode: int value TreeNode leftChild TreeNode rightChild function preOrder(T): if T == null: return [] else: return [T.value ... $[12,6,7,9,10,15,2,1,4,8,11,14,3,13,5]$ $\text{Cannot be uniquely determined from given information.}$
asked Dec 10, 2017 in DS Arjun 452 views
3 votes
3 answers
16
The notation "$\Rightarrow$" denotes "implies" and "$\wedge$" denotes "and" in the following formulae. Let $X$ denote the formula: $(b \Rightarrow a ) \Rightarrow ( a \Rightarrow b)$ Let $Y$ denote the formula: $(a \Rightarrow b) \wedge b$ Which of the following is ... not tautology and $Y$ is not satisfiable. $X$ is not tautology and $Y$ is satisfiable. $X$ is a tautology and $Y$ is satisfiable,
asked Dec 10, 2017 in Mathematical Logic Arjun 627 views
6 votes
2 answers
17
How many distinct minimum weight spanning trees does the following undirected, weighted graph have ? $1$ $2$ $4$ $6$ $8$
asked Dec 10, 2017 in Graph Theory Arjun 769 views
6 votes
1 answer
18
Consider the following non-deterministic automation, where $\large s_{1}$ is the start state and $\large s_{4}$ is the final (accepting) state. The alphabet is $\{a,b\}.$ A transition with label $\large\epsilon$ can be taken without consuming any symbol from the input. Which of the following regular expressions ... $aba(a+b)^{*}aba$ $(a+b)aba(b+a)^{*}$ $aba(a+b)^{*}$ $(ab)^{*}aba$
asked Dec 10, 2017 in Theory of Computation Arjun 476 views
8 votes
11 answers
19
What is the remainder when $4444^{4444}$ is divided by $9?$ $1$ $2$ $5$ $7$ $8$
asked Dec 10, 2017 in Combinatory Arjun 1.3k views
4 votes
1 answer
20
An $n \times n$ matrix $M$ with real entries is said to be positive definite if for every non-zero $n$-dimensional vector $x$ with real entries, we have $x^{T}Mx>0.$ Let $A$ and $B$ be symmetric, positive definite matrices of size $n\times n$ with real entries. ... $(2)$ Only $(3)$ Only $(1)$ and $(3)$ None of the above matrices are positive definite All of the above matrices are positive definite
asked Dec 10, 2017 in Linear Algebra Arjun 542 views
1 vote
3 answers
21
We are given a (possibly empty) set of objects. Each object in the set is colored either black or white, is shaped either circular or rectangular, and has a profile that is either fat or thin, Those properties obey the following principles: Each white object is also circular. Not all ... $(i) \text{ and } (iii)$ only None of the statements must be TRUE All of the statements must be TRUE
asked Dec 10, 2017 in Numerical Ability Arjun 469 views
4 votes
2 answers
22
Let $C$ be a biased coin such that the probability of a head turning up is $p.$ Let $p_n$ denote the probability that an odd number of heads occurs after $n$ tosses for $n \in \{0,1,2,\ldots \},$ ... $p_{n}=1 \text{ if } n \text{ is odd and } 0 \text{ otherwise}.$
asked Dec 10, 2017 in Probability Arjun 589 views
7 votes
2 answers
23
A crime has been committed with four people at the scene of the crime. You are responsible for finding out who did it. You have recorded the following statements from the four witnesses, and you know one of them has committed the crime. Anuj says that Binky did it. ... $\text{Chacko}$ $\text{Desmond}$ $\text{Either Anuj or Binky; the information is insufficient to pinpoint the criminal}$
asked Dec 10, 2017 in Numerical Ability Arjun 558 views
10 votes
3 answers
24
Consider the following function definition. void greet(int n) { if(n>0) { printf("hello"); greet(n-1); } printf("world"); } If you run greet(n) for some non-negative integer n, what would it print? n times "hello", followed by n+1 times "world" n times "hello", followed by n times "world" n times "helloworld" n+1 times "helloworld" n times "helloworld", followed by "world"
asked Dec 10, 2017 in Programming Arjun 987 views
11 votes
5 answers
25
What is the minimum number of students needed in a class to guarantee that there are at least $6$ students whose birthdays fall in the same month ? $6$ $23$ $61$ $72$ $91$
asked Dec 10, 2017 in Combinatory Arjun 816 views
4 votes
1 answer
26
Which of the following id the derivative of $f(x)=x^{x}$ when $x>0$ ? $x^{x}$ $x^{x} \ln \;x$ $x^{x}+x^{x}\ln\;x$ $(x^{x}) (x^{x}\ln\;x)$ $\text{None of the above;function is not differentiable for }x>0$
asked Dec 10, 2017 in Calculus Arjun 453 views
1 vote
1 answer
27
Consider a point $A$ inside a circle $C$ that is at distance $9$ from the centre of a circle. Suppose you told that there is a chord of length $24$ passing through $A$ with $A$ as its midpoint. How many distinct chords of $C$ have integer length and pass through $A?$ $2$ $6$ $7$ $12$ $14$
asked Dec 10, 2017 in Numerical Ability Arjun 704 views
1 vote
2 answers
28
The distance from your home to your office is $4$ kilometers and your normal walking speed is $4$ Km/hr. On the first day, you walk at your normal walking speed and take time $T_1$ to reach office. On the second day, you walk at a speed of $3$ Km/hr from $2$ Kilometers, and at a speed of $5$ Km/hr for the ... $T_{1}>T_{3}$ $T_{1}=T_{2}$ and $T_{1}<T_{3}$ $T_{1}<T_{2}$ and $T_{1}=T_{3}$
asked Dec 10, 2017 in Others Arjun 247 views
15 votes
2 answers
29
Which of the following statements is TRUE for all sufficiently large integers n ? $2^{2^{\sqrt{\log \log n}}} <2^{\sqrt{\log n}} < n$ $2^{\sqrt{\log n}}<n<2^{2^{\sqrt{\log \log n}}}$ $n<2^{\sqrt{\log n}}<2^{2^{\sqrt{\log \log n}}}$ $n<2^{2^{\sqrt{\log \log n}}} <2^{\sqrt{\log n}}$ $2^{\sqrt{\log n}}<2^{2^{\sqrt{\log \log n}}} < n$
asked Dec 10, 2017 in Algorithms Arjun 942 views
1 vote
1 answer
30
Consider the following subset of $\mathbb{R} ^{3}$ (the first two are cylinder, the third is a plane): $C_{1}=\left \{ \left ( x,y,z \right ): y^{2}+z^{2}\leq 1 \right \};$ ... Let $A = C_{1}\cap C_{2}\cap H.$ Which of the following best describe the shape of set $A?$ Circle Ellipse Triangle Square An octagonal convex figure with curved sides
asked Dec 10, 2017 in Numerical Ability Arjun 291 views
To see more, click for the full list of questions or popular tags.
...