Recent activity by pranavsettaluri9 / GATE Overflow for GATE CSE

1 answer

1

GATE Overflow Test Series | Mock GATE | Test 5 | Question: 62
Which of the following is/are CORRECT? (Mark all the appropriate choices) The loop invariant code motion transformation always results in a faster executing code. During the high level control/dataflow graph (CDFG) ... resources. The dead code elimination transformation may sometimes result in a larger control/dataflow graph (CDFG).

Which of the following is/are CORRECT? (Mark all the appropriate choices)The loop invariant code motion transformation always results in a faster executing code.During th...

423 views

commented Feb 10, 2021

3 answers

2

ISI Entrance Exam MTech (CS)
Consider all possible trees with $n$ nodes. Let $k$ be the number of nodes with degree greater than $1$ in a given tree. What is the maximum possible value of $k$?

Consider all possible trees with $n$ nodes. Let $k$ be the number of nodes with degree greater than $1$ in a given tree. What is the maximum possible value of $k$?

2.4k views

commented Oct 16, 2020

4 answers

3

GATE CSE 2008 | Question: 50
Which of the following statements are true? Every left-recursive grammar can be converted to a right-recursive grammar and vice-versa All $\epsilon$-productions can be removed from any context-free grammar by suitable transformations The language generated by a context-free grammar all ... trees I, II, III and IV II, III and IV only I, III and IV only I, II and IV only

Which of the following statements are true?Every left-recursive grammar can be converted to a right-recursive grammar and vice-versaAll $\epsilon$-productions can be remo...

13.6k views

commented Sep 25, 2020

6 answers

4

GATE CSE 2009 | Question: 40
Let $L = L_1 \cap L_2 $, where $L_1$ and $L_2$ are languages as defined below: $L_1= \left \{ a^m b^mca^nb^n \mid m,n \geq 0 \right \}$ $L_2=\left \{ a^i b^j c^k \mid i,j,k \geq 0 \right \}$ Then $L$ is Not recursive Regular Context free but not regular Recursively enumerable but not context free.

Let $L = L_1 \cap L_2 $, where $L_1$ and $L_2$ are languages as defined below:$L_1= \left \{ a^m b^mca^nb^n \mid m,n \geq 0 \right \}$$L_2=\left \{ a^i b^j c^k \mid i,j,k...

13.1k views

commented Jul 27, 2020

3 answers

5

TIFR CSE 2013 | Part B | Question: 8
Which one of the following languages over the alphabet ${0, 1}$ is regular? The language of balanced parentheses where $0, 1$ are thought of as $(,)$ respectively. The language of palindromes, i.e. bit strings $x$ that read the same from left to right as well as right to ... $(c)$ above. $\left \{ 0^{m} 1^{n} | 1 \leq m \leq n\right \}$

Which one of the following languages over the alphabet ${0, 1}$ is regular?The language of balanced parentheses where $0, 1$ are thought of as $(,)$ respectively.The lang...

4.1k views

commented Jul 27, 2020

4 answers

6

GATE CSE 2003 | Question: 51
Let $G=\left(\left\{S\right\}, \left\{a,b\right\},R,S\right)$ be a context free grammar where the rule set R is $S \to a S b \mid S S \mid \epsilon$ Which of the following statements is true? $G$ is not ambiguous There ... $L(G)$ We can find a deterministic finite state automaton that accepts $L(G)$

Let $G=\left(\left\{S\right\}, \left\{a,b\right\},R,S\right)$ be a context free grammar where the rule set R is $S \to a S b \mid S S \mid \epsilon$Which of the following...

17.5k views

commented Jul 24, 2020

4 answers

7

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.4k views

commented Jul 17, 2020

3 answers

8

GATE CSE 2014 Set 2 | Question: 31
Consider the procedure below for the Producer-Consumer problem which uses semaphores: semaphore n = 0; semaphore s = 1; void producer() { while(true) { produce(); semWait(s); addToBuffer(); semSignal(s); semSignal(n); } } void consumer() { while( ... the buffer is empty. The starting value for the semaphore $n$ must be $1$ and not $0$ for deadlock-free operation.

Consider the procedure below for the Producer-Consumer problem which uses semaphores: semaphore n = 0; semaphore s = 1;void producer() { while(true) { produce(); semWait(...

14.2k views

commented Jul 10, 2020

11 answers

9

GATE IT 2005 | Question: 41
Given below is a program which when executed spawns two concurrent processes : semaphore $X : = 0 ;$ /* Process now forks into concurrent processes $P1$ & $P2$ ... (II) are true. (I) is true but (II) is false. (II) is true but (I) is false Both (I) and (II) are false

Given below is a program which when executed spawns two concurrent processes :semaphore $X : = 0 ;$/* Process now forks into concurrent processes $P1$ & $P2$ */$\begin{ar...

23.9k views

commented Jul 9, 2020

2 answers

10

Doubt on Write through
Consider the following specifications: Hit ratio for read = 0.8, Hit ratio for write = 0.9 Block size =2 words, cache of 10 ns is 10 times faster than main memory On any miss entire block is moved from main memory to cache memory 20% references are for write operations What is avg access time with write through using 1) Write allocate 2) No write allocate

Consider the following specifications:Hit ratio for read = 0.8,Hit ratio for write = 0.9Block size =2 words,cache of 10 ns is 10 times faster than main memory On any miss...

981 views

comment edited Jul 9, 2020

4 answers

11

GATE CSE 2005 | Question: 68
A $5$ stage pipelined CPU has the following sequence of stages: IF - instruction fetch from instruction memory RD - Instruction decode and register read EX - Execute: ALU operation for data and address computation MA - Data memory access - for write access, the ... taken to complete the above sequence of instructions starting from the fetch of $I_1$? $8$ $10$ $12$ $15$

A $5$ stage pipelined CPU has the following sequence of stages:IF – instruction fetch from instruction memoryRD – Instruction decode and register readEX – Execute: ...

46.2k views

commented Jul 7, 2020

2 answers

12

GATE CSE 2014 Set 2 | Question: 44
If the associativity of a processor cache is doubled while keeping the capacity and block size unchanged, which one of the following is guaranteed to be NOT affected? Width of tag comparator Width of set index decoder Width of way selection multiplexer Width of processor to main memory data bus

If the associativity of a processor cache is doubled while keeping the capacity and block size unchanged, which one of the following is guaranteed to be NOT affected?Widt...

10.2k views

commented Jul 6, 2020

5 answers

13

GATE CSE 2014 Set 2 | Question: 43
In designing a computer's cache system, the cache block (or cache line) size is an important parameter. Which one of the following statements is correct in this context? A smaller block size implies better spatial locality A smaller block ... size implies a larger cache tag and hence lower cache hit time A smaller block size incurs a lower cache miss penalty

In designing a computer's cache system, the cache block (or cache line) size is an important parameter. Which one of the following statements is correct in this context?A...

21.0k views

commented Jul 6, 2020

9 answers

14

GATE IT 2005 | Question: 52
Let $G$ be a weighted undirected graph and e be an edge with maximum weight in $G$. Suppose there is a minimum weight spanning tree in $G$ containing the edge $e$. Which of the following statements is always TRUE? There exists a cutset in $G$ having ... $e$ cannot be contained in a cycle. All edges in $G$ have the same weight.

Let $G$ be a weighted undirected graph and e be an edge with maximum weight in $G$. Suppose there is a minimum weight spanning tree in $G$ containing the edge $e$. Which ...

20.6k views

commented Jul 2, 2020

2 answers

15

TIFR CSE 2011 | Part B | Question: 21
Let $S=\left \{ x_{1},....,x_{n} \right \}$ be a set of $n$ numbers. Consider the problem of storing the elements of $S$ in an array $A\left [ 1...n \right ]$ ... time. This problem can be solved in $O \left ( n^{2} \right )$ time but not in $O(n\log n)$ time. None of the above.

Let $S=\left \{ x_{1},....,x_{n} \right \}$ be a set of $n$ numbers. Consider the problem of storing the elements of $S$ in an array $A\left [ 1...n \right ]$ such that t...

2.1k views

commented Jul 1, 2020

3 answers

16

TIFR CSE 2010 | Part B | Question: 23
Suppose you are given $n$ numbers and you sort them in descending order as follows: First find the maximum. Remove this element from the list and find the maximum of the remaining elements, remove this element, and so on, until all elements are exhausted. How many comparisons ... $O\left ( n^{1.5} \right )$ but not better.

Suppose you are given $n$ numbers and you sort them in descending order as follows:First find the maximum. Remove this element from the list and find the maximum of the r...

4.9k views

commented Jul 1, 2020

7 answers

17

GATE IT 2008 | Question: 43
If we use Radix Sort to sort $n$ integers in the range $\left (n^{k/2}, n^k \right ]$, for some $k > 0$ which is independent of $n$, the time taken would be? $\Theta(n)$ $\Theta(kn)$ $\Theta(n \log n)$ $\Theta(n^2)$

If we use Radix Sort to sort $n$ integers in the range $\left (n^{k/2}, n^k \right ]$, for some $k 0$ which is independent of $n$, the time taken would be?$\Theta(n)$$\T...

20.7k views

commented Jun 30, 2020

15 answers

18

GATE CSE 2005 | Question: 39
Suppose there are $\lceil \log n \rceil$ sorted lists of $\lfloor n /\log n \rfloor$ elements each. The time complexity of producing a sorted list of all these elements is: (Hint:Use a heap data structure) $O(n \log \log n)$ $\Theta(n \log n)$ $\Omega(n \log n)$ $\Omega\left(n^{3/2}\right)$

Suppose there are $\lceil \log n \rceil$ sorted lists of $\lfloor n /\log n \rfloor$ elements each. The time complexity of producing a sorted list of all these elements i...

26.3k views

commented Jun 30, 2020

9 answers

19

GATE CSE 2003 | Question: 62
In a permutation $a_1\ldots a_n$, of $n$ distinct integers, an inversion is a pair $(a_i, a_j)$ such that $i < j$ and $a_i > a_j.$ What would be the worst case time complexity of the Insertion Sort algorithm, if the inputs are restricted to permutations of $1. . . n$ with at most $n$ inversions? $\Theta(n^2)$ $\Theta(n\log n)$ $\Theta(n^{1.5})$ $\Theta(n)$

In a permutation $a_1\ldots a_n$, of $n$ distinct integers, an inversion is a pair $(a_i, a_j)$ such that $i < j$ and $a_i a_j.$What would be the worst case time complex...

19.8k views

commented Jun 30, 2020

5 answers

20

GATE CSE 1991 | Question: 13
Give an optimal algorithm in pseudo-code for sorting a sequence of $n$ numbers which has only $k$ distinct numbers ($k$ is not known a Priori). Give a brief analysis for the time-complexity of your algorithm.

Give an optimal algorithm in pseudo-code for sorting a sequence of $n$ numbers which has only $k$ distinct numbers ($k$ is not known a Priori). Give a brief analysis for ...

6.6k views

commented Jun 29, 2020

3 answers

21

GATE CSE 1991 | Question: 01,vii
The minimum number of comparisons required to sort $5$ elements is ______

The minimum number of comparisons required to sort $5$ elements is ______

8.7k views

commented Jun 29, 2020

4 answers

22

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.6k views

commented Jun 29, 2020

9 answers

23

GATE IT 2008 | Question: 44
When $n = 2^{2k}$ for some $k \geqslant 0$, the recurrence relation $T(n) = √(2) T(n/2) + √n$, $T(1) = 1$ evaluates to : $√(n) (\log n + 1)$ $√(n) \log n$ $√(n) \log √(n)$ $n \log √n$

When $n = 2^{2k}$ for some $k \geqslant 0$, the recurrence relation$T(n) = √(2) T(n/2) + √n$, $T(1) = 1$evaluates to :$√(n) (\log n + 1)$$√(n) \log n$$√(n) \log...

17.3k views

commented Jun 29, 2020

3 answers

24

GATE CSE 1989 | Question: 13b
Find a solution to the following recurrence equation: $T(n)=\sqrt{n}+T\left(\frac{n}{2}\right)$ $T(1)=1$

Find a solution to the following recurrence equation:$T(n)=\sqrt{n}+T\left(\frac{n}{2}\right)$$T(1)=1$

4.2k views

commented Jun 28, 2020

11 answers

25

GATE CSE 2003 | Question: 69
The following are the starting and ending times of activities $A, B, C, D, E, F, G$ and $H$ ... a room only if the room is reserved for the activity for its entire duration. What is the minimum number of rooms required? $3$ $4$ $5$ $6$

The following are the starting and ending times of activities $A, B, C, D, E, F, G$ and $H$ respectively in chronological order: $“a_s \: b_s \: c_s \: a_e \: d_s \: c_...

14.3k views

commented Jun 27, 2020

1 answer

26

#Algorithms Gate 2005 Question Self Doubt.
Source of the question - here A sink in a directed graph is a vertex i such that there is an edge from every vertex $j ≠ i $ to i and there is no edge from i to any other vertex. A directed graph G with n vertices is represented by ... the diagonal elements in adjacency matrix is = 0. You can take a Graph with 4 vertices and make anyone of them as a sink.

Source of the question - hereA sink in a directed graph is a vertex i such that there is an edge from every vertex $j ≠ i $ to i and there is no edge from i to any othe...

1.2k views

commented Jun 27, 2020

7 answers

27

GATE CSE 2009 | Question: 58
Frames of $1000\text{ bits}$ are sent over a $10^6$ bps duplex link between two hosts. The propagation time is $25ms$. Frames are to be transmitted into this link to maximally pack them in transit (within the link). Let $I$ be ... before starting transmission of the next frame? (Identify the closest choice ignoring the frame processing time) $16ms$ $18ms$ $20ms$ $22ms$

Frames of $1000\text{ bits}$ are sent over a $10^6$ bps duplex link between two hosts. The propagation time is $25ms$. Frames are to be transmitted into this link to maxi...

30.1k views

commented Jun 12, 2020

5 answers

28

GATE IT 2004 | Question: 83
A $20$ $\text{Kbps}$ satellite link has a propagation delay of $400$ $\text{ms}$. The transmitter employs the "go back $n$ $ARQ$" scheme with $n$ set to $10$. Assuming that each frame is $100$ $\text{byte}$ long, what is the maximum data rate possible? $5$ $\text{Kbps}$ $10$ $\text{Kbps}$ $15$ $\text{Kbps}$ $20$ $\text{Kbps}$

A $20$ $\text{Kbps}$ satellite link has a propagation delay of $400$ $\text{ms}$. The transmitter employs the "go back $n$ $ARQ$" scheme with $n$ set to $10$. Assuming th...

11.0k views

commented Jun 11, 2020

6 answers

29

GATE CSE 2016 Set 1 | Question: 53
An IP datagram of size $1000$ $\text{bytes }$arrives at a router. The router has to forward this packet on a link whose MTU (maximum transmission unit) is $100$ $\text{bytes }$. Assume that the size of the IP header is $20$ $\text{bytes }.$ The number of fragments that the IP datagram will be divided into for transmission is________.

An IP datagram of size $1000$ $\text{bytes }$arrives at a router. The router has to forward this packet on a link whose MTU (maximum transmission unit) is $100$ $\text{by...

16.7k views

answered Jun 9, 2020

7 answers

30

GATE CSE 2012 | Question: 45
Consider an instance of TCP's Additive Increase Multiplicative Decrease (AIMD) algorithm where the window size at the start of the slow start phase is $2$ MSS and the threshold at the start of the first transmission is $8$ MSS. Assume that a timeout occurs during ... Find the congestion window size at the end of the tenth transmission. $8$ MSS $14$ MSS $7$ MSS $12$ MSS

Consider an instance of TCP’s Additive Increase Multiplicative Decrease (AIMD) algorithm where the window size at the start of the slow start phase is $2$ MSS and the t...

38.4k views

commented Jun 9, 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