Recent activity by falgun09 / GATE Overflow for GATE CSE

1 answer

1

GATE Overflow Test Series | Mock GATE | Test 4 | Question: 45
What is time complexity of Dijkstra's algorithm if we use sorted linked list instead of min-heap or priority queue. Assume graph $G(V,E)$ is represented by an adjacency list and $|V| = v$ and $|E| = e.$ $\Theta((v + e)\log v)$ $\Theta(v^2 + e \log v)$ $\Theta(v . e)$ $\Theta(v^2)$

What is time complexity of Dijkstra's algorithm if we use sorted linked list instead of min-heap or priority queue. Assume graph $G(V,E)$ is represented by an adjacency l...

460 views

commented Feb 10, 2021

3 answers

2

GATE Overflow Test Series | Probability | Test 1 | Question: 23
Suppose that there are $9$ balls in total of colors red and white. The probability that the two randomly chosen balls are of the same color is the same as the probability that they are of different colors. Which of the following is the correct choices for number ... the appropriate choices) $w=3, r = 6$ $w=6,r=3$ $w=4,r=5$ $w=5,r=4$

Suppose that there are $9$ balls in total of colors red and white. The probability that the two randomly chosen balls are of the same color is the same as the probability...

237 views

commented Feb 6, 2021

2 answers

3

GATE Overflow Test Series | Mock GATE | Test 3 | Question: 41
AVL tree is a self-balancing Binary Search Tree (BST) where the difference between heights of left and right subtrees cannot be more than one for all nodes. What is the different shapes possible for an AVL tree with minimum number of nodes and height $4?\; ($Assume height of root as $0).$

AVL tree is a self-balancing Binary Search Tree (BST) where the difference between heights of left and right subtrees cannot be more than one for all nodes. What is the d...

738 views

commented Feb 4, 2021

1 answer

4

GATE Overflow Test Series | Mock GATE | Test 3 | Question: 39
Consider the grammar $S \rightarrow AaAb \mid BbBa$ $A \rightarrow \varepsilon$ $B \rightarrow \varepsilon$ If the number of shift-reduce conflicts for $LR(0)$ parsing of the above grammar is $\alpha,$ and the number of reduce-reduce conflicts is $\beta,$ then the value of $\alpha - \beta =$__________

Consider the grammar$S \rightarrow AaAb \mid BbBa$$A \rightarrow \varepsilon$$B \rightarrow \varepsilon$If the number of shift-reduce conflicts for $LR(0)$ parsing of the...

604 views

commented Feb 3, 2021

1 answer

5

GATE Overflow Test Series | Mock GATE | Test 3 | Question: 63
Assume a main memory access time of $112\;ns$ and a memory system capable of a sustained transfer rate of $8$ GBps. If the block size is $64$ bytes, what is the maximum number of outstanding misses we ... maintain the peak bandwidth given the request stream and that accesses never conflict. For simplicity, ignore the time between misses.

Assume a main memory access time of $112\;ns$ and a memory system capable of a sustained transfer rate of $8$ GBps. If the block size is $64$ bytes, what is the maximum n...

603 views

commented Feb 2, 2021

2 answers

6

GATE Overflow Test Series | Operating Systems | Test 2 | Question: 23
A typical program has $10\%$ memory instructions. Assume there are $2\%$ data TLB misses, each requiring $100$ extra cycles to be handled. Also assume that each instruction requires $1$ cycle to execute, data TLB access ... takes $45$ extra cycles to be handled. How long (in cycles) would it take to execute $100$ instructions?

A typical program has $10\%$ memory instructions. Assume there are $2\%$ data TLB misses, each requiring $100$ extra cycles to be handled. Also assume that each instructi...

560 views

commented Jan 29, 2021

1 answer

7

GATE Overflow Test Series | Mixed Subjects | Test 3 | Question: 17
Consider the following schedule $\textbf{Schedule}$ ... $a,$ the value of $2^a = $ ________

Consider the following schedule$$\textbf{Schedule}$$$$\begin{array}{|c|c|c|c|c|c|} \hline T_{1} & T_{2} & T_{3} & T_{4} \\\hline R(x) & & & \\ & R(x) & & \\ & & R(x) & \...

213 views

commented Jan 26, 2021

2 answers

8

GATE Overflow Test Series | Digital Logic | Test 1 | Question: 10
Assume that the propagation delay in each gate in a $16$-bit ripple carry adder (made of AND, OR and NOT gates only with upto $3$ inputs) is $1ns.$ Time taken in $\text{nanoseconds}$ to perform a $16$-bit addition is $\_\_\_\_\_\_.$

Assume that the propagation delay in each gate in a $16$-bit ripple carry adder (made of AND, OR and NOT gates only with upto $3$ inputs) is $1ns.$ Time taken in $\text{n...

912 views

commented Jan 23, 2021

1 answer

9

GATE Overflow Test Series | Mock GATE | Test 2 | Question: 1
Let $a(t), b(t),$ and $c(t)$ be the lengths of the three sides of a triangle $t$ in non-decreasing order (i.e. $a(t) \leq b(t) \leq c(t)).$ ... $X \cup Y$ $X \cap Y$ $X \oplus Y$ None of the above

Let $a(t), b(t),$ and $c(t)$ be the lengths of the three sides of a triangle $t$ in non-decreasing order (i.e. $a(t) \leq b(t) \leq c(t)).$We define the sets:$\blacksquar...

508 views

commented Jan 22, 2021

1 answer

10

GATE Overflow Test Series | Operating Systems | Test 2 | Question: 25
A demand paging system takes $181$ time units to service a page fault and $301$ time units to replace a dirty page. Memory access time is $1$ time unit. The probability of a page fault is $p$. In case of a page fault, ... the average access time is $7$ time units. Then the value of $100p$ is _______ (up to two decimal places).

A demand paging system takes $181$ time units to service a page fault and $301$ time units to replace a dirty page. Memory access time is $1$ time unit. The probability o...

442 views

commented Jan 22, 2021

1 answer

11

GATE Overflow Test Series | Data Structures | Test 1 | Question: 11
Let $L$ be a linked list of $n$ elements and $I$ be another linked list of $k$ node positions in $L$ ($n/4 < k < n/2)$ and elements in $I$ are not necessarily in sorted order. The best possible algorithm (use $O(1)$ extra space if ... $I$ will run in _____ $\Theta(n)$ $\Theta (n \log n)$ $\Theta (n .k \log k) $ $\Theta (nk)$

Let $L$ be a linked list of $n$ elements and $I$ be another linked list of $k$ node positions in $L$ ($n/4 < k < n/2)$ and elements in $I$ are not necessarily in sorted o...

672 views

commented Jan 15, 2021

1 answer

12

GATE Overflow Test Series | Linear Algebra | Test 1 | Question: 21
The value of $'x'$ for which all the eigen values of the matrix given below $\begin{bmatrix} 2 & 3+i & 6\\ x & 3 & 2\\ 1 & 4 & 3\\ \end{bmatrix}$ are real is ________ $(i = \sqrt{-1})$ $3 + i$ $1 - 3i$ $3 - i$ $1 + 3i$

The value of $'x'$ for which all the eigen values of the matrix given below $\begin{bmatrix}2 & 3+i & 6\\x & 3 & 2\\1 & 4 & 3\\\end{bmatrix}$ are real is ________ $(i = \...

371 views

commented Jan 10, 2021

1 answer

13

GATE Overflow Test Series | Computer Networks | Test 1 | Question: 10
Which of the following is/are NOT correct? (Mark all the appropriate choices) Full-duplex ethernet use CSMA/CD for collision detection A dedicated switch port is required for each full-duplex node Hubs can ... mode Half-duplex Ethernet shares a collision domain and provides a lower effective throughput than full-duplex Ethernet

Which of the following is/are NOT correct? (Mark all the appropriate choices)Full-duplex ethernet use CSMA/CD for collision detectionA dedicated switch port is required f...

492 views

commented Dec 31, 2020

1 answer

14

GATE Overflow Test Series | Algorithms | Test 2 | Question: 24
Which of the following is/are correct with respect to Dijkstra's algorithm to find Single Source Shortest Path in a weighted directed graph $G$? (Mark all the appropriate choices) Dijkstra's algorithm runs in $O(|E| \lg |V|)$ ... has a worst case time complexity of $O(|V|\lg |V| + |E|)$ when implemented with a Fibonacci heap

Which of the following is/are correct with respect to Dijkstra's algorithm to find Single Source Shortest Path in a weighted directed graph $G$? (Mark all the appropriate...

487 views

commented Dec 25, 2020

1 answer

15

GATE Overflow Test Series | Operating Systems | Test 1 | Question: 26
Consider a system having $k$ resources of the same type. These resources are shared by $5$ processes $A,B,C,D$, and $E$ which have peak demands of $5,7,9,3$ and $8$ respectively. Further it is restricted that at any ... of the following values of $k,$ deadlock may occur? (Mark all the appropriate choices) $24$ $25$ $27$ $26$

Consider a system having $k$ resources of the same type. These resources are shared by $5$ processes $A,B,C,D$, and $E$ which have peak demands of $5,7,9,3$ and $8$ respe...

460 views

commented Dec 12, 2020

1 answer

16

GATE Overflow Test Series | Linear Algebra | Test 1 | Question: 11
If $A = \begin{bmatrix} 1&-3 & -4\\ -1 & 3 & 4\\ 1 & -3 & -4 \end{bmatrix},$ is a nilpotent matrix, its index is _______

If $A = \begin{bmatrix}1&-3 & -4\\-1 & 3 & 4\\1 & -3 & -4\end{bmatrix},$ is a nilpotent matrix, its index is _______

266 views

commented Dec 5, 2020

1 answer

17

GATE Overflow Test Series | Computer Organization and Architecture | Test 1 | Question: 30
Consider a CPU with an average CPI of $1.4$ ... allocate policy with the probability of a cache block being dirty being $0.15$ (round off to $2$ decimal places).

Consider a CPU with an average CPI of $1.4$ when all memory accesses hit on the cache.Assume an instruction mix$$\begin{array}{|c | c|}\hline\text{ALU }& 45\%\\\text{LOAD...

842 views

commented Nov 13, 2020

1 answer

18

GATE Overflow Test Series | Discrete Mathematics | Test 3 | Question: 27
Suppose $G$ is a group that has exactly $48$ distinct elements of order $5$. How many distinct subgroups of order $5$ does $G$ have? $12$ $6$ $1$ $4$

Suppose $G$ is a group that has exactly $48$ distinct elements of order $5$. How many distinct subgroups of order $5$ does $G$ have?$12$$6$$1$$4$

516 views

commented Nov 9, 2020

1 answer

19

GATE Overflow Test Series | Algorithms | Test 2 | Question: 29
Consider a weighted undirected graph with distinct positive edge weights and let $(u,v)$ be an edge in the graph. It is known that the shortest path from the source vertex $s$ to $u$ has weight $36$ and the shortest path from $s$ to $v$ has weight $44$. ... $(u, v) \leq 8$ weight $(u, v) > 8$ weight $(u, v) \geq 8$

Consider a weighted undirected graph with distinct positive edge weights and let $(u,v)$ be an edge in the graph. It is known that the shortest path from the source verte...

261 views

commented Nov 3, 2020

1 answer

20

GATE Overflow Test Series | Computer Organization and Architecture | Test 1 | Question: 19
Suppose the functions $A$ and $B$ can be computed in $6$ and $4$ nanoseconds by functional units $U_A$ and $U_B$, respectively. Given two instances of $U_A$ and three instances of $U_B$, ... . Ignoring all other delays, the minimum time required to complete this computation (in nanoseconds) is _______

Suppose the functions $A$ and $B$ can be computed in $6$ and $4$ nanoseconds by functional units $U_A$ and $U_B$, respectively. Given two instances of $U_A$ and three ins...

504 views

commented Nov 1, 2020

2 answers

21

cache memory
A computer system contains a main memory of 32K 16-bit words. It also has a 4Kword cache divided into four-line sets with 64 words per line. Assume that the cache is initially empty. The processor fetches words from locations 0, 1, 2, . . ., ... is 10 times faster than main memory. Estimate the improvement resulting from the use of the cache. Assume an LRU policy for block replacement.

A computer system contains a main memory of 32K 16-bit words. It also has a 4Kword cache divided into four-line sets with 64 words per line. Assume that the cache is init...

5.2k views

commented Nov 1, 2020

1 answer

22

GATE Overflow Test Series | Computer Organization and Architecture | Test 1 | Question: 22
A Disk drive with $8$ surfaces, $256$ tracks/surface, $256$ sectors/track, $512$ bytes/sector and rotation speed of $3600$ rpm is operated in cycle stealing mode whereby whenever one $2$ Byte word ... the maximum percentage of time that a CPU gets blocked during DMA operations (rounded to $1$ decimal point).

A Disk drive with $8$ surfaces, $256$ tracks/surface, $256$ sectors/track, $512$ bytes/sector and rotation speed of $3600$ rpm is operated in cycle stealing mode whereby ...

604 views

commented Sep 12, 2020

2 answers

23

GATE Overflow Test Series | Computer Organization and Architecture | Test 1 | Question: 26
Assume a main memory access time of $64\;ns$ and a memory system capable of a sustained transfer rate of $16$ GBps. If the block size is $64$ bytes, what is the maximum number of ... the peak bandwidth given the request stream and that accesses never conflict. For simplicity, ignore the time between misses.

Assume a main memory access time of $64\;ns$ and a memory system capable of a sustained transfer rate of $16$ GBps. If the block size is $64$ bytes, what is the maximum n...

624 views

comment edited Sep 3, 2020

1 answer

24

GATE Overflow Test Series | Programming | Test 1 | Question: 9
Which of the following correctly declare a pointer to function returning a pointer to an integer and accepting a pointer to a one-dimensional integer array of size $10$ as input? int * (*p)(int * my_array[10]) int * (*p)(int (* my_array)[10]) int * p(int * my_array[10]) int * (*p) (int * my_array)

Which of the following correctly declare a pointer to function returning a pointer to an integer and accepting a pointer to a one-dimensional integer array of size $10$ a...

319 views

comment edited Jul 29, 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