Highest voted questions in Others / GATE Overflow for GATE CSE

0 votes

0 answers

1321

CMI-2021-DataScience-A: 18
Let $A_{11}, A_{12}, A_{21}, A_{22}, B_{11}, B_{12}, B_{21}, B_{22}$ be $n \times n$ matrices. Consider the $2n \times 2n$ matrices $A = \left[\begin{array}{cc}A_{11} & A_{12} \\ A_{21} & A_{22}\end{array}\right]$ ...

Let $A_{11}, A_{12}, A_{21}, A_{22}, B_{11}, B_{12}, B_{21}, B_{22}$ be $n \times n$ matrices. Consider the $2n \times 2n$ matrices $A = \left[\begin{array}{cc}A_{11} & A...

admin

143 views

admin asked Jul 23, 2022

0 votes

0 answers

1322

CMI-2021-DataScience-A: 19
Consider right angled triangles with integer side lengths $a, b, c$ where $c$ is the hypotenuse. Call a right angled triangle special if $a$ and $b$ are odd integers. How many special right angled triangles exist? $23$ infinitely many $0$ $12$

Consider right angled triangles with integer side lengths $a, b, c$ where $c$ is the hypotenuse. Call a right angled triangle special if $a$ and $b$ are odd integers. How...

admin

268 views

admin asked Jul 23, 2022

0 votes

0 answers

1323

CMI-2021-DataScience-A: 20
Given a sequence of numbers $\left[x_{1}, x_{2}, \dots, x_{n}\right]$, we say that $x_{i}$ is left-visible if each number in $\left[x_{1}, x_{2}, \dots, x_{i-1}\right]$ is strictly smaller than $x_{i}$. Similarly $x_{i}$ is right-visible if each ... the left. What are the possible numbers at the third and fifth positions? $\{38,53\}$ $\{38,49\}$ $\{17,49\}$ $\{17,38\}$

Given a sequence of numbers $\left[x_{1}, x_{2}, \dots, x_{n}\right]$, we say that $x_{i}$ is left-visible if each number in $\left[x_{1}, x_{2}, \dots, x_{i-1}\right]$ i...

admin

148 views

admin asked Jul 23, 2022

0 votes

0 answers

1324

CMI2022-B: 2
Consider the language $\text{L}$ over the alphabet $\left \{ a, b \right \}$ given below. $\text{L}= \{ w \mid w \;\text{has equal number of $a$'s and $b$'s, and there are no adjacent $a$'s.}\}$ For instance, the words $abba, abab$ are in language ... $baab$. Prove that $\text{L}$ does not contain any word that starts and ends with $a$ $b$. Give a context-free grammar for $\text{L}$.

Consider the language $\text{L}$ over the alphabet $\left \{ a, b \right \}$ given below.$$\text{L}= \{ w \mid w \;\text{has equal number of $a$’s and $b$’s, and the...

admin

223 views

admin asked Jul 22, 2022

0 votes

0 answers

1325

CMI2022-B: 3
We say that an integer $a$ is co-prime to another integer $b$ if $\gcd(a, b) = 1$. For any integer $n, \varphi (n)$ is the number of integers from $1$ up to $|n|$ that are co-prime to $n$. Calculate $\varphi (5), \varphi (10)$ and $\varphi (20)$. Show that ... for any prime $p$. Prove that if $a$ is co-prime to $b$ then the remainder of $a$ when divided by $b$ is also co-prime to $b$.

We say that an integer $a$ is co-prime to another integer $b$ if $\gcd(a, b) = 1$. For any integer $n, \varphi (n)$ is the number of integers from $1$ up to $|n|$ that a...

admin

170 views

admin asked Jul 22, 2022

0 votes

0 answers

1326

CMI2022-B: 4
You are organizing a party involving $2n$ diplomats. Each pair of diplomats are either friends or enemies. You have managed to invite an excellent set of guests, each of whom has more friends than enemies (among the other guests). Can you now seat ... as their neighbours. (Hint: Model this situation as an appropriate graph so that the desired seating arrangement is a Hamiltonian path.)

You are organizing a party involving $2n$ diplomats. Each pair of diplomats are either friends or enemies. You have managed to invite an excellent set of guests, each of ...

admin

191 views

admin asked Jul 22, 2022

0 votes

0 answers

1327

CMI2022-B: 5
For any set $\text{S}$ of natural numbers, we say that a relation $\text{R} \subseteq \text{S} \times \text{S}$ is a $2$-spanner of $\text{S}$ if it satisfies the following conditions: $\left ( i, j \right ) \in R \Rightarrow i < j$ ... any set $\text{S}$ of size $2^{k} - 1$ (for $k > 2)$ has a $2$-spanner of size $(k - 2) 2^{k} + 2$.

For any set $\text{S}$ of natural numbers, we say that a relation $\text{R} \subseteq \text{S} \times \text{S}$ is a $2$-spanner of $\text{S}$ if it satisfies the followi...

admin

279 views

admin asked Jul 22, 2022

0 votes

0 answers

1328

CMI2022-B: 6
There is a treasure hunt game in which parts of a treasure are hidden across $n$ islands, numbered $1$ to $n$. You start in island $1 ,$ and aim to collect all parts of the treasure, by hopping from island to island. Each island has a list of other islands you ... can succeed in collecting all parts of the treasure. The algorithm should run in time $O\left(n^{2} \cdot 2^{n}\right)$.

There is a treasure hunt game in which parts of a treasure are hidden across $n$ islands, numbered $1$ to $n$. You start in island $1 ,$ and aim to collect all parts of t...

admin

272 views

admin asked Jul 22, 2022

0 votes

0 answers

1329

CMI2022-B: 7
Consider the following inventory problem. You are running a company that sells lorries. Predictions tell you the quantity of sales to expect over the next $n$ months. Let $d_{i}$ denote the number of sales expected in month $i$. We assume that sales happen on ... dynamic programming algorithm that computes $c_{1}(0)$. Your algorithm must run in time polynomial in $n$ and $\text{C}$.

Consider the following inventory problem. You are running a company that sells lorries. Predictions tell you the quantity of sales to expect over the next $n$ months. Let...

admin

225 views

admin asked Jul 22, 2022

0 votes

0 answers

1330

CMI2022-A: 4
Consider the following languages over the alphabet $\left \{ a, b, c, d \right \}$ $\text{L}_{1} = \left\{ a^{n} b^{n} c^{m} d^{m} \mid n, m\geq 0\right\}$ $\text{L}_{2} = \left \{ a^{n} b^{m} c^{n} d^{m} \mid n, m\geq 0\right\}$ ... languages is/are context-free? None of them. Only $\text{L}_{1}$ and $\text{L}_{2}$. Only $\text{L}_{1}$ and $\text{L}_{3}$. All of them.

Consider the following languages over the alphabet $\left \{ a, b, c, d \right \}$$\text{L}_{1} = \left\{ a^{n} b^{n} c^{m} d^{m} \mid n, m\geq 0\right\}$$\text{L}_{2} ...

admin

202 views

admin asked Jul 22, 2022

0 votes

0 answers

1331

CMI2022-A: 7
Consider a random graph $\text{G}$ on $n$ vertices where for each pair of vertices $u, v,$ there is an edge $(u, v)$ with probability $p \in [0, 1]$. What is the expected number of cycles of length $3$ in this graph? $\binom{n}{3} \cdot p^{3}$ $\frac{p^{3}}{\binom{n}{3}}$ $n^{3}p^{3}$ None of the above.

Consider a random graph $\text{G}$ on $n$ vertices where for each pair of vertices $u, v,$ there is an edge $(u, v)$ with probability $p \in [0, 1]$. What is the expected...

admin

258 views

admin asked Jul 22, 2022

0 votes

0 answers

1332

CMI2022-A: 8
Refer to the following two functions. int f(int m) { int g(int m) { int a, b, c, d; int a = 1; a = 0; b = 0; int i = 0; c = 0; d = 1; while (i < m) { while (a < m) { i = i + 1; a = a + 1; a = 2 * a; b = b + c; } int temp = d; return a; d = c; } c = temp; } return b; } What is the result of $\textsf{f (100)}?$ $100$ $5050$ $50$ $1$

Refer to the following two functions.int f(int m) { int g(int m) { int a, b, c, d; int a = 1; a = 0; b = 0; int i = 0; c = 0; d = 1; while (i < m) { while (a ...

admin

226 views

admin asked Jul 22, 2022

0 votes

0 answers

1333

CMI2022-A: 9
Refer to the following two functions. int f(int m) { int g(int m) { int a, b, c, d; int a = 1; a = 0; b = 0; int i = 0; c = 0; d = 1; while (i < m) { while (a < m) { i = i + 1; a = a + 1; a = 2 * a; b = b + c; } int temp = d; return a; d = c; } c = temp; } return b; } If $\textsf{g(f(n)) = 32}$ which of the following is a possible value of $\textsf{n}?$ $8$ $11$ $5$ $64$

Refer to the following two functions.int f(int m) { int g(int m) { int a, b, c, d; int a = 1; a = 0; b = 0; int i = 0; c = 0; d = 1; while (i < m) { while (a ...

admin

225 views

admin asked Jul 22, 2022

0 votes

0 answers

1334

CMI2022-A: 10
What can you conclude from the following statements about problems $\text{A}$ and $\text{B}?$ There is a polynomial-time algorithm to solve $\text {A}$. There is an exponential-time algorithm to solve $\text{B}$. $\text{B}$ can be reduced to $\text{A}$ in ... for $\text{B}$. A cannot be reduced to $\text{B}$ in polynomial-time. There is no exponential-time algorithm for $\text{A}$.

What can you conclude from the following statements about problems $\text{A}$ and $\text{B}?$There is a polynomial-time algorithm to solve $\text {A}$.There is an exponen...

admin

192 views

admin asked Jul 22, 2022

0 votes

0 answers

1335

CMI2021-B: 1
Let $\text{A}=\left ( \sqrt{3} +\sqrt{2}\right )^{1000}, \text{B}=\left ( \sqrt{3} -\sqrt{2}\right )^{1000}$. Prove the following statements. $\text{A+B}$ is an integer. The digit immediately after the decimal point in $\text{B}$ is $0$. The digit immediately after the decimal point in $\text{A}$ is $9$. Both $\text{A, B}$ is irrational.

Let $\text{A}=\left ( \sqrt{3} +\sqrt{2}\right )^{1000}, \text{B}=\left ( \sqrt{3} -\sqrt{2}\right )^{1000}$. Prove the following statements.$\text{A+B}$ is an integer.Th...

admin

271 views

admin asked Jul 22, 2022

0 votes

0 answers

1336

CMI2021-B: 2
Imagine you are playing a computer game that consists of different types of coins. You have the power to cast two magic spells $s_{1}$ and $s_{2}$. Each spell consumes some number of coins of each type and produces some number of coins of each type. Spell $s_{1}$ ... coins. There is no sequence of spells using only $s_{1}$ and $s_{3}$ that can produce more than $4 n$ total coins.

Imagine you are playing a computer game that consists of different types of coins. You have the power to cast two magic spells $s_{1}$ and $s_{2}$. Each spell consumes so...

admin

177 views

admin asked Jul 22, 2022

0 votes

0 answers

1337

CMI2021-B: 3
A cut edge of a connected graph $\text{G}$ is any edge $e=\left \{ u, v \right \}$ of $\text{G}$ such that the graph $\text{G} -e$ obtained by deleting edge $e$ (and not deleting $u$ or $v$ ... have an odd number of vertices. To disprove this statement it suffices to exhibit a graph which contradicts the statement. A proof must take the form of an argument.

A cut edge of a connected graph $\text{G}$ is any edge $e=\left \{ u, v \right \}$ of $\text{G}$ such that the graph $\text{G} -e$ obtained by deleting edge $e$ (and not ...

admin

232 views

admin asked Jul 22, 2022

0 votes

0 answers

1338

CMI2021-B: 4
For a language $\text{L}$ over an alphabet $\Sigma$, define $\text{SW(L)}:= \left \{ y \in \Sigma^{\ast} \mid \exists x \in \Sigma^{\ast}\; \text{s.t.}\; xyx \in \text{L} \right \}$ Prove that if $\text{L}$ is regular, $\text{SW(L)}$ is also regular.

For a language $\text{L}$ over an alphabet $\Sigma$, define$$\text{SW(L)}:= \left \{ y \in \Sigma^{\ast} \mid \exists x \in \Sigma^{\ast}\; \text{s.t.}\; xyx \in \text{L}...

admin

179 views

admin asked Jul 22, 2022

0 votes

0 answers

1339

CMI2021-B: 5
Given a list $\text{A}$ of $\text{N}$ elements and a number $\text{K}$, your task is to output the $\text{N – K + 1}$ values listing the minimum among $\text{A} [i]\cdots \text{A}[i+\text{K}-1]$ for every $1\leq i\leq \text{N – K + 1}$. Provide an algorithm for this task, that runs in time atmost $\mathcal{O}(\text{N} \log \text{K}).$

Given a list $\text{A}$ of $\text{N}$ elements and a number $\text{K}$, your task is to output the $\text{N – K + 1}$ values listing the minimum among $\text{A} [i]\...

admin

185 views

admin asked Jul 22, 2022

0 votes

0 answers

1340

CMI2021-B: 6
Let $\text{A = A [1] A[2]} \cdots \text{A [n]}$ be an array of $n$ numbers where $n = 2^{k} - 1$ for some $k > 0$. Consider a binary tree $\text{T}$ built from the array in the following manner. The root of $\text{T}$ ... $\text {A}[i_{1}] \text {A}[i_{2}]\cdots\text {A}[i_{m}]$ consisting only of good indices is sorted.

Let $\text{A = A A } \cdots \text{A [n]}$ be an array of $n$ numbers where $n = 2^{k} – 1$ for some $k 0$. Consider a binary tree $\text{T}$ built from the array in ...

admin

144 views

admin asked Jul 22, 2022

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