Questions by VS - GATE Overflow

+2 votes

2 answers

1

Merge Sort
Let A,B,C,D,E are sorted sequences having length 70,74,80,85,102 respectively.They are merged into a single sequence by merging together two sequences at a time.The minimum number of comparisons that will be needed by algorithm in best case for going merging is _________.

asked Jan 31, 2018 in Algorithms | 444 views

+1 vote

1 answer

2

Identify class of the language
L={ xy | x,y$\epsilon$ (a+b)*, na(x) = nb(y) }

asked Jan 24, 2018 in Theory of Computation | 111 views

+1 vote

0 answers

3

Aptitude

asked Jan 24, 2018 in Numerical Ability | 101 views

+1 vote

0 answers

4

Stack algorithm
Is Most Recently Used (MRU) Page replacement algorithm a 'Stack Algorithm' i.e. it doesn't suffer from Belady's Anomaly ?

asked Jan 23, 2018 in Operating System | 160 views

+3 votes

2 answers

5

#Conflict Misses
A byte addressable computer has a small data cache capable of holding 16 32-bit words. Each cache block consist of four 32 bits words. For the following sequence of main memory addresses (in hexadecimal). The conflict miss if 2-way set associative LRU cache is used is ________. 100, 108, 114, 1C7, 128, 1B5, 100, 108, 1C7

asked Jan 21, 2018 in CO and Architecture | 303 views

+3 votes

0 answers

6

CSL or not ?
L={ (an)m bn | n,m>=1 }

asked Jan 20, 2018 in Theory of Computation | 67 views

+1 vote

1 answer

7

Resource Allocation
Consider a scenario where 3 processes P1, P2 and P3 are sharing x resources of the same type. The maximum need of the three processes is 4, 8, 6. It is also known that the maximum combined need of both processes P1 and P2 at a time is 9 and they always execute only in combined manner. Then the value of x is ___

asked Jan 20, 2018 in Operating System | 586 views

+1 vote

0 answers

8

Dynamic programming
Consider the following recursive function which is used by dynamic programming: T(n)= 0 ;if n<1 = 1;if n=1 =T(n-1)+T(n-2)+1 ;if n>1 Assume for every function call T(i) it checks the table first, if its value is already ... of n' so that overflow cannot occur ________. (Assume system allocate 4 byte to each stack entry which is sufficient for storing required data.)

asked Jan 20, 2018 in Algorithms | 199 views

0 votes

0 answers

9

Min. #Tables
.......

asked Jan 17, 2018 in Databases | 154 views

+2 votes

0 answers

10

Weighted undirected graph
Consider a Weighted undirected graph connected with 'V' vertices and 'E' edges.What is the worst case time complexity to check if 2 particular vertices 'x' and 'y' are present in the graph, if present then calculate the minimum distance between them?

asked Jan 17, 2018 in Algorithms | 291 views

+2 votes

1 answer

11

Hamiltonian Graph
A complement of a cyclic graph on 5 vertices , has an Hamiltonian circuit . (True/False)

asked Jan 16, 2018 in Mathematical Logic | 282 views

+2 votes

0 answers

12

DAG_#Nodes
Consider the basic block given below: b=b+c d=b+d b=b-d e=d+b The minimum number of nodes and edges present in the DAG representation of the above basic block respectively are:

asked Jan 16, 2018 in Compiler Design | 436 views

+4 votes

1 answer

13

Theads
True/False : 1)Several threads can share same physical address space. 2)Several threads can share same virtual address space.

asked Jan 16, 2018 in Operating System | 352 views

+4 votes

1 answer

14

Balanced binary search tree
A balanced binary search tree of n nodes,the number of steps needed to find and remove the 9th largest element in the worst case? (Please mention the algorithm followed)

asked Jan 15, 2018 in Algorithms | 219 views

+1 vote

0 answers

15

Logical shift
a) Shifting a Unsigned integer right by one bit, and filling from the left with 0, is always equivalent to dividing by 2. (True/False) b) Shifting a Unsigned integer left by one bit, and filling from the right with 0, is always equivalent to multiplying by 2. (True/False)

asked Jan 13, 2018 in CO and Architecture | 120 views

+1 vote

1 answer

16

Cartesian Product
Suppose L = { {} } , N = {1, 2, 3}. Now what does the set N × L contain ?

asked Jan 13, 2018 in Set Theory & Algebra | 85 views

+2 votes

1 answer

17

Contingency or Not ?
~ $\forall$ x [ P(x) -> (Q(x) v P(x) ) ]

asked Jan 11, 2018 in Mathematical Logic | 157 views

+1 vote

1 answer

18

Starvation
I am confused with what exactly Starvation mean ? AFAIK Considering Process Scheduling eg SRTF and SJF , Starvation can be considered when some process is getting preempted by other high priority processes and hence not getting a chance to execute on CPU and ... do we consider a Single processor system or a Multiprocessor i.e. when we have multiple processing cores or CPUs available?

asked Jan 9, 2018 in Operating System | 125 views

+2 votes

0 answers

19

CSMA/CD
In standard ethernet with transmission rate of 20 Mbps, the length of the cables is 2500 m and the size of frame is 512 bits. The propagation speed of a signal in a cable is 2 × 108 m/s. The percentage of the time channel is idle or not used by a station is _________ (in approximate integer value).

asked Jan 6, 2018 in Computer Networks | 389 views

+3 votes

0 answers

20

TCP Congestion Control
Consider an instance of TCP’s Additive Increase Multiplicative Decrease (AIMD) algorithm where the window size at the start of slow start phase is 2 KB and the threshold at the start of first transmission is 24 KB. Assume that 3 duplicate ACK are received during the 5th transmission what is the congestion window size at the end of 10th transmission?

asked Jan 6, 2018 in Computer Networks | 299 views

+2 votes

2 answers

21

BST(Test Series)
Consider a Binary Search Tree is created using element 1 to n in following order: 3, 2, 1, 6, 5, 4, 9, 8, 7, 12, 11, 10, ....., n – 3, n – 4, n – 5, n – 2, n – 1, n What is the worst time complexity of searching a number in the Binary Search Tree?

asked Jan 3, 2018 in DS | 296 views

+2 votes

0 answers

22

Asymptotic-notations
Let f(n)=O(n),g(n)=O(n) and h(n)=Ѳ(n). Then [f(n).g(n)]+h(n) is: Ω (n) O (n) Ѳ (n) None of these

asked Jan 3, 2018 in Algorithms | 66 views

+2 votes

1 answer

23

Flooding
Flooding always guaranteed to send packet from source to destination with minimum number of hops. (True / False)

asked Jan 1, 2018 in Computer Networks | 341 views

+10 votes

4 answers

24

Hashing (Test Series)
Consider an initially empty hash table of length 10. Following set of keys are inserted using open addressing with hash function h(k) = k mod 10 and linear probing. 0 1 91 2 2 3 13 4 24 5 12 6 62 7 77 8 82 9 The number of different insertion sequence of the key values using the given hash function and linear probing will result in the hash table shown in above __________.

asked Jan 1, 2018 in DS | 1.2k views

+2 votes

0 answers

25

Identify class of language
L={ (anbn)* | n>0 }

asked Dec 28, 2017 in Theory of Computation | 118 views

+1 vote

1 answer

26

Distributed Lattice
Is the following lattice distributed ?

asked Dec 28, 2017 in Set Theory & Algebra | 325 views

+1 vote

0 answers

27

Stack
Consider a stack and we wish to perform an operation StackDelete() in which we wish to delete all the elements of the stack .What is the worst case time complexity of doing this if stack is implemented: 1) Using an array 2)Using a Linked list

asked Dec 26, 2017 in Programming | 157 views

+2 votes

2 answers

28

DCFG grammar
Can a DCFG grammar be Ambiguous? If so please provide an example.

asked Dec 24, 2017 in Theory of Computation | 489 views

+2 votes

0 answers

29

LL(k)
I know that LL(1) grammar can have No left factoring ,No Left recursion and No Ambiguity. Is same thing true for LL(k) as well i.e. LL(k) which is reading k symbols at a time from input string. Does LL(k) grammar can have No left factoring ,No Left recursion and No Ambiguity ?

asked Dec 24, 2017 in Compiler Design | 727 views

+1 vote

1 answer

30

Go back n
Consider a network connecting two systems, ‘A’ and ‘B’ located 6000 km apart. The propagation speed of media is 2 × 106 mps. It is needed to design a Go-Back-7 sliding window protocol for this network. The average packet size is 107 bits. If network used as its full capacity, then the bandwidth of network is__________ Mbps

asked Dec 23, 2017 in Computer Networks | 329 views