Recent activity by shashankpal / GATE Overflow for GATE CSE

6 answers

1

GATE CSE 2021 Set 2 | Question: 50
Let $S$ be a set of consisting of $10$ elements. The number of tuples of the form $(A,B)$ such that $A$ and $B$ are subsets of $S$, and $A \subseteq B$ is ___________

Let $S$ be a set of consisting of $10$ elements. The number of tuples of the form $(A,B)$ such that $A$ and $B$ are subsets of $S$, and $A \subseteq B$ is ___________

12.2k views

answer edited Feb 18, 2021

3 answers

2

GATE CSE 2021 Set 2 | Question: 46
Consider the following directed graph: Which of the following is/are correct about the graph? The graph does not have a topological order A depth-first traversal starting at vertex $S$ classifies three directed edges as back edges The graph does not have a strongly connected component For each pair of vertices $u$ and $v$, there is a directed path from $u$ to $v$

Consider the following directed graph:Which of the following is/are correct about the graph?The graph does not have a topological orderA depth-first traversal starting at...

8.9k views

answer edited Feb 18, 2021

4 answers

3

GATE CSE 2021 Set 2 | Question: 42
Consider the following multi-threaded code segment (in a mix of C and pseudo-code), invoked by two processes $P_1$ and $P_2$, and each of the processes spawns two threads $T_1$ and $T_2$: int x = 0; // global Lock L1; // global main () { create a ... the value of $y$ as $2.$ Both $T_1$ and $T_2$, in both the processes, will print the value of $y$ as $1.$

Consider the following multi-threaded code segment (in a mix of C and pseudo-code), invoked by two processes $P_1$ and $P_2$, and each of the processes ...

10.5k views

commented Feb 18, 2021

1 answer

4

GATE CSE 2021 Set 2 | Question: 51
Consider the following augmented grammar with $\{ \#, @, <, >, a, b, c \}$ ... $\text{GOTO(GOTO}(I_0<), <)$ is ___________

Consider the following augmented grammar with $\{ \#, @, <, >, a, b, c \}$ as the set of terminals. $$\begin{array}{l} S’ \rightarrow S \\ S \rightarrow S \# cS \\ S \r...

6.7k views

answered Feb 18, 2021

3 answers

5

GATE CSE 2021 Set 2 | Question: 55
In a directed acyclic graph with a source vertex $\textsf{s}$, the $\textit{quality-score}$ of a directed path is defined to be the product of the weights of the edges on the path. Further, for a vertex $v$ other than $\textsf{s}$, the quality ... $\textsf{s}$ is assumed to be $1$. The sum of the quality-scores of all vertices on the graph shown above is _______

In a directed acyclic graph with a source vertex $\textsf{s}$, the $\textit{quality-score}$ of a directed path is defined to be the product of the weights of the edges on...

7.3k views

answered Feb 18, 2021

4 answers

6

GATE CSE 1999 | Question: 19
A certain computer system has the segmented paging architecture for virtual memory. The memory is byte addressable. Both virtual and physical address spaces contain $2^{16}$ bytes each. The virtual address space is divided into $8$ non-overlapping equal ... in page table entry for storing the aging information for the page? Assume that the page size is $512$ bytes.

A certain computer system has the segmented paging architecture for virtual memory. The memory is byte addressable. Both virtual and physical address spaces contain $2^{1...

25.9k views

answer edited Jan 31, 2021

14 answers

7

GATE CSE 2008 | Question: 67
A processor uses $36$ bit physical address and $32$ bit virtual addresses, with a page frame size of $4$ Kbytes. Each page table entry is of size $4$ bytes. A three level page table is used for virtual to physical address translation, where the virtual address is used as ... tables are respectively $\text{20,20,20}$ $\text{24,24,24}$ $\text{24,24,20}$ $\text{25,25,24}$

A processor uses $36$ bit physical address and $32$ bit virtual addresses, with a page frame size of $4$ Kbytes. Each page table entry is of size $4$ bytes. A three level...

77.4k views

comment edited Jan 31, 2021

5 answers

8

GATE CSE 2012 | Question: 29
Let $G$ be a weighted graph with edge weights greater than one and $G'$ be the graph constructed by squaring the weights of edges in $G$. Let $T$ and $T'$ be the minimum spanning trees of $G$ and $G'$, respectively, with total weights $t$ ... $t' < t^2$ $T' \neq T$ but total weight $t' = t^2$ None of the above

Let $G$ be a weighted graph with edge weights greater than one and $G'$ be the graph constructed by squaring the weights of edges in $G$. Let $T$ and $T'$ be the minimum ...

16.6k views

comment edited Jan 17, 2021

5 answers

9

GATE CSE 2018 | Question: 43
Let $G$ be a graph with $100!$ vertices, with each vertex labelled by a distinct permutation of the numbers $1, 2,\ldots, 100.$ There is an edge between vertices $u$ and $v$ if and only if the label of $u$ can be obtained by swapping two adjacent ... denote the degree of a vertex in $G$, and $z$ denote the number of connected components in $G$. Then, $y+10z=$ ______.

Let $G$ be a graph with $100!$ vertices, with each vertex labelled by a distinct permutation of the numbers $1, 2,\ldots, 100.$ There is an edge between vertices $u$ and ...

20.0k views

commented Jan 13, 2021

5 answers

10

GATE CSE 2015 Set 3 | Question: 4
Consider the equality $\displaystyle{\sum_{i=0}^n} i^3 = X$ and the following choices for $X$: $\Theta(n^4)$ $\Theta(n^5)$ $O(n^5)$ $\Omega(n^3)$ The equality above remains correct if $X$ is replaced by Only I Only II I or III or IV but not II II or III or IV but not I

Consider the equality $\displaystyle{\sum_{i=0}^n} i^3 = X$ and the following choices for $X$:$\Theta(n^4)$$\Theta(n^5)$$O(n^5)$$\Omega(n^3)$The equality above remains co...

16.8k views

commented Jan 13, 2021

7 answers

11

GATE CSE 2006 | Question: 12
To implement Dijkstra’s shortest path algorithm on unweighted graphs so that it runs in linear time, the data structure to be used is: Queue Stack Heap B-Tree

To implement Dijkstra’s shortest path algorithm on unweighted graphs so that it runs in linear time, the data structure to be used is:QueueStackHeapB-Tree

31.8k views

commented Jan 12, 2021

4 answers

12

GATE IT 2005 | Question: 84b
A sink in a directed graph is a vertex i such that there is an edge from every vertex $j \neq i$ to $i$ and there is no edge from $i$ to any other vertex. A directed graph $G$ with $n$ vertices is represented by its adjacency matrix $A$, where $A[i] [j] = 1$ if there is an edge ... $(!A[i][j] \ \left | \right | A[j][i])$ $(A[i][j] \ \left | \right | \ !A[j][i])$

A sink in a directed graph is a vertex i such that there is an edge from every vertex $j \neq i$ to $i$ and there is no edge from $i$ to any other vertex. A directed grap...

7.6k views

commented Jan 11, 2021

7 answers

13

GATE CSE 2015 Set 3 | Question: 49
Suppose $c = \langle c[0], \dots, c[k-1]\rangle$ is an array of length $k$, where all the entries are from the set $\{0, 1\}$. For any positive integers $a \text{ and } n$, consider the following pseudocode. DOSOMETHING (c, a, n) $z \leftarrow 1$ ... , then the output of DOSOMETHING(c, a, n) is _______.

Suppose $c = \langle c[0], \dots, c[k-1]\rangle$ is an array of length $k$, where all the entries are from the set $\{0, 1\}$. For any positive integers $a \text{ and } n...

7.5k views

comment edited Jan 10, 2021

7 answers

14

GATE CSE 2015 Set 1 | Question: 31
Consider the following C function. int fun1 (int n) { int i, j, k, p, q = 0; for (i = 1; i < n; ++i) { p = 0; for (j = n; j > 1; j = j/2) ++p; for (k = 1; k < p; k = k * 2) ++q; } return q; } Which one of the following most closely approximates the return value of the function $\text{fun1}$? $n^3$ $n(\log n)^2$ $n \log n$ $n \log(\log n)$

Consider the following C function.int fun1 (int n) { int i, j, k, p, q = 0; for (i = 1; i < n; ++i) { p = 0; for (j = n; j 1; j = j/2) ++p; for (k = 1; k < p; k = k * 2)...

21.0k views

commented Jan 10, 2021

2 answers

15

GATE CSE 1996 | Question: 14
A two dimensional array $A[1..n][1..n]$ of integers is partially sorted if $\forall i, j\in [1..n-1], A[i][j] < A[i][j+1] \text{ and } A[i][j] < A[i+1][j]$ The smallest item in the array is at $A[i][j]$ where $i=\_\_$ and $j=\_\_$. The smallest ... if A[i+1][j] < A[i][j] ___ then begin A[i][j]:=A[i+1][j]; i:=i+1; end else begin _____ end A[i][j]:= ____ end

A two dimensional array $A[1..n][1..n]$ of integers is partially sorted if $\forall i, j\in [1..n-1], A[i][j] < A[i][j+1] \text{ and } A[i][j] < A[i+1][j]$The smallest it...

5.8k views

commented Jan 10, 2021

3 answers

16

TIFR CSE 2015 | Part B | Question: 1
Consider the following recurrence relation: $T(n) = \begin{cases} 2T (\lfloor\sqrt{n}\rfloor)+ \log n & \text{if }n \geq 2 \\ 1& \text{if }n = 1 \end{cases}$ Which of the following statements is TRUE? $T(n)$ is $O(\log n)$. $T(n)$ ... but not $O(\log^{3/2} n)$. $T(n)$ is $O(\log^{2} n \cdot \log \log n)$ but not $O(\log^{2} n)$.

Consider the following recurrence relation:$T(n)= \begin{cases}2T (\lfloor\sqrt{n}\rfloor)+ \log n & \text{if }n \geq 2 \\ 1& \text{if }n = 1 \end{cases}$Which of the...

3.1k views

answer edited Jan 9, 2021

4 answers

17

TIFR CSE 2014 | Part B | Question: 11
Consider the following recurrence relation: $T\left(n\right)= \begin{cases} T\left(\frac{n}{k}\right)+ T\left(\frac{3n}{4}\right)+ n & \text{if } n \geq 2 \\ 1& \text{if } n=1 \end{cases}$ Which of the following statements is FALSE? $T(n)$ is $O(n^{3/2})$ ... $k=4$. $T(n)$ is $O(n \log n)$ when $k=5$. $T(n)$ is $O(n)$ when $k=5$.

Consider the following recurrence relation:$T\left(n\right)=\begin{cases}T\left(\frac{n}{k}\right)+ T\left(\frac{3n}{4}\right)+ n & \text{if } n \geq 2 \\ 1& \text{if }...

5.7k views

commented Jan 9, 2021

2 answers

18

GATE CSE 2016 Set 2 | Question: 39
The given diagram shows the flowchart for a recursive function $A(n)$. Assume that all statements, except for the recursive calls, have $O(1)$ time complexity. If the worst case time complexity of this function is $O(n^{\alpha})$, then the least possible value (accurate up to two decimal positions) of $\alpha$ is ________. Flow chart for Recursive Function $A(n)$.

The given diagram shows the flowchart for a recursive function $A(n)$. Assume that all statements, except for the recursive calls, have $O(1)$ time complexity. If the wor...

16.6k views

commented Jan 9, 2021

9 answers

19

GATE CSE 2019 | Question: 10
Let $G$ be an arbitrary group. Consider the following relations on $G$: $R_1: \forall a , b \in G, \: a R_1 b \text{ if and only if } \exists g \in G \text{ such that } a = g^{-1}bg$ ... $R_1$ and $R_2$ $R_1$ only $R_2$ only Neither $R_1$ nor $R_2$

Let $G$ be an arbitrary group. Consider the following relations on $G$:$R_1: \forall a , b \in G, \: a R_1 b \text{ if and only if } \exists g \in G \text{ such that } a ...

17.6k views

answer edited Jan 7, 2021

6 answers

20

GATE CSE 2017 Set 2 | Question: 21
Consider the set $X=\{a, b, c, d, e\}$ under partial ordering $R=\{(a,a), (a, b), (a, c), (a, d), (a, e), (b, b), (b, c), (b, e), (c, c), (c, e), (d, d), (d, e), (e, e) \}$ The Hasse diagram of the partial order $(X, R)$ is shown below. The minimum number of ordered pairs that need to be added to $R$ to make $(X, R)$ a lattice is ______

Consider the set $X=\{a, b, c, d, e\}$ under partial ordering $R=\{(a,a), (a, b), (a, c), (a, d), (a, e), (b, b), (b, c), (b, e), (c, c), (c, e), (d, d), (d, e), (e, e...

12.1k views

commented Jan 7, 2021

8 answers

21

GATE CSE 2016 Set 2 | Question: 28
Consider a set $U$ of $23$ different compounds in a chemistry lab. There is a subset $S$ of $U$ of $9$ compounds, each of which reacts with exactly $3$ compounds of $U$. Consider the following statements: Each compound in U \ S reacts ... \ S reacts with an even number of compounds. Which one of the above statements is ALWAYS TRUE? Only I Only II Only III None.

Consider a set $U$ of $23$ different compounds in a chemistry lab. There is a subset $S$ of $U$ of $9$ compounds, each of which reacts with exactly $3$ compounds of $U$. ...

16.8k views

comment edited Jan 6, 2021

6 answers

22

GATE CSE 2003 | Question: 39
Let $\Sigma = \left\{a, b, c, d, e\right\}$ be an alphabet. We define an encoding scheme as follows: $g(a) = 3, g(b) = 5, g(c) = 7, g(d) = 9, g(e) = 11$. Let $p_i$ denote the i-th prime number $\left(p_1 = 2\right)$ ... numbers is the encoding, $h$, of a non-empty sequence of strings? $2^73^75^7$ $2^83^85^8$ $2^93^95^9$ $2^{10}3^{10}5^{10}$

Let $\Sigma = \left\{a, b, c, d, e\right\}$ be an alphabet. We define an encoding scheme as follows:$g(a) = 3, g(b) = 5, g(c) = 7, g(d) = 9, g(e) = 11$.Let $p_i$ denote t...

7.7k views

answer edited Jan 5, 2021

6 answers

23

GATE IT 2006 | Question: 20
Which of the following statement(s) is TRUE? A hash function takes a message of arbitrary length and generates a fixed length code. A hash function takes a message of fixed length and generates a code of variable length. A hash function may give the same hash value for distinct messages. I only II and III only I and III only II only

Which of the following statement(s) is TRUE?A hash function takes a message of arbitrary length and generates a fixed length code.A hash function takes a message of fixed...

12.2k views

commented Dec 25, 2020

8 answers

24

GATE CSE 2014 Set 3 | Question: 39
Suppose we have a balanced binary search tree $T$ holding $n$ numbers. We are given two numbers $L$ and $H$ and wish to sum up all the numbers in $T$ that lie between $L$ and $H$. Suppose there are $m$ such numbers in $T$. If the tightest upper bound on the time to compute the sum is $O(n^a\log^bn+m^c\log^dn)$, the value of $a+10b+100c+1000d$ is ______.

Suppose we have a balanced binary search tree $T$ holding $n$ numbers. We are given two numbers $L$ and $H$ and wish to sum up all the numbers in $T$ that lie between $L$...

31.8k views

commented Dec 23, 2020

2 answers

25

GATE IT 2008 | Question: 52
C program is given below: # include <stdio.h> int main () { int i, j; char a [2] [3] = {{'a', 'b', 'c'}, {'d', 'e', 'f'}}; char b [3] [2]; char *p = *b; for (i = 0; i < 2; i++) { for (j = 0; j < ... $\text{b e}$ $\text{c f}$ $\text{a c}$ $\text{e b}$ $\text{d f}$ $\text{a e}$ $\text{d c}$ $\text{b f}$

C program is given below:# include <stdio.h int main () { int i, j; char a [3] = {{'a', 'b', 'c'}, {'d', 'e', 'f'}}; char b [3] ; char *p = *b; for (i = 0; i < 2; i++)...

10.6k views

comment edited Dec 17, 2020

5 answers

26

GATE CSE 2009 | Question: 51
A hard disk has $63$ sectors per track, $10$ platters each with $2$ recording surfaces and $1000$ cylinders. The address of a sector is given as a triple $\langle c, h, s \rangle$, where $c$ is the cylinder number, $h$ is the surface number ... $\langle 400, 16, 29 \rangle$ corresponds to sector number: $505035$ $505036$ $505037$ $505038$

A hard disk has $63$ sectors per track, $10$ platters each with $2$ recording surfaces and $1000$ cylinders. The address of a sector is given as a triple $\langle c, h, s...

20.1k views

comment edited Dec 4, 2020

7 answers

27

GATE IT 2006 | Question: 66
A router has two full-duplex Ethernet interfaces each operating at $100$ $\text{Mb/s}$. Ethernet frames are at least $84$ $\text{bytes}$ long (including the Preamble and the Inter-Packet-Gap). The maximum packet processing time at the router for wirespeed forwarding to be possible is (in microseconds) $0.01$ $3.36$ $6.72$ $8$

A router has two full-duplex Ethernet interfaces each operating at $100$ $\text{Mb/s}$. Ethernet frames are at least $84$ $\text{bytes}$ long (including the Preamble and ...

22.4k views

commented Dec 3, 2020

3 answers

28

GATE CSE 2008 | Question: 59
A client process P needs to make a TCP connection to a server process S. Consider the following situation: the server process S executes a $\text{socket()}$, a $\text{bind()}$ and a $\text{listen()}$ system call in that order, following which ... $\text{connect()}$ system call returns an error $\text{connect()}$ system call results in a core dump

A client process P needs to make a TCP connection to a server process S. Consider the following situation: the server process S executes a $\text{socket()}$, a $\text{bin...

16.9k views

comment edited Dec 3, 2020

5 answers

29

GATE CSE 1998 | Question: 25b
Consider a disk with $c$ cylinders, $t$ tracks per cylinder, $s$ sectors per track and a sector length $s_l$. A logical file $d_l$ with fixed record length $r_l$ is stored continuously on this disk starting at location $(c_L, t_L, s_L)$, where ... the formula to calculate the disk address (i.e. cylinder, track and sector) of a logical record n assuming that $r_l=s_l$.

Consider a disk with $c$ cylinders, $t$ tracks per cylinder, $s$ sectors per track and a sector length $s_l$. A logical file $d_l$ with fixed record length $r_l$ is stor...

3.0k views

comment edited Dec 1, 2020

2 answers

30

OS:- Page fault service time vs Effective memory access time
I got some doubt while solving previous year questions:- Since While calculating EMAT and question involves page fault service time,we use formulae:- p*s+(1-p)*m ,taken from Galvin p is page fault rate s is page fault service time m ... sense. So why in first reference/doubt we are not using 2m instead of m in case of NOT a page fault?

I got some doubt while solving previous year questions:-Since While calculating EMAT and question involves page fault service time,we use formulae:-p*s+(1-p)*m ,taken fro...

13.1k views

comment edited Nov 27, 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