Answers by Jhaiyam / GATE Overflow for GATE CSE

0 votes

1

UGC NET CSE | December 2019 | Part 2 | Question: 41
When using Dijkstra's algorithm to find shortest path in a graph, which of the following statement is not true? It can find shortest path within the same graph data structure Every time a new node is visited, we choose the ... Shortest path always passes through least number of vertices The graph needs to have a non-negative weight on every edge

When using Dijkstra’s algorithm to find shortest path in a graph, which of the following statement is not true?It can find shortest path within the same graph data stru...

918 views

answered Aug 13, 2021

2 votes

2

GATE CSE 2004 | Question: 78
Two $n$ bit binary strings, $S_1$ and $S_2$ are chosen randomly with uniform probability. The probability that the Hamming distance between these strings (the number of bit positions where the two strings differ) is equal to $d$ is $\dfrac{^{n}C_{d}}{2^{n}}$ $\dfrac{^{n}C_{d}}{2^{d}}$ $\dfrac{d}{2^{n}}$ $\dfrac{1}{2^{d}}$

Two $n$ bit binary strings, $S_1$ and $S_2$ are chosen randomly with uniform probability. The probability that the Hamming distance between these strings (the number of b...

7.4k views

answered Aug 31, 2020

0 votes

3

GATE CSE 2005 | Question: 52
A random bit string of length n is constructed by tossing a fair coin n times and setting a bit to 0 or 1 depending on outcomes head and tail, respectively. The probability that two such randomly generated strings are not identical is: $\frac{1}{2^n}$ $1 - \frac{1}{n}$ $\frac{1}{n!}$ $1 - \frac{1}{2^n}$

A random bit string of length n is constructed by tossing a fair coin n times and setting a bit to 0 or 1 depending on outcomes head and tail, respectively. The probabili...

8.6k views

answered Aug 31, 2020

0 votes

4

GATE CSE 2001 | Question: 2.1
How many $4$-digit even numbers have all $4$ digits distinct? $2240$ $2296$ $2620$ $4536$

How many $4$-digit even numbers have all $4$ digits distinct?$2240$$2296$$2620$$4536$

12.7k views

answered Aug 26, 2020

0 votes

5

ISRO2009-56
A simple graph ( a graph without parallel edge or loops) with $n$ vertices and $k$ components can have at most $n$ edges $n-k$ edges $(n-k) (n-k+1)$ edges $(n-k) (n-k+1)/2$ edges

A simple graph ( a graph without parallel edge or loops) with $n$ vertices and $k$ components can have at most$n$ edges$n-k$ edges$(n-k) (n-k+1)$ edges$(n-k) (n-k+1)/2$ e...

3.4k views

answered Aug 26, 2020

0 votes

6

GATE CSE 2019 | Question: 30
Consider three $4$-variable functions $f_1, f_2$, and $f_3$, which are expressed in sum-of-minterms as $f_1=\Sigma(0,2,5,8,14),$ $f_2=\Sigma(2,3,6,8,14,15),$ $f_3=\Sigma (2,7,11,14)$ For the following circuit with one AND gate and one XOR gate the output function $f$ can be ... as: $\Sigma(7,8,11)$ $\Sigma (2,7,8,11,14)$ $\Sigma (2,14)$ $\Sigma (0,2,3,5,6,7,8,11,14,15)$

Consider three $4$-variable functions $f_1, f_2$, and $f_3$, which are expressed in sum-of-minterms as$f_1=\Sigma(0,2,5,8,14),$$f_2=\Sigma(2,3,6,8,14,15),$$f_3=\Sigma (2,...

14.4k views

answered Aug 22, 2020

2 votes

7

GATE IT 2006 | Question: 21
Consider the following first order logic formula in which $R$ is a binary relation symbol. $∀x∀y (R(x, y) \implies R(y, x))$ The formula is satisfiable and valid satisfiable and so is its negation unsatisfiable but its negation is valid satisfiable but its negation is unsatisfiable

Consider the following first order logic formula in which $R$ is a binary relation symbol.$∀x∀y (R(x, y) \implies R(y, x))$The formula issatisfiable and validsatisfia...

13.4k views

answered Aug 18, 2020

0 votes

8

relations and functions

391 views

answered Aug 15, 2020

0 votes

9

relations and functions
A binary relation R on Z × Z is defined as follows: (a, b) R (c, d) iff a = c or b = d Consider the following propositions: 1. R is reflexive. 2. R is symmetric. 3. R is antisymmetric. Which one of the above statements is True?

A binary relation R on Z × Z is defined as follows: (a, b) R (c, d) iff a = c or b = dConsider the following propo...

639 views

answered Aug 15, 2020

3 votes

10

GATE CSE 2004 | Question: 26
The number of different $n \times n $ symmetric matrices with each element being either 0 or 1 is: (Note: $\text{power} \left(2, X\right)$ is same as $2^X$) $\text{power} \left(2, n\right)$ $\text{power} \left(2, n^2\right)$ $\text{power} \left(2,\frac{ \left(n^2+ n \right) }{2}\right)$ $\text{power} \left(2, \frac{\left(n^2 - n\right)}{2}\right)$

The number of different $n \times n $ symmetric matrices with each element being either 0 or 1 is: (Note: $\text{power} \left(2, X\right)$ is same as $2^X$)$\text{power} ...

12.6k views

answered Aug 10, 2020

0 votes

11

GATE CSE 2015 Set 3 | Question: 53
Language $L_1$ is polynomial time reducible to language $L_2$. Language $L_3$ is polynomial time reducible to language $L_2$, which in turn polynomial time reducible to language $L_4$. Which of the following is/are true? $\text{ if } L_4 \in P, \text{ then } L_2 \in P$ ... $\text{ if } L_4 \in P, \text{ then } L_3 \in P$ II only III only I and IV only I only

Language $L_1$ is polynomial time reducible to language $L_2$. Language $L_3$ is polynomial time reducible to language $L_2$, which in turn polynomial time reducible to l...

9.1k views

answered Aug 9, 2020

1 votes

12

GATE CSE 2018 | Question: 15
Two people, $P$ and $Q$, decide to independently roll two identical dice, each with $6$ faces, numbered $1$ to $6$. The person with the lower number wins. In case of a tie, they roll the dice repeatedly until there is no tie. Define a ... and that all trials are independent. The probability (rounded to $3$ decimal places) that one of them wins on the third trial is ____

Two people, $P$ and $Q$, decide to independently roll two identical dice, each with $6$ faces, numbered $1$ to $6$. The person with the lower number wins. In case of a ti...

11.0k views

answered Aug 9, 2020

2 votes

13

GATE CSE 2008 | Question: 21
The minimum number of equal length subintervals needed to approximate $\int_1^2 xe^x\,dx$ to an accuracy of at least $\frac{1}{3}\times10^{-6}$ using the trapezoidal rule is 1000e 1000 100e 100

The minimum number of equal length subintervals needed to approximate $\int_1^2 xe^x\,dx$ to an accuracy of at least $\frac{1}{3}\times10^{-6}$ using the trapezoidal rule...

3.1k views

answered Aug 1, 2020

0 votes

14

GATE CSE 1988 | Question: 1i
Loosely speaking, we can say that a numerical method is unstable if errors introduced into the computation grow at _________ rate as the computation proceeds.

Loosely speaking, we can say that a numerical method is unstable if errors introduced into the computation grow at _________ rate as the computation proceeds.

574 views

answered Jul 31, 2020

1 votes

15

GATE IT 2007 | Question: 66
Consider the following two transactions$: T1$ and $T2.$ ...

Consider the following two transactions$: T1$ and $T2.$$\begin{array}{clcl} T1: & \text{read (A);} & T2: & \text{read (B);} \\ & \text{read (B);} & & \text{read (A);} \\ ...

18.0k views

answered Jul 23, 2020

0 votes

16

GATE IT 2005 | Question: 34
Let $n =$ $p^{2}q$, where $p$ and $q$ are distinct prime numbers. How many numbers m satisfy $1 ≤ m ≤ n$ and $gcd$ $(m, n) = 1?$ Note that $gcd$ $(m, n)$ is the greatest common divisor of $m$ and $n$. $p(q - 1)$ $pq$ $\left ( p^{2}-1 \right ) (q - 1)$ $p(p - 1) (q - 1)$

Let $n =$ $p^{2}q$, where $p$ and $q$ are distinct prime numbers. How many numbers m satisfy $1 ≤ m ≤ n$ and $gcd$ $(m, n) = 1?$ Note that $gcd$ $(m, n)$ is the great...

8.1k views

answered Jul 20, 2020

2 votes

17

GATE CSE 2006 | Question: 21
For each element in a set of size $2n$, an unbiased coin is tossed. The $2n$ coin tosses are independent. An element is chosen if the corresponding coin toss was a head. The probability that exactly $n$ elements are chosen is $\frac{^{2n}\mathrm{C}_n}{4^n}$ $\frac{^{2n}\mathrm{C}_n}{2^n}$ $\frac{1}{^{2n}\mathrm{C}_n}$ $\frac{1}{2}$

For each element in a set of size $2n$, an unbiased coin is tossed. The $2n$ coin tosses are independent. An element is chosen if the corresponding coin toss was a head. ...

8.2k views

answered Jul 20, 2020

1 votes

18

GATE CSE 2008 | Question: 78
Let $x_n$ denote the number of binary strings of length $n$ that contain no consecutive $0$s. Which of the following recurrences does $x_n$ satisfy? $x_n = 2x_{n-1}$ $x_n = x_{\lfloor n/2 \rfloor} + 1$ $x_n = x_{\lfloor n/2 \rfloor} + n$ $x_n = x_{n-1} + x_{n-2}$

Let $x_n$ denote the number of binary strings of length $n$ that contain no consecutive $0$s.Which of the following recurrences does $x_n$ satisfy?$x_n = 2x_{n-1}$$x_n = ...

8.5k views

answered Jul 18, 2020

3 votes

19

GATE 1995
If the disk is rotating at 3600rpm, determine the effective data transfer rate which is defined as the number of bytes transferred per second between disk and memory. (Given the size of track = 512 bytes)?

If the disk is rotating at 3600rpm, determine the effective data transfer rate which is defined as the number of bytes transferred per second betweendisk and memory. (Giv...

3.6k views

answered Jul 17, 2020

3 votes

20

GATE CSE 2003 | Question: 34
$m$ identical balls are to be placed in $n$ distinct bags. You are given that $m \geq kn$, where $k$ is a natural number $\geq 1$. In how many ways can the balls be placed in the bags if each bag must contain at least $k$ ... $\left( \begin{array}{c} m - kn + n + k - 2 \\ n - k \end{array} \right)$

$m$ identical balls are to be placed in $n$ distinct bags. You are given that $m \geq kn$, where $k$ is a natural number $\geq 1$. In how many ways can the balls be place...

11.2k views

answered Jul 13, 2020

1 votes

21

GATE CSE 2016 Set 2 | Question: 33
Consider a $3 \ \text{GHz}$ (gigahertz) processor with a three stage pipeline and stage latencies $\large\tau_1,\tau_2$ and $\large\tau_3$ such that $\large\tau_1 =\dfrac{3 \tau_2}{4}=2\tau_3$. If the longest pipeline stage is split into two pipeline stages of equal latency , the new frequency is __________ $\text{GHz}$, ignoring delays in the pipeline registers.

Consider a $3 \ \text{GHz}$ (gigahertz) processor with a three stage pipeline and stage latencies $\large\tau_1,\tau_2$ and $\large\tau_3$ such that $\large\tau_1 =\dfrac...

19.2k views

answered Jul 13, 2020

0 votes

22

GATE CSE 2005 | Question: 65
Consider a three word machine instruction $\text{ADD} A[R_0], @B$ The first operand (destination) $ A[R_0] $ uses indexed addressing mode with $R_0$ as the index register. The second operand (source) $ @B $ uses indirect addressing mode. $A$ and $B$ ... (first operand). The number of memory cycles needed during the execution cycle of the instruction is: $3$ $4$ $5$ $6$

Consider a three word machine instruction$\text{ADD} A[R_0], @B$The first operand (destination) $“A[R_0]”$ uses indexed addressing mode with $R_0$ as the index regist...

34.3k views

answered Jul 13, 2020

0 votes

23

GATE CSE 2004 | Question: 68
A hard disk with a transfer rate of $10$ Mbytes/second is constantly transferring data to memory using DMA. The processor runs at $600$ MHz, and takes $300$ and $900$ ... percentage of processor time consumed for the transfer operation? $5.0 \%$ $1.0\%$ $0.5\%$ $0.1\%$

A hard disk with a transfer rate of $10$ Mbytes/second is constantly transferring data to memory using DMA. The processor runs at $600$ MHz, and takes $300$ and $900$ clo...

27.2k views

answered Jul 12, 2020

0 votes

24

GATE CSE 2001 | Question: 2.13
Consider the following data path of a simple non-pipelined CPU. The registers $A, B$, $A_{1},A_{2}, \textsf{MDR},$ the $\textsf{bus}$ and the $\textsf{ALU}$ are $8$-$bit$ wide. $\textsf{SP}$ and $\textsf{MAR}$ are $16$-$bit$ registers. The ... $\textsf{CPU}$ clock cycles are required to execute the "push r" instruction? $2$ $3$ $4$ $5$

Consider the following data path of a simple non-pipelined CPU. The registers $A, B$, $A_{1},A_{2}, \textsf{MDR},$ the $\textsf{bus}$ and the $\textsf{ALU}$ are $8$-$bit$...

21.2k views

answered Jul 12, 2020

0 votes

25

GATE CSE 2005 | Question: 80
Consider the following data path of a $\text{CPU}.$ The $\text{ALU},$ the bus and all the registers in the data path are of identical size. All operations including incrementation of the $\text{PC}$ and the $\text{GPRs}$ are to be carried out in ... $2$ $3$ $4$ $5$

Consider the following data path of a $\text{CPU}.$The $\text{ALU},$ the bus and all the registers in the data path are of identical size. All operations including increm...

24.2k views

answered Jul 12, 2020

0 votes

26

GATE CSE 2004 | Question: 81
Let $G_1=(V,E_1)$ and $G_2 =(V,E_2)$ be connected graphs on the same vertex set $V$ with more than two vertices. If $G_1 \cap G_2= (V,E_1\cap E_2)$ is not a connected graph, then the graph $G_1\cup G_2=(V,E_1\cup E_2)$ cannot have a cut vertex must have a cycle must have a cut-edge (bridge) has chromatic number strictly greater than those of $G_1$ and $G_2$

Let $G_1=(V,E_1)$ and $G_2 =(V,E_2)$ be connected graphs on the same vertex set $V$ with more than two vertices. If $G_1 \cap G_2= (V,E_1\cap E_2)$ is not a connected gr...

11.8k views

answered Jul 9, 2020

1 votes

27

GATE CSE 2019 | Question: 46
Let $T$ be a full binary tree with $8$ leaves. (A full binary tree has every level full.) Suppose two leaves $a$ and $b$ of $T$ are chosen uniformly and independently at random. The expected value of the distance between $a$ and $b$ in $T$ (ie., the number of edges in the unique path between $a$ and $b$) is (rounded off to $2$ decimal places) _________.

Let $T$ be a full binary tree with $8$ leaves. (A full binary tree has every level full.) Suppose two leaves $a$ and $b$ of $T$ are chosen uniformly and independently at ...

30.7k views

answered Jul 8, 2020

0 votes

28

GATE CSE 2006 | Question: 51, ISRO2016-34
Consider the following recurrence: $ T(n)=2T\left ( \sqrt{n}\right )+1,$ $T(1)=1$ Which one of the following is true? $ T(n)=\Theta (\log\log n)$ $ T(n)=\Theta (\log n)$ $ T(n)=\Theta (\sqrt{n})$ $ T(n)=\Theta (n)$

Consider the following recurrence:$ T(n)=2T\left ( \sqrt{n}\right )+1,$ $T(1)=1$Which one of the following is true?$ T(n)=\Theta (\log\log n)$$ T(n)=\Theta (\log n)$$ T(n...

28.6k views

answered Jul 6, 2020

0 votes

29

GATE CSE 2006 | Question: 17
An element in an array $X$ is called a leader if it is greater than all elements to the right of it in $X$. The best algorithm to find all leaders in an array solves it in linear time using a left to right pass of the array solves it in linear time using ... pass of the array solves it using divide and conquer in time $\Theta (n\log n)$ solves it in time $\Theta( n^2)$

An element in an array $X$ is called a leader if it is greater than all elements to the right of it in $X$. The best algorithm to find all leaders in an array solves it i...

17.9k views

answered Jul 5, 2020

0 votes

30

GATE CSE 2019 | Question: 50
What is the minimum number of $2$-input NOR gates required to implement a $4$ -variable function expressed in sum-of-minterms form as $f=\Sigma(0,2,5,7, 8, 10, 13, 15)?$ Assume that all the inputs and their complements are available. Answer: _______

What is the minimum number of $2$-input NOR gates required to implement a $4$ -variable function expressed in sum-of-minterms form as $f=\Sigma(0,2,5,7, 8, 10, 13, 15)?$ ...

30.4k views

answered Jul 2, 2020

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