Questions by Arjun / GATE Overflow for GATE CSE

10 votes

2 answers

1231

TIFR CSE 2019 | Part B | Question: 5
Stirling's approximation for $n!$ states for some constants $c_1,c_2$ $c_1 n^{n+\frac{1}{2}}e^{-n} \leq n! \leq c_2 n^{n+\frac{1}{2}}e^{-n}.$ What are the tightest asymptotic bounds that can be placed on $n!$ $?$ ... $n! =\Theta((\frac{n}{e})^{n+\frac{1}{2}})$ $n! =\Theta(n^{n+\frac{1}{2}}2^{-n})$

Stirling’s approximation for $n!$ states for some constants $c_1,c_2$$$c_1 n^{n+\frac{1}{2}}e^{-n} \leq n! \leq c_2 n^{n+\frac{1}{2}}e^{-n}.$$What are the tightest asym...

3.4k views

asked Dec 18, 2018

12 votes

3 answers

1232

TIFR CSE 2019 | Part B | Question: 6
Given the following pseudocode for function $\text{printx()}$ below, how many times is $x$ printed if we execute $\text{printx(5)}?$ void printx(int n) { if(n==0){ printf(“x”); } for(int i=0;i<=n-1;++i){ printx(n-1); } } $625$ $256$ $120$ $24$ $5$

Given the following pseudocode for function $\text{printx()}$ below, how many times is $x$ printed if we execute $\text{printx(5)}?$void printx(int n) { if(n==0){ printf...

2.5k views

asked Dec 18, 2018

3 votes

1 answer

1233

TIFR CSE 2019 | Part B | Question: 7
A formula is said to be a $3$-CF-formula if it is a conjunction (i.e., an AND) of clauses, and each clause has at most $3$ literals. Analogously, a formula is said to be a $3$ ... $\text{3-DF-SAT}$ is NP-complete Neither $\text{3-CF-SAT}$ nor $\text{3-DF-SAT}$ are in P

A formula is said to be a $3$-CF-formula if it is a conjunction (i.e., an AND) of clauses, and each clause has at most $3$ literals. Analogously, a formula is said to be ...

1.0k views

asked Dec 18, 2018

5 votes

2 answers

1234

TIFR CSE 2019 | Part B | Question: 8
Consider the following program fragment: var a,b : integer; procedure G(c,d: integer); begin c:=c-d; d:=c+d; c:=d-c end; a:=2; b:=3; G(a,b); If both parameters to $G$ are passed by reference, what are the values of $a$ and $b$ at the end of the above program fragment ? $a=0$ and $b=2$ $a=3$ and $b=2$ $a=2$ and $b=3$ $a=1$ and $b=5$ None of the above

Consider the following program fragment:var a,b : integer; procedure G(c,d: integer); begin c:=c-d; d:=c+d; c:=d-c end; a:=2; b:=3; G(a,b);If both parameters to $G$ are p...

2.0k views

asked Dec 18, 2018

12 votes

2 answers

1235

TIFR CSE 2019 | Part B | Question: 9
Consider the following program fragment: var x, y: integer; x := 1; y := 0; while y < x do begin x := 2*x; y := y+1 end; For the above fragment , which of the following is a loop invariant ? $x=y+1$ $x=(y+1)^2$ $x=(y+1)2^y$ $x=2^y$ None of the above, since the loop does not terminate

Consider the following program fragment:var x, y: integer; x := 1; y := 0; while y < x do begin x := 2*x; y := y+1 end;For the above fragment , which of the following is ...

3.5k views

asked Dec 18, 2018

9 votes

2 answers

1236

TIFR CSE 2019 | Part B | Question: 10
Let the language $D$ be defined in the binary alphabet $\{0,1\}$ as follows: $D:= \{ w \in \{0,1\}^* \mid \text{ substrings 01 and 10 occur an equal number of times in w} \}$ For example , $101 \in D$ while $1010 \notin D$ ... $D$ is context-free but not regular $D$ is decidable but not context-free $D$ is decidable but not in NP $D$ is undecidable

Let the language $D$ be defined in the binary alphabet $\{0,1\}$ as follows:$D:= \{ w \in \{0,1\}^* \mid \text{ substrings 01 and 10 occur an equal number of times in w}...

2.0k views

asked Dec 18, 2018

11 votes

3 answers

1237

TIFR CSE 2019 | Part B | Question: 11
Consider the following non-deterministic automaton,where $s_1$ is the start state and $s_4$ is the final (accepting) state. The alphabet is $\{a,b\}$. A transition with label $\epsilon$ can be taken without consuming any symbol from the input. Which of the following regular expressions correspond ... $(a+b)^*ba^*$ $(a+b)^*ba(aa)^*$ $(a+b)^*$ $(a+b)^*baa^*$

Consider the following non-deterministic automaton,where $s_1$ is the start state and $s_4$ is the final (accepting) state. The alphabet is $\{a,b\}$. A transition with l...

2.1k views

asked Dec 18, 2018

6 votes

1 answer

1238

TIFR CSE 2019 | Part B | Question: 12
Let $G=(V,E)$ be a directed graph with $n(\geq 2)$ vertices, including a special vertex $r$. Each edge $e \in E$ has a strictly positive edge weight $w(e)$. An arborescence in $G$ rooted at $r$ is a subgraph $H$ of $G$ ... is acyclic $w^*$ is less than the weight of the minimum weight directed Hamiltonian cycle in $G$, when $G$ has a directed Hamiltonian cycle

Let $G=(V,E)$ be a directed graph with $n(\geq 2)$ vertices, including a special vertex $r$. Each edge $e \in E$ has a strictly positive edge weight $w(e)$. An arborescen...

2.4k views

asked Dec 18, 2018

20 votes

7 answers

1239

TIFR CSE 2019 | Part B | Question: 13
A row of $10$ houses has to be painted using the colours red, blue, and green so that each house is a single colour, and any house that is immediately to the right of a red or a blue house must be green. How many ways are there to paint the houses? $199$ $683$ $1365$ $3^{10}-2^{10}$ $3^{10}$

A row of $10$ houses has to be painted using the colours red, blue, and green so that each house is a single colour, and any house that is immediately to the right of a r...

5.0k views

asked Dec 18, 2018

3 votes

2 answers

1240

TIFR CSE 2019 | Part B | Question: 14
Let $m$ and $n$ be two positive integers. Which of the following is NOT always true? If $m$ and $n$ are co-prime, there exist integers $a$ and $b$ such that $am + bn=1$ $m^{n-1} \equiv 1 (\text{ mod } n)$ ... $m+1$ is a factor of $m^{n(n+1)}-1$ If $2^n -1$ is prime, then $n$ is prime

Let $m$ and $n$ be two positive integers. Which of the following is NOT always true?If $m$ and $n$ are co-prime, there exist integers $a$ and $b$ such that $am + bn=1$$m^...

1.3k views

asked Dec 18, 2018

7 votes

2 answers

1241

TIFR CSE 2019 | Part B | Question: 15
Consider directed graphs on $n$ labelled vertices $\{1,2, \dots ,n\}$, where each vertex has exactly one edge coming in and exactly one edge going out. We allow self-loops. How many graphs have exactly two cycles ? $\displaystyle \sum_{k=1}^{n-1} k!(n-k)!$ ... $n!\bigg[\displaystyle \sum_{k=1}^{n-1} \frac{1}{k}\bigg]$ $\frac{n!(n-1)}{2}$ None of the above

Consider directed graphs on $n$ labelled vertices $\{1,2, \dots ,n\}$, where each vertex has exactly one edge coming in and exactly one edge going out. We allow self-loo...

2.2k views

asked Dec 18, 2018

3 votes

1 answer

1242

NIELIT 2018-1
A Professor passed one sixth of his life in childhood, one twelfth in youth, and one seventh more as a bachelor, five years after his marriage a son was born who died four years before his father at half his final age, then what is the age of Professor? $84$ years $74$ years $64$ years $54$ years

A Professor passed one sixth of his life in childhood, one twelfth in youth, and one seventh more as a bachelor, five years after his marriage a son was born who died fou...

5.5k views

asked Dec 7, 2018

4 votes

3 answers

1243

NIELIT 2018-2
Divide $88$ into four parts such as first part known as $a,$ second part $b,$ third part $c,$ and fourth part is $d,$ when $5$ is added to the first part, $5$ is subtracted from the second part, $3$ is multiplied by the third part and the fourth part is divided by $5,$ then all results ... $d$ respectively. $7, 17, 4, 60$ $8, 25, 5, 50$ $10, 30, 3, 45$ $17, 7, 4, 60$

Divide $88$ into four parts such as first part known as $a,$ second part $b,$ third part $c,$ and fourth part is $d,$ when $5$ is added to the first part, $5$ is subtract...

3.1k views

asked Dec 7, 2018

3 votes

2 answers

1244

NIELIT 2018-3
A software engineer has the capability of thinking $200$ lines of code in five minutes and can type $200$ lines of code in $10$ minutes. He takes a break for five minutes after every $10$ minutes. How many lines of code will he complete typing after an hour? $200$ $300$ $400$ $500$

A software engineer has the capability of thinking $200$ lines of code in five minutes and can type $200$ lines of code in $10$ minutes. He takes a break for five minutes...

4.6k views

asked Dec 7, 2018

2 votes

1 answer

1245

NIELIT 2018-4
Candid is to indirect as honest is to frank wicked truthful untruthful

Candid is to indirect as honest is tofrankwickedtruthfuluntruthful

1.5k views

asked Dec 7, 2018

2 votes

2 answers

1246

NIELIT 2018-5
Suppose a fraud shopkeeper sells rice to the customer at the cost price, but he uses a false weight of $900$ gm for a kg then his percentage gain is ______ $5.75 \%$ $5.56 \%$ $5.20 \%$ $5.00 \%$

Suppose a fraud shopkeeper sells rice to the customer at the cost price, but he uses a false weight of $900$ gm for a kg then his percentage gain is ______$5.75 \%$$5.56 ...

6.6k views

asked Dec 7, 2018

7 votes

5 answers

1247

NIELIT 2018-6
A construction company ready to finish a construction work in $180$ days, hired $80$ workers each working $8$ hours daily. After $90$ days, only $2/7$ of the work was completed. How many workers are to be increased to complete the work on time? Note: If additionally acquired workers do agree to work for $10$ hours daily. $90$ workers $80$ workers $65$ workers $85$ workers

A construction company ready to finish a construction work in $180$ days, hired $80$ workers each working $8$ hours daily. After $90$ days, only $2/7$ of the work was com...

4.8k views

asked Dec 7, 2018

2 votes

1 answer

1248

NIELIT 2018-7
Here are some words translated from any Language. dionot means oak tree blyonot means oak leaf blycrin means maple leaf Which word could mean “maple syrup”? blymuth hupponot patricin crinweel

Here are some words translated from any Language.dionot means oak treeblyonot means oak leafblycrin means maple leafWhich word could mean “maple syrup”?blymuthhuppono...

1.6k views

asked Dec 7, 2018

1 votes

2 answers

1249

NIELIT 2018-8
Let us consider the length of the side of a square represented by $2y+3$. The length of the side of an equilateral triangle is $4y$. If the square and the equilateral triangle have equal perimeter, then what is the value of $y$? $3$ $4$ $6$ $8$

Let us consider the length of the side of a square represented by $2y+3$. The length of the side of an equilateral triangle is $4y$. If the square and the equilateral tri...

2.3k views

asked Dec 7, 2018

2 votes

1 answer

1250

NIELIT 2018-9
Look at this series: $25, 25, 37, 37, \dots , 51, ….$. What number should fill the blank? $51$ $39$ $23$ $25$

Look at this series: $25, 25, 37, 37, \dots , 51, ….$. What number should fill the blank?$51$$39$$23$$25$

3.3k views

asked Dec 7, 2018

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