Answers by Nikhil_dhama / GATE Overflow for GATE CSE

3 votes

1

Made Easy Probability - Let X be a set containing n elements. Three subsets A,B, C of X are chosen at random. The probability that A, B, C are pairwise disjoint is? (What do they mean by pairwise disjoint? and how should I approach this question?)

1.1k views

answered Dec 28, 2023

5 votes

2

GATE CSE 2022 | Question: 41
Consider the following recurrence: $\begin{array}{} f(1) & = & 1; \\ f(2n) & = & 2f(n) - 1, & \; \text{for}\; n \geq 1; \\ f(2n+1) & = & 2f(n) + 1, & \; \text{for}\; n \geq 1. \end{array}$ Then, which of the following statements is/are $\text{TRUE}?$ ... $f(2^{n}) = 1$ $f(5 \cdot 2^{n}) = 2^{n+1} + 1$ $f(2^{n} + 1) = 2^{n} + 1$

Consider the following recurrence:$$\begin{array}{} f(1) & = & 1; \\ f(2n) & = & 2f(n) – 1, & \; \text{for}\; n \geq 1; \\ f(2n+1) & = & 2f(n) + 1, & \; \text...

7.8k views

answered Feb 16, 2022

3 votes

3

Applied Test Series
Given a system with 3 processes where each process requires at least 2 resources to complete their execution, then the largest number of resources which will guarantee a deadlock is ___

Given a system with 3 processes where each process requires at least 2 resources to complete their execution, then the largest number of resources which will guarantee a ...

438 views

answered Nov 12, 2021

0 votes

4

CMI-2018-DataScience-A: 15
A farmer owns $50$ papaya trees. Each tree produces $600$ papayas in a year. For each additional tree planted in the orchard, the output of each tree (including the pre-existing ones) drops by $5$ papayas. How many trees should be added to the existing orchard in order to maximize the total production of papayas?

A farmer owns $50$ papaya trees. Each tree produces $600$ papayas in a year. For each additional tree planted in the orchard, the output of each tree (including the pre-e...

527 views

answered May 10, 2021

1 votes

5

TIFR CSE 2021 | Part B | Question: 8
Let $A$ and $B$ be two matrices of size $n \times n$ and with real-valued entries. Consider the following statements. If $AB = B$, then $A$ must be the identity matrix. If $A$ is an idempotent (i.e. $A^{2} = A$) nonsingular matrix, then $A$ must be the identity matrix. ... true of $A$? $1, 2 $ and $3$ Only $2$ and $3$ Only $1$ and $2$ Only $1$ and $3$ Only $2$

Let $A$ and $B$ be two matrices of size $n \times n$ and with real-valued entries. Consider the following statements.If $AB = B$, then $A$ must be the identity matrix.If ...

703 views

answered May 10, 2021

1 votes

6

TIFR CSE 2021 | Part B | Question: 4
Consider the following two languages. ... $\text{NP}$ vs. $\text{P}$ question.

Consider the following two languages.$\begin{array}{rcl} \text{PRIME} & = & \{ 1^{n} \mid n \text{ is a prime number} \}, \\ \text{FACTOR} & = & \{ 1^{n}0 1^{a} 01^{b} ...

495 views

answered May 10, 2021

14 votes

7

GATE CSE 2021 Set 1 | GA Question: 4
A circular sheet of paper is folded along the lines in the directions shown. The paper, after being punched in the final folded state as shown and unfolded in the reverse order of folding, will look like _______.

A circular sheet of paper is folded along the lines in the directions shown. The paper, after being punched in the final folded state as shown and unfolded in the reverse...

2.6k views

answered Apr 5, 2021

0 votes

8

TIFR CSE 2021 | Part B | Question: 14
Consider the following greedy algorithm for colouring an $n$-vertex undirected graph $G$ with colours $c_{1}, c_{2}, \dots:$ consider the vertices of $G$ ... $m\left ( n, r \right ) = nr$ $m\left ( n, r \right ) = n\binom{r}{2}$

Consider the following greedy algorithm for colouring an $n$-vertex undirected graph $G$ with colours $c_{1}, c_{2}, \dots:$ consider the vertices of $G$ in any sequence ...

742 views

answered Apr 4, 2021

0 votes

9

TIFR CSE 2021 | Part B | Question: 13
Let $A$ be a $3 \times 6$ matrix with real-valued entries. Matrix $A$ has rank $3$. We construct a graph with $6$ vertices where each vertex represents distinct column in $A$, and there is an edge between two vertices if the two columns represented ... is connected. There is a clique of size $3$. The graph has a cycle of length $4$. The graph is $3$-colourable.

Let $A$ be a $3 \times 6$ matrix with real-valued entries. Matrix $A$ has rank $3$. We construct a graph with $6$ vertices where each vertex represents distinct column in...

609 views

answered Apr 4, 2021

1 votes

10

TIFR CSE 2021 | Part B | Question: 12
Let $G$ be an undirected graph. For any two vertices $u, v$ in $G$, let $\textrm{cut} (u, v)$ be the minimum number of edges that should be deleted from $G$ so that there is no path between $u$ and $v$ in the resulting graph. Let $a, b, c, d$ be $4$ ... $\textrm{cut} (b,d) = 2$, $\textrm{cut} (b,c) = 2$ and $\textrm{cut} (c,d) = 1$

Let $G$ be an undirected graph. For any two vertices $u, v$ in $G$, let $\textrm{cut} (u, v)$ be the minimum number of edges that should be deleted from $G$ so that there...

586 views

answered Apr 4, 2021

1 votes

11

TIFR CSE 2021 | Part B | Question: 10
Let $G$ be a connected bipartite simple graph (i.e., no parallel edges) with distinct edge weights. Which of the following statements on $\text{MST}$ (minimum spanning tree) need $\text{NOT}$ be true? $G$ has a unique $\text{MST}$ ... edge. Every $\text{MST}$ in $G$ contains the third lightest edge. No $\text{MST}$ in $G$ contains the heaviest edge.

Let $G$ be a connected bipartite simple graph (i.e., no parallel edges) with distinct edge weights. Which of the following statements on $\text{MST}$ (minimum spanning tr...

697 views

answered Apr 4, 2021

1 votes

12

TIFR CSE 2021 | Part B | Question: 1
Consider the following statements about propositional formulas. $\left ( p\wedge q \right )\rightarrow r$ and $\left ( p \rightarrow r \right )\wedge \left ( q\rightarrow r \right )$ are $\textit{not }$ ... values $p$ and $q$, $\text{(i)}$ can be either true or false, while $\text{(ii)}$ is always false.

Consider the following statements about propositional formulas.$\left ( p\wedge q \right )\rightarrow r$ and $\left ( p \rightarrow r \right )\wedge \left ( q\rightarrow ...

892 views

answered Apr 4, 2021

4 votes

13

TIFR CSE 2021 | Part A | Question: 14
Five married couples attended a party. In the party, each person shook hands with those they did not know. Everyone knows his or her spouse. At the end of the party, Shyamal, one of the attendees, listed the number of hands that other attendees ... in the list. How many persons shook hands with Shyamal at the party? $2$ $4$ $6$ $8$ Insufficient information

Five married couples attended a party. In the party, each person shook hands with those they did not know. Everyone knows his or her spouse. At the end of the party, Shya...

711 views

answered Apr 4, 2021

2 votes

14

TIFR CSE 2021 | Part A | Question: 9
Fix $n\geq 6$. Consider the set $\mathcal{C}$ of binary strings $x_{1}, x_{2} \dots x_{n}$ of length $n$ such that the bits satisfy the following set of equalities, all modulo $2$: $x_{i}+x_{i+1}+x_{i+2}=0$ ... $3$ $\left | \mathcal{C} \right |=4$. If $n\geq 6$ is not divisible by $3$ then $\left | \mathcal{C} \right |=1$.

Fix $n\geq 6$. Consider the set $\mathcal{C}$ of binary strings $x_{1}, x_{2} \dots x_{n}$ of length $n$ such that the bits satisfy the following set of equalities, all m...

498 views

answered Apr 4, 2021

2 votes

15

TIFR CSE 2021 | Part A | Question: 6
A matching in a graph is a set of edges such that no two edges in the set share a common vertex. Let $G$ be a graph on $n$ $\textit{vertices}$ in which there is a subset $M$ of $m$ $\textit{edges}$ which is a matching. Consider a random process where each vertex in the ... $\left ( 1-p^{2} \right )^{m}$ $1-\left ( 1-p\left ( 1-p \right ) \right )^{m}$

A matching in a graph is a set of edges such that no two edges in the set share a common vertex. Let $G$ be a graph on $n$ $\textit{vertices}$ in which there is a subset ...

771 views

answered Apr 4, 2021

26 votes

16

GATE CSE 2021 Set 2 | Question: 39
For constants $a \geq 1$ and $b>1$, consider the following recurrence defined on the non-negative integers: $T(n) = a \cdot T \left(\dfrac{n}{b} \right) + f(n)$ Which one of the following options is correct about the recurrence $T(n)$? If $f(n)$ is $n \log_2(n)$, ... $f(n)$ is $\Theta(n^{\log_b(a)})$, then $T(n)$ is $\Theta(n^{\log_b(a)})$

For constants $a \geq 1$ and $b>1$, consider the following recurrence defined on the non-negative integers:$$T(n) = a \cdot T \left(\dfrac{n}{b} \right) + f(n)$$ Which on...

8.2k views

answered Apr 3, 2021

2 votes

17

GATE CSE 2021 Set 2 | Question: 38
For a statement $S$ in a program, in the context of liveness analysis, the following sets are defined: $\text{USE}(S)$ : the set of variables used in $S$ $\text{IN}(S)$ : the set of variables that are live at the entry of $S$ $\text{OUT}(S)$ : the set of variables ... S_2$) }\cup \text{ OUT ($S_2$)}$ $\text{OUT ($S_1$)} = \text{USE ($S_1$)} \cup \text{IN ($S_2$)}$

For a statement $S$ in a program, in the context of liveness analysis, the following sets are defined:$\text{USE}(S)$ : the set of variables used in $S$$\text{IN}(S)$ : t...

6.8k views

answered Apr 3, 2021

4 votes

18

GATE CSE 2021 Set 2 | Question: 29
In an examination, a student can choose the order in which two questions ($\textsf{QuesA}$ and $\textsf{QuesB}$) must be attempted. If the first question is answered wrong, the student gets zero marks. If the first question is answered correctly and the ... $22$. First $\textsf{QuesA}$ and then $\textsf{QuesB}$. Expected marks $16$.

In an examination, a student can choose the order in which two questions ($\textsf{QuesA}$ and $\textsf{QuesB}$) must be attempted.If the first question is answered wrong...

7.6k views

answered Apr 3, 2021

26 votes

19

GATE CSE 2021 Set 2 | Question: 25
Suppose that $f: \mathbb{R} \rightarrow \mathbb{R}$ is a continuous function on the interval $[-3, 3]$ and a differentiable function in the interval $(-3,3)$ such that for every $x$ in the interval, $f’(x) \leq 2$. If $f(-3)=7$, then $f(3)$ is at most __________

Suppose that $f: \mathbb{R} \rightarrow \mathbb{R}$ is a continuous function on the interval $[-3, 3]$ and a differentiable function in the interval $(-3,3)$ such that fo...

6.3k views

answered Apr 3, 2021

36 votes

20

GATE CSE 2021 Set 2 | Question: 24
Suppose that $P$ is a $4 \times 5$ matrix such that every solution of the equation $\text{Px=0}$ is a scalar multiple of $\begin{bmatrix} 2 & 5 & 4 &3 & 1 \end{bmatrix}^T$. The rank of $P$ is __________

Suppose that $P$ is a $4 \times 5$ matrix such that every solution of the equation $\text{Px=0}$ is a scalar multiple of $\begin{bmatrix} 2 & 5 & 4 &3 & 1 \end{bmatrix}^T...

18.7k views

answered Apr 3, 2021

7 votes

21

GATE CSE 2021 Set 2 | Question: 19
Consider a set-associative cache of size $\text{2KB (1KB} =2^{10}$ bytes$\text{)}$ with cache block size of $64$ bytes. Assume that the cache is byte-addressable and a $32$ -bit address is used for accessing the cache. If the width of the tag field is $22$ bits, the associativity of the cache is _________

Consider a set-associative cache of size $\text{2KB (1KB} =2^{10}$ bytes$\text{)}$ with cache block size of $64$ bytes. Assume that the cache is byte-addressable and a $3...

7.3k views

answered Apr 3, 2021

16 votes

22

GATE CSE 2021 Set 2 | Question: 8
What is the worst-case number of arithmetic operations performed by recursive binary search on a sorted array of size $n$? $\Theta ( \sqrt{n})$ $\Theta (\log _2(n))$ $\Theta(n^2)$ $\Theta(n)$

What is the worst-case number of arithmetic operations performed by recursive binary search on a sorted array of size $n$?$\Theta ( \sqrt{n})$$\Theta (\log _2(n))$$\Theta...

12.0k views

answered Apr 3, 2021

18 votes

23

GATE CSE 2021 Set 2 | Question: 7
Consider the three-way handshake mechanism followed during $\text{TCP}$ connection establishment between hosts $P$ and $Q$. Let $X$ and $Y$ be two random $32$-bit starting sequence numbers chosen by $P$ and $Q$ respectively. Suppose $P$ sends a $\text{TCP}$ connection request ... $=Y$, $\text{ACK}$ bit $=1$, $\text{ACK}$ number $=X$, $\text{FIN}$ bit $=0$

Consider the three-way handshake mechanism followed during $\text{TCP}$ connection establishment between hosts $P$ and $Q$. Let $X$ and $Y$ be two random $32$-bit startin...

7.0k views

answered Apr 3, 2021

16 votes

24

GATE CSE 2021 Set 2 | Question: 5
Which one of the following circuits implements the Boolean function given below? $f(x,y,z) = m_0+m_1+m_3+m_4+m_5+m_6$, where $m_i$ is the $i^{\text{th}}$ minterm.

Which one of the following circuits implements the Boolean function given below?$f(x,y,z) = m_0+m_1+m_3+m_4+m_5+m_6$, where $m_i$ is the $i^{\text{th}}$ minterm.

9.2k views

answered Apr 3, 2021

13 votes

25

GATE CSE 2021 Set 2 | GA Question: 9
The number of units of a product sold in three different years and the respective net profits are presented in the figure above. The cost/unit in Year $3$ was ₹$\;1$, which was half the cost/unit in Year $2$. The cost/unit in Year $3$ was one-third of the ... the selling price in Year $2$ to the selling price in Year $3$ is _________. $4:3$ $1:1$ $3:4$ $1:2$

The number of units of a product sold in three different years and the respective net profits are presented in the figure above. The cost/unit in Year $3$ was ₹$\;1$, w...

6.3k views

answered Apr 3, 2021

50 votes

26

GATE CSE 2021 Set 1 | Question: 30
Consider the following recurrence relation. $T\left ( n \right )=\left\{\begin{array} {lcl} T(n ∕ 2)+T(2n∕5)+7n & \text{if} \; n>0\\1 & \text{if}\; n=0 \end{array}\right.$ Which one of the following options is correct? $T(n)=\Theta (n^{5/2})$ $T(n)=\Theta (n\log n)$ $T(n)=\Theta (n)$ $T(n)=\Theta ((\log n)^{5/2})$

Consider the following recurrence relation.$$T\left ( n \right )=\left\{\begin{array} {lcl} T(n ∕ 2)+T(2n∕5)+7n & \text{if} \; n>0\\1 & \text{if}\; n=0 \end{array}\r...

23.9k views

answered Apr 1, 2021

23 votes

27

GATE CSE 2021 Set 1 | Question: 25
Three processes arrive at time zero with $\text{CPU}$ bursts of $16,\;20$ and $10$ milliseconds. If the scheduler has prior knowledge about the length of the $\text{CPU}$ bursts, the minimum achievable average waiting time for these three processes in a non-preemptive scheduler (rounded to nearest integer) is _____________ milliseconds.

Three processes arrive at time zero with $\text{CPU}$ bursts of $16,\;20$ and $10$ milliseconds. If the scheduler has prior knowledge about the length of the $\text{CPU}$...

9.2k views

answered Apr 1, 2021

1 votes

28

GATE CSE 2021 Set 1 | Question: 12
Let $\langle M \rangle$ denote an encoding of an automaton $M$. Suppose that $\Sigma = \{0,1\}$. Which of the following languages is/are $\text{NOT}$ recursive? $L= \{ \langle M \rangle \mid M$ is a $\text{DFA}$ such that $L(M)=\emptyset \}$ ... that $L(M)=\emptyset \}$ $L= \{ \langle M \rangle \mid M$ is a $\text{PDA}$ such that $L(M)=\Sigma ^* \}$

Let $\langle M \rangle$ denote an encoding of an automaton $M$. Suppose that $\Sigma = \{0,1\}$. Which of the following languages is/are $\text{NOT}$ recursive?$L= \{ \la...

7.3k views

answered Apr 1, 2021

19 votes

29

GATE CSE 2021 Set 1 | Question: 43
A relation $R$ is said to be circular if $a\text{R}b$ and $b\text{R}c$ together imply $c\text{R}a$. Which of the following options is/are correct? If a relation $S$ is reflexive and symmetric, then $S$ is an equivalence relation ... and circular, then $S$ is an equivalence relation. If a relation $S$ is transitive and circular, then $S$ is an equivalence relation.

A relation $R$ is said to be circular if $a\text{R}b$ and $b\text{R}c$ together imply $c\text{R}a$.Which of the following options is/are correct?If a relation $S$ is refl...

8.3k views

answered Feb 20, 2021

25 votes

30

GATE CSE 2021 Set 1 | Question: 29
Assume that a $12$-bit Hamming codeword consisting of $8$-bit data and $4$ check bits is $d_8d_7d_6d_5c_8d_4d_4d_3d_2c_4d_1c_2c_1$ ... $0$ and $y$ is $1$ $x$ is $1$ and $y$ is $0$ $x$ is $1$ and $y$ is $1$

Assume that a $12$-bit Hamming codeword consisting of $8$-bit data and $4$ check bits is $d_8d_7d_6d_5c_8d_4d_4d_3d_2c_4d_1c_2c_1$, where the data bits and the check bits...

15.5k views

answered Feb 19, 2021

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