Two alternate packages A and B are available for processing a database having 10^k records. Package A requires 0.0001n² time units and package B requires $$10n.\log _{10}^n$$ time units to process n records. What is the smallest value of k for which package B will be preferred over A?

Consider a complete undirected graph with vertex set {0, 1, 2, 3, 4}. Entry W(ij) in the matrix W below is the weight of the edge {i, j}. $$$w = \left( {\matrix{ 0 & 1 & 8 & 1 & 4 \cr 1 & 0 & {12} & 4 & 9 \cr 8 & {12} & 0 & 7 & 3 \cr 1 & 4 & 7 & 0 & 2 \cr 4 & 9 & 3 & 2 & 0 \cr } } \right)$$$ What is the minimum possible weight of a spanning tree T in this graph such that vertex 0 is a leaf node in the tree T?

Consider a complete undirected graph with vertex set {0, 1, 2, 3, 4}. Entry W(ij) in the matrix W below is the weight of the edge {i, j}. $$$w = \left( {\matrix{ 0 & 1 & 8 & 1 & 4 \cr 1 & 0 & {12} & 4 & 9 \cr 8 & {12} & 0 & 7 & 3 \cr 1 & 4 & 7 & 0 & 2 \cr 4 & 9 & 3 & 2 & 0 \cr } } \right)$$$ What is the minimum possible weight of a path P from vertex 1 to vertex 2 in this graph such that P contains at most 3 edges?

The program below uses six temporary variables a, b, c, d, e, f.

a = 1 
b = 10 
c = 20 
d = a + b 
e = c + d 
f = c + e 
b = c + e 
e = b + f 
d = 5 + e 
return d + f

Assuming that all operations take their operands from registers, what is the minimum number of registers needed to execute this program without spilling?

Which data structure in a compiler is used for managing information about variables and their attributes?

The grammar $$S \to aSa\,|\,\,bS\,|\,\,c$$ is

Which languages necessarily need heap allocation in the runtime environment?

Which one of the following is not a client-server application?

One of the header fields in an IP datagram is the Time to Live (TTL) field. Which of the following statements best explains the need for this field?

Suppose computers A and B have IP addresses 10.105.1.113 and 10.105.1.91 respectively and they both use the same net mask N. Which of the values of N given below should not be used if A and B should belong to the same network?

Consider a network with 6 routers R1 to R6 connected with links having weights as shown in the following diagram

All the routers use the distance vector based routing algorithm to update their routing tables. Each router starts with its routing table initialized to contain an entry for each neighbour with the weight of the respective connecting link. After all the routing tables stabilize, how many links in the network will never be used for carrying any data?

Consider a network with 6 routers R1 to R6 connected with links having weights as shown in the following diagram

Suppose the weights of all unused links in the previous question are changed to 2 and the distance vector algorithm is used again until all routing tables stabilize. How many links will now remain unused?

A main memory unit with a capacity of $$4$$ megabytes is built using $$1M \times 1$$-bit $$DRAM$$ chips. Each $$DRAM$$ chip has $$1K$$ rows of cells with $$1K$$ cells in each row. The time taken for a single refresh operation is $$100$$ nanoseconds. The time required to perform one refresh operation on all the cells in the memory unit is

A computer system has an $$L1$$ cache, an $$L2$$ cache, and a main memory unit connected as shown below. The block size in $$L1$$ cache is $$4$$ words. The block size in $$L2$$ cache is $$16$$ words. The memory access times are $$2$$ nanoseconds, $$20$$ nanoseconds and $$200$$ nanoseconds for $$L1$$ cache, $$L2$$ cache and main memory unit respectively.

When there is a miss in both $$L1$$ cache and $$L2$$ cache, first a block is transferred from main memory to $$L2$$ cache, and then a block is transferred from $$L2$$ cache to $$L1$$ cache.
What is the total time taken for these transfers?

A computer system has an $$L1$$ cache, an $$L2$$ cache, and a main memory unit connected as shown below. The block size in $$L1$$ cache is $$4$$ words. The block size in $$L2$$ cache is $$16$$ words. The memory access times are $$2$$ nanoseconds, $$20$$ nanoseconds and $$200$$ nanoseconds for $$L1$$ cache, $$L2$$ cache and main memory unit respectively.

When there is a miss in $$L1$$ cache and a hit in $$L2$$ cache, a block is transferred from $$L2$$ cache to $$L1$$ cache. What is the time taken for this transfer?

A $$5$$-stage pipelined processor has Instruction Fetch $$(IF),$$ Instruction Decode $$(ID),$$ Operand Fetch $$(OF),$$ Perform Operation $$(PO)$$ and Write Operand $$(WO)$$ stages. The $$IF, ID, OF$$ and $$WO$$ stages take $$1$$ clock cycle each for any instruction. The $$PO$$ stage takes $$1$$ clock cycle for $$ADD$$ and $$SUB$$ instructions, $$3$$ clock cycles for $$MUL$$ instruction, and $$6$$ clock cycles for $$DIV$$ instruction respectively. Operand forwarding is used in the pipeline. What is the number of clock cycles needed to execute the following sequence of instructions?

A hash table of length 10 uses open addressing with hash function h(k)=k mod 10, and linear probing. After inserting 6 values into an empty hash table, the table is as shown below How many different insertion sequences of the key values using the same hash function and linear probing will result in the hash table shown above?

The following C function takes a simply-linked list as input argument. It modifies the list by moving the last element to the front of the list and returns the modified list. Some part of the code is left blank.

typedef struct node { 
    int value; 
    struct node *next; 
} Node;
 
Node *move_to_front(Node *head) { 
     Node *p, *q; 
     if ((head = = NULL: || (head->next = = NULL)) return head; 
     q = NULL; p = head; 
     while (p-> next !=NULL) { 
       q=P; 
       p=p->next; 
     } 
     return head; 
} 

Choose the correct alternative to replace the blank line.

Consider a complete undirected graph with vertex set {0,1,2,3,4}. Entry W_ij in the matrix W below is the weight of the edge {i, j} $$$W = \left( {\matrix{ 0 & 1 & 8 & 1 & 4 \cr 1 & 0 & {12} & 4 & 9 \cr 8 & {12} & 0 & 7 & 3 \cr 1 & 4 & 7 & 0 & 2 \cr 4 & 9 & 3 & 2 & 0 \cr } } \right)$$$ What is the minimum possible weight of a spanning tree T in this graph such that vertex 0 is a leaf node in the tree T?

Consider a complete undirected graph with vertex set {0,1,2,3,4}. Entry W_ij in the matrix W below is the weight of the edge {i, j} $$$W = \left( {\matrix{ 0 & 1 & 8 & 1 & 4 \cr 1 & 0 & {12} & 4 & 9 \cr 8 & {12} & 0 & 7 & 3 \cr 1 & 4 & 7 & 0 & 2 \cr 4 & 9 & 3 & 2 & 0 \cr } } \right)$$$ What is the minimum possible weight of a path P from vertex 1 to vertex 2 in this graph such that P contains at most 3 edges?

A hash table of length 10 uses open addressing with hash function h(k)=k mod 10, and linear probing. After inserting 6 values into an empty hash table, the table is as shown below Which one of the following choices gives a possible order in which the key values could have been inserted in the table?

A relational schema for a train reservation database is given below:

Passenger ( pid, pname, age)
Reservation (pid, cass, tid)

Table: Passenger

pid	pname	age
0	'Sachin'	65
1	'Rahul'	66
2	'Sourav'	67
3	'Anil'	69

Table: Reservation

pid	class	tid
0	'AC'	8200
1	'AC'	8201
2	'SC'	8201
5	'AC'	8203
1	'SC'	8204
3	'AC'	8202

What pids are returned by the following SQL query for the above instance of the tables?

SELECT   pid
FROM   Reservation
WHERE   class 'AC' AND 
EXISTS (SELECT * 
FROM Passenger 
WHERE age > 65 
AND Passenger.pid = Reservation.pid);

The following functional dependencies hold for relations R(A, B, C) and S(B, D, E): $$$\eqalign{ & B \to A \cr & A \to C \cr} $$$

The relation R contains 200 tuples and the relation S contains 100 tuples. What is the maximum number of tuples possible in the natural join R $$\Join$$ S?

Which of the following concurrency control protocols ensure both conflict serializability and freedom from deadlock?

I. 2-phase locking
II. Time-stamp ordering

Consider the following schedule for transactions T1, T2 and T3: Which one of the schedules below is the correct serialization of the above?

Consider a B⁺- tree in which the maximum number of keys in a node is 5. What is the minimum number of keys in any non-root node?

$$P$$ is a $$16$$-bit signed integer. The $$2's$$ complement representtation of $$P$$ is $${\left( {F87B} \right)_{16}}$$ . The $$2's$$ complement representation of $$8{}^ * \,P$$ is

The minters expansion of $$f\left( {P,Q,R} \right) = PQ + Q\overline R + P\overline R $$ is

What is the Boolean expression for the output f of the combinational logic circuit of NOR gates given below?

The Boolean expression for the output $$f$$ of the multiplexer shown below is

Suppose the predicate $$F(x,y,t)$$ is used to represent the statements that person $$x$$ can fool person $$y$$ at time $$t$$. Which one of the statements below expresses best the meaning of the formula $$\forall x\exists y\exists t\left( {\neg F\left( {x,y,t} \right)} \right)?$$

Consider a company that assembles computers. The probability of a faulty assembly of any computer is P. The company therefore subjects each computer to a testing process. This gives the correct result for any computer with a probability of q. What is the probability of a computer being declared faulty?

What is the possible number of reflexive relations on a set $$5$$ elements?

Consider the set $$S = \left\{ {1,\,\omega ,\,{\omega ^2}} \right\},$$ where $$\omega $$ and $${{\omega ^2}}$$, are cube roots of unity. If $$ * $$ denotes the multiplication operation, the structure $$\left\{ {S,\, * } \right\}$$ forms

Let $$G$$ $$\,\,\,\,\, = \,\,\,\left( {V,\,\,\,\,\,E} \right)$$ be a graph. Define $$\xi \left( G \right) = \sum\limits_d {{i_d} \times } {\mkern 1mu} d,$$ where $${{i_d}}$$ is the number of vertices of degree $$d$$ in $$G$$. If $$S$$ and $$T$$ are two different trees with $$\xi \left( S \right) = \xi \left( T \right)$$, then

What is the value of $$\mathop {\lim }\limits_{n \to \infty } {\left[ {1 - {1 \over n}} \right]^{2n}}?$$

The degree sequence of a simple graph is the sequence of the degrees of the nodes in the graph in decreasing order. Which of the following sequences can not be the degree sequence of any graph?
$${\rm I}.$$$$\,\,\,\,\,7,6,5,4,4,3,2,1$$
$${\rm I}{\rm I}.$$$$\,\,\,\,\,6,6,6,6,3,3,2,2$$
$${\rm I}{\rm I}{\rm I}.$$$$\,\,\,\,\,7,6,6,4,4,3,2,2$$
$${\rm I}V.$$$$\,\,\,\,\,8,7,7,6,4,2,1,1$$

Consider the following matrix $$A = \left[ {\matrix{ 2 & 3 \cr x & y \cr } } \right]\,\,$$ If the eigen values of $$A$$ are $$4$$ and $$8$$, then

Consider the following matrix $$A = \left[ {\matrix{ 2 & 3 \cr x & y \cr } } \right].$$
If the eigen values of $$A$$ are $$4$$ and $$8$$ then

What is the probability that divisor of $${10^{99}}$$ is a multiple of $${10^{96}}$$ ?

A system uses FIFO policy for page replacement. It has $$4$$ pages frames with no pages loaded to begin with. The system first accesses $$100$$ distinct pages in some order and then accesses the same $$100$$ pages but now in the reverse order. How many page faults will occur?

A system has n resources R₀,.....,R_n-1, and k processes P₀,.....,P_k-1. The implementation of the resource request logic of each process P_i, is as follows:

if (i%2==0) {
  if (i < n) request Ri;
  if (i+2 < n) request Ri+2 ;
}
else {
  if (i < n) request Rn-i;
  if (i+2 < n) request Rn-i-2;
}

In which one of the following situations is a deadlock possible?

Which of the following statements are true?
$${\rm I}.$$ Shortest remaining time first scheduling may cause starvation
$${\rm II}.$$ Preemptive scheduling may cause starvation
$${\rm III}.$$ Round robin is better than $$FCFS$$ in terms of response time

Consider the methods used by processes P1 and P2 for accessing their critical sections whenever needed, as given below. The initial values of shared boolean variables S1 and S2 are randomly assigned.


Which of the following statement describes the properties achieved?

The following program consists of 3 concurrent processes and 3 binary semaphores. The semaphores are initialized as S0=1, S1=0, S2=0. How many times will process P0 print '0'?

Which languages necessarily need heap allocation in the runtime environment?

What does the following program print?

#include < stdio.h >
void f (int *p, int *q) {
     p = q;
    *p = 2;
}
int i = 0, j = 1;
int main ( ){
     f(&i, &j);
     printf ("%d %d \ n", i, j);
     return 0;
}

The Cyclomatic complexity of each of the module $$A$$ & $$B$$ shown below is $$10.$$ What is the cyclomatic complexity of the sequential integration show on the right hand side?

What is the appropriate pairing of items in the two columns using listing various activities encountered in a software use cycle?

The following program is to be tested for statement coverage:
begin
if $$\left( {a = \,\, = b} \right)\,\,\left\{ {S1;\,\,exit;} \right\}$$
else if $$\left( {c = \,\, = d} \right)\,\,\left\{ {S2;} \right\}$$
else $$\left\{ {S3;\,\,exit;} \right\}$$
$$S4;$$
end

The test cases $${T_1},\,{T_2},\,{T_3}\,\,\& \,{T_4}$$ given below are expressed in terms of the properties satisfied by the values of variables $$a, b, c$$ and $$d.$$ The exact values are not given.
$${T_1}:\,a,\,b,\,c\,\& \,d$$ are all equal
$${T_2}:\,a,\,b,\,c\,\& \,d$$ are all distinct
$${T_3}:\,a = b\,\,\,\& \,\,\,\,c\,!\, = \,d$$
$${T_4}:\,a! = b\,\,\,\& \,\,\,\,c\, = \,d$$

Which of the test suites given below ensures coverage of statements $${S_1},\,{S_2},\,{S_3}\,\,\& \,{S_4}$$ ?

Let $${L_1}$$ recursive language. Let $${L_2}$$ and $${L_3}$$ be languages that are recursively enumerable but not recursive. Which of the following statement is not necessarily true?

Let $$L = \left\{ {w \in {{\left( {0 + 1} \right)}^ * }\left| {\,w} \right.} \right.$$ has even number of $$\,\left. {1's} \right\},$$ i.e $$L$$ is the set of all bit strings with even number of $$1's.$$ which one of rhe regular expression below represents $$L.$$

Let $$w$$ be any string of length $$n$$ in $${\left\{ {0,1} \right\}^ * }$$. Let $$L$$ be the set of all substrings of $$w.$$ What is the minimum number of states in a non-deterministic finite automation that accepts $$L$$?

Consider the languages $$$\eqalign{ & {L_1} = \left\{ {{0^i}{1^j}\,\left| {i \ne j} \right.} \right\},\,{L_2} = \left\{ {{0^i}{1^j}\,\left| {i = j} \right.} \right\}, \cr & {L_3} = \left\{ {{0^i}{1^j}\,\left| {i = 2j + 1} \right.} \right\}, \cr & {L_4} = \left\{ {{0^i}{1^j}\,\left| {i \ne 2j} \right.} \right\}, \cr} $$$