# Questions by VS

1
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 _________.
2
L={ xy | x,y$\epsilon$ (a+b)*, na(x) = nb(y) }
1 vote
3
1 vote
4
Is Most Recently Used (MRU) Page replacement algorithm a 'Stack Algorithm' i.e. it doesn't suffer from Belady's Anomaly ?
5
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
6
L={ (an)m bn | n,m>=1 }
1 vote
7
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 ___
1 vote
8
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 computed it retrieves ... value of n' so that overflow cannot occur ________. (Assume system allocate 4 byte to each stack entry which is sufficient for storing required data.)
9
.......
10
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?
11
A complement of a cyclic graph on 5 vertices , has an Hamiltonian circuit . (True/False)
12
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:
13
14
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)
1 vote
15
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)
1 vote
16
Suppose L = { {} } , N = {1, 2, 3}. Now what does the set N × L contain ?
17
~ $\forall$ x [ P(x) -> (Q(x) v P(x) ) ]
1 vote