Search results for tifr2018 / GATE Overflow for GATE CSE

32 votes

3 answers

1

TIFR CSE 2018 | Part B | Question: 8
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 ... Vertex $n$ has degree $1$. The diameter of the graph is at most $\frac{n}{10}$ All of the above choices must be TRUE

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

Arjun

5.5k views

Arjun asked Dec 10, 2017

30 votes

6 answers

2

TIFR CSE 2018 | Part A | Question: 9
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$

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

Rohit Gupta 8

4.6k views

Rohit Gupta 8 asked Dec 10, 2017

8 votes

5 answers

3

TIFR CSE 2018 | Part A | Question: 14
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 ... and $(2)$ are correct but not necessarily statement $(3)$ all the three statements $(1), (2),$ and $(3)$ are correct

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

Rohit Gupta 8

3.5k views

Rohit Gupta 8 asked Dec 10, 2017

16 votes

5 answers

4

TIFR CSE 2018 | Part A | Question: 7
Consider the following function definition. void greet(int n) { if(n>0) { printf("hello"); greet(n-1); } printf("world"); } If you run $\textsf{greet(n)}$ ... "helloworld" $\textsf{n+1}$ times "helloworld" $\textsf{n}$ times "helloworld", followed by "world"

Consider the following function definition. void greet(int n) { if(n>0) { printf("hello"); greet(n-1); } printf("world"); }If you run $\textsf{greet(n)}$ for some non-neg...

Arjun

2.9k views

Arjun asked Dec 10, 2017

17 votes

12 answers

5

TIFR CSE 2018 | Part B | Question: 1
What is the remainder when $4444^{4444}$ is divided by $9?$ $1$ $2$ $5$ $7$ $8$

What is the remainder when $4444^{4444}$ is divided by $9?$$1$$2$$5$$7$$8$

Arjun

3.3k views

Arjun asked Dec 10, 2017

17 votes

3 answers

6

TIFR CSE 2018 | Part A | Question: 15
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 $\text{ 1"}$ ... $\text{ 2"}$ on it is present in the box? $9/20$ $9/19$ $1/2$ $10/19$ None of the above

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

Rohit Gupta 8

2.7k views

Rohit Gupta 8 asked Dec 10, 2017

22 votes

3 answers

7

TIFR CSE 2018 | Part A | Question: 3
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$

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

Arjun

3.0k views

Arjun asked Dec 10, 2017

16 votes

6 answers

8

TIFR CSE 2018 | Part A | Question: 6
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$

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$

Arjun

3.4k views

Arjun asked Dec 10, 2017

11 votes

3 answers

9

TIFR CSE 2018 | Part B | Question: 13
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 ... edge of $C$ is not in $T.$ $T$ can be found in $O(n)$ time from the adjacency list representation of $G.$

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

Arjun

2.8k views

Arjun asked Dec 10, 2017

13 votes

1 answer

10

TIFR CSE 2018 | Part B | Question: 7
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, ... $\Theta\left(\dfrac{1}{n \log^{2} n}\right)$

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

Arjun

8.3k views

Arjun asked Dec 10, 2017

13 votes

3 answers

11

TIFR CSE 2018 | Part B | Question: 14
Define the language $\text{INFINITE}_{DFA}\equiv \{(A)\mid A \text{ is a DFA and } L(A) \text{ is an infinite language}\},$ where $(A)$ denotes the description of the deterministic finite automata (DFA).Then which ... It is Turing decidable (recursive). It is Turing recognizable but not decidable. Its complement is Turing recognizable but it is not decidable.

Define the language $\text{INFINITE}_{DFA}\equiv \{(A)\mid A \text{ is a DFA and } L(A) \text{ is an infinite language}\},$ where $(A)$ denotes the description of the det...

Arjun

3.6k views

Arjun asked Dec 10, 2017

7 votes

2 answers

12

TIFR CSE 2018 | Part A | Question: 10
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}.$

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

Arjun

2.1k views

Arjun asked Dec 10, 2017

11 votes

1 answer

13

TIFR CSE 2018 | Part B | Question: 10
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$ ... such linear functions for $n \geq 2$ is: $2^{n}$ $2^{n^{2}}$ $\large2^{\frac{n}{2}}$ $2^{4n}$ $2^{n^{2}+n}$

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

Arjun

1.6k views

Arjun asked Dec 10, 2017

3 votes

3 answers

14

TIFR CSE 2018 | Part A | Question: 11
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 ... $(i) \text{ and } (iii)$ only None of the statements must be TRUE All of the statements must be TRUE

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

Arjun

1.7k views

Arjun asked Dec 10, 2017

9 votes

2 answers

15

TIFR CSE 2018 | Part B | Question: 3
How many distinct minimum weight spanning trees does the following undirected, weighted graph have ? $1$ $2$ $4$ $6$ $8$

How many distinct minimum weight spanning trees does the following undirected, weighted graph have ?$1$$2$$4$$6$$8$

Arjun

2.6k views

Arjun asked Dec 10, 2017

14 votes

1 answer

16

TIFR CSE 2018 | Part B | Question: 5
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

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} \...

Arjun

3.6k views

Arjun asked Dec 10, 2017

17 votes

2 answers

17

TIFR CSE 2018 | Part A | Question: 13
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 ... $ \frac{1}{(26)^{10}}$ None of the above

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

Rohit Gupta 8

2.0k views

Rohit Gupta 8 asked Dec 10, 2017

12 votes

1 answer

18

TIFR CSE 2018 | Part B | Question: 9
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 ... is NOT a shortest path in $G,$ then $\omega'(P)<2\times \omega(P).$ All of the above options are necessarily TRUE.

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

Arjun

2.4k views

Arjun asked Dec 10, 2017

12 votes

2 answers

19

TIFR CSE 2018 | Part B | Question: 11
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 ... defined as $\overline{L} = \left \{ a,b,c \right \}^{*}\backslash L,$ is regular. $L$ is regular, context-free and decidable

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

Arjun

2.5k views

Arjun asked Dec 10, 2017

4 votes

3 answers

20

TIFR CSE 2018 | Part B | Question: 4
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: ... is not satisfiable. $X$ is not tautology and $Y$ is satisfiable. $X$ is a tautology and $Y$ is satisfiable,

The notation "$\Rightarrow$" denotes "implies" and "$\wedge$" denotes "and" in the following formulae.Let $X$ denote the formula: $(b \Rightarrow a ) \Rightarrow ( a \Ri...

Arjun

1.9k views

Arjun asked Dec 10, 2017

tags	tag:apple
author	user:martin
title	title:apple
content	content:apple
exclude	-tag:apple
force match	+apple
views	views:100
score	score:10
answers	answers:2
is accepted	isaccepted:true
is closed	isclosed:true