Consider the following array of elements.

$$\,\,\,\,\,\,\,\,$$$$〈89, 19, 50, 17, 12, 15, 2, 5, 7, 11, 6, 9, 100〉$$

The minimum number of interchanges needed to convert it into a max-heap is

Assume that a mergesort algorithm in the worst case takes $$30$$ seconds for an input of size $$64.$$ Which of the following most closely approximates the maximum input size of a problem that can be solved in $$6$$ minutes?

Let $$f\left( n \right) = n$$ and $$g\left( n \right) = {n^{\left( {1 + \sin \,\,n} \right)}},$$ where $$n$$ is a positive integer. Which of the following statements is/are correct?

$$\eqalign{ & \,\,\,\,\,\,\,{\rm I}.\,\,\,\,\,\,\,f\left( n \right) = O\left( {g\left( n \right)} \right) \cr & \,\,\,\,\,{\rm I}{\rm I}.\,\,\,\,\,\,\,f\left( n \right) = \Omega \left( {g\left( n \right)} \right) \cr} $$

Consider the equality $$\sum\limits_{i = 0}^n {{i^3}} = X$$ and the following choices for $$X$$
$$\eqalign{ & \,\,\,\,\,\,\,{\rm I}.\,\,\,\,\,\,\Theta \left( {{n^4}} \right) \cr & \,\,\,\,\,{\rm I}{\rm I}.\,\,\,\,\,\,\Theta \left( {{n^5}} \right) \cr & \,\,\,{\rm I}{\rm I}{\rm I}.\,\,\,\,\,\,O\left( {{n^5}} \right) \cr & \,\,\,{\rm I}V.\,\,\,\,\,\,\Omega \left( {{n^3}} \right) \cr} $$
The equality above remains correct if $$𝑋$$ is replaced by

Consider the following grammar $$G$$

$$\eqalign{ & \,\,\,\,\,\,\,S \to \,\,\,\,\,\,\,F|H \cr & \,\,\,\,\,\,F \to \,\,\,\,\,\,\,p|c \cr & \,\,\,\,\,\,H \to \,\,\,\,\,\,\,d|c \cr} $$

where $$S, F$$ and $$H$$ are non-terminal symbols, $$p, d,$$ and $$c$$ are terminal symbols. Which of the following statement(s) is/are correct?

$$\,\,\,\,\,\,\,S1.\,\,\,\,\,\,\,LL\left( 1 \right)\,\,$$ can parse all strings that are generated using grammar $$G$$
$$\,\,\,\,\,\,\,S2.\,\,\,\,\,\,\,LR\left( 1 \right)\,\,$$ can parse all strings that are generated using grammar $$G$$

Among simple $$LR (SLR) ,$$ canonical $$LR,$$ and look-ahead $$LR$$ $$(LALR),$$ which of the following pairs identify the method that is very easy to implement and the method that is the most powerful , in that order?

Two hosts are connected via a packet switch with $${10^7}$$ bits per second links. Each link has a propagation delay of $$20$$ micro-seconds. The switch begins forwarding a packet $$35$$ microseconds after it receives the same. If $$10000$$ bits of data are to be transmitted between the two hosts using a packet size of $$5000$$ bits, the time elapsed between the transmission of the first bit of data and the reception of the last bit of the data in microseconds is____________.

Consider a CSMA/CD network that transmits data at a rate of 100 Mbps (10⁸ bits second) over a 1 km(kilometer) cable with no repeaters. If the minimum frame size required for this network is 1250 bytes, what is the signal speed (km/sec) in the cable?

Consider a network connected two systems located 8000 kilometers apart. The bandwidth of the network is 500 × 10⁶ bits per second. The propagation speed of the media is 4 × 10⁶ meters per second. It is needed to design a Go-Back-N sliding window protocol for this network. The average packet size is 10⁷ bits. The network is to be used to its full capacity. Assume that processing delays at nodes are negligible. Then the minimum size in bits of the sequence number field has to be ___________.

In the network 200.20.11.144/27, the fourth octet (in decimal) of the last IP address of the network which can be assigned to a host is ________.

Consider the following statements.

I. TCP connections are full duplex
II. TCP has no option for selective acknowledgment
III. TCP connections are message streams

Consider the following code sequence having five instructions $${I_1}$$ to $${I_5}$$. Each of these instructions has the following format.

$$\,\,\,\,\,\,\,\,\,\,\,\,\,\,OP\,\,Ri,\,\,Rj,\,\,Rk$$

where operation $$OP$$ is performed on contents of registers $$Rj$$ and $$Rk$$ and the result is stored in register $$Ri.$$

$$\eqalign{ & \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,{I_1}:ADD\,\,\,R1,\,R2,\,R3 \cr & \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,{I_2}:MUL\,\,R7,\,R1,\,R3 \cr & \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,{I_3}:SUB\,\,\,\,R4,\,R1,\,R5 \cr & \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,{I_4}:ADD\,\,\,R3,\,R2,\,R4 \cr & \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,{I_5}:MUL\,\,\,R7,\,R8,\,R9 \cr} $$

Consider the following three statements.

$$\,\,\,\,\,\,S1:\,\,$$ There is an anti-dependence between instructions $${L_2}$$ and $${L_5}$$
$$\,\,\,\,\,\,S2:\,\,$$ There is an anti-dependence between instructions $${L_2}$$ and $${L_4}$$
$$\,\,\,\,\,\,S3:\,\,$$ Within an instruction pipeline an anti-dependence always creates one or more stalls

Which one of above statements is/are correct?

Consider a machine with a byte addressable main memory of $${2^{20}}$$ bytes, block size of $$16$$ bytes and a direct mapped cache having $${2^{12}}$$ cache lines. Let the addresses of two consecutive bytes in main memory be $${\left( {E201F} \right)_{16}}$$ and $${\left( {E2020} \right)_{16}}$$. What are the tag and cache line address (in $$hex$$) for main memory address $${\left( {E201F} \right)_{16}}$$?

Consider the following reservation table for a pipeline having three stages $${S_1},{S_2}$$ and $${S_3}.$$

The minimum average latency $$(MAL)$$ is ________.

The result evaluating the postfix expression $$10\,\,5\, + 60$$ $$\,\,6/\, * \,8\, - $$ is

While inserting the elements $$71, 65, 84, 69, 67, 83$$ in an empty binary search tree $$(BST)$$ in the sequence shown, the element in the lowest level is

Let $$G$$ be a connected undirected graph of $$100$$ vertices and $$300$$ edges. The weight of a minimum spanning tree of $$G$$ is $$500.$$ When the weight of each edge of $$G$$ is increased by five, the weight of a minimum spanning tree becomes ________.

Consider a binary tree $$T$$ that has $$200$$ leaf nodes. Then, the number of nodes in $$T$$ that have exactly two children are ________.

Given a hash table $$𝑇$$ with $$25$$ slots that stores $$2000$$ elements, the load factor $$\alpha $$ for $$𝑇$$ is ____________ .

Consider the following relation
$$\,\,\,\,\,\,\,\,$$ Cinema(theater, address, capacity)
Which of the following options will be needed at the end of the $$SQL$$ query

$$\,\,\,\,\,\,\,\,$$ SELECT $$P1.$$address
$$\,\,\,\,\,\,\,\,$$ FROM Cinema $$P1$$

such that it always finds the addresses of theaters with maximum capacity?

Consider the following partial Schedule S involving two transactions $$T1$$ and $$T2.$$ Only the read and the write operations have been shown. The read operation on data item $$P$$ is denoted by read$$(P)$$ and the write operation on data item $$P$$ is denoted by write $$(P).$$

Suppose that the transaction $$T1$$ fails immediately after time instance $$9.$$ Which one of the following statements is correct?

Consider a B⁺ tree in which the search key is 12 bytes long, block size is 1024 bytes, record pointer is 10 bytes long and block pointer is 8 bytes long. The maximum number of keys that can be accommodated in each non-leaf node of the tree is ____.

Consider the relation $$X\left( {P,Q,R,S,T,U} \right)$$ with the following set of functional dependencies
$$\eqalign{ & F = \left\{ \, \right. \cr & \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\left\{ {P,R} \right\} \to \left\{ {S,T} \right\}, \cr & \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\left\{ {P,S,U} \right\} \to \left\{ {Q,R} \right\} \cr & \,\,\,\,\,\,\,\,\,\,\left. \, \right\} \cr} $$
Which of the following is the trivial functional dependency in $${F^ + },$$ where $${F^ + }$$ is closure of $$f$$ ?

Given the function $$F = P′ + QR,$$ where $$F$$ is a function in three Boolean variables $$P,Q$$ and $$R$$ and $$P'=!P,$$ consider the following statements.

$$\eqalign{ & \,\,\,\,\,\,\,\,\,\,\,\,\,\,\left( {S1} \right)\,\,\,\,F = \sum {\left( {4,5,6} \right)} \cr & \,\,\,\,\,\,\,\,\,\,\,\,\,\,\left( {S2} \right)\,\,\,\,F = \sum {\left( {0,1,2,3,7} \right)} \cr & \,\,\,\,\,\,\,\,\,\,\,\,\,\,\left( {S3} \right)\,\,\,\,F = \sum {\Pi \left( {4,5,6} \right)} \cr & \,\,\,\,\,\,\,\,\,\,\,\,\,\,\left( {S4} \right)\,\,\,\,F = \sum {\Pi \left( {0,1,2,3,7} \right)} \cr} $$

Which of the following is true?

Consider the equation $${\left( {43} \right)_x} = {\left( {y3} \right)_8}$$ where $$x$$ and $$y$$ are unknown. The number of possible solutions is ______________

The total number of prime implicants of the function
$$f\left( {w,x,y,z} \right) = \sum {\left( {0,2,4,5,6,10} \right)} $$ _________________.

Let $$ \ne $$ be a binary operator defined as $$X \ne Y = X' + Y'$$ where $$𝑋$$ and $$𝑌$$ are Boolean variables. Consider the following two statements. $$$\eqalign{ & \left( {S1} \right)\,\,\,\,\,\,\,\left( {P \ne Q} \right) \ne R = P \ne \left( {Q \ne R} \right) \cr & \left( {S2} \right)\,\,\,\,\,\,\,Q \ne R = R \ne Q \cr} $$$

Which of the following is/are true for the Boolean variables $$𝑃, 𝑄$$ and $$𝑅$$?

In a room there are only two types of people, namely Type $$1$$ and Type $$2.$$ Type $$1$$ people always tell the truth and Type $$2$$ people always lie. You give a fair coin to a person in that room, without knowing which type he is from and tell him to toss it and hide the result from you till you ask for it. Upon asking, the person replies the following “The result of the toss is head if and only if I am telling the truth.”

Which of the following options is correct?

Let $$R$$ be a relation on the set of ordered pairs of positive integers such that $$\left( {\left( {p,q} \right),\left( {r,s} \right)} \right) \in R$$ if and only if $$p - s = q - r.$$ Which one of the following is true about $$R$$?

In the given matrix $$\left[ {\matrix{ 1 & { - 1} & 2 \cr 0 & 1 & 0 \cr 1 & 2 & 1 \cr } } \right],$$ one of the eigenvalues is $$1.$$ The eigen vectors corresponding to the eigen value $$1$$ are

A function $$f(x)$$ is linear and has a value of $$29$$ at $$x=-2$$ and $$39$$ at $$x=3.$$ Find its value at $$x=5.$$

If for non-zero $$x,$$ $$af\left( x \right) + bf\left( {{1 \over x}} \right) = {1 \over x} - 25$$
where $$a \ne b$$ then $$\int\limits_1^2 {f\left( x \right)dx} \,$$ is

The value of $$\mathop {\lim }\limits_{x \to \alpha } {\left( {1 + {x^2}} \right)^{{e^{ - x}}}}\,\,$$ is

Choose the most appropriate equation for the function drawn as a thick line, in the plot below.

Suppose $${X_i}$$ for $$i=1,2,3$$ are independent and identically distributed random variables whose probability mass functions are $$\,\,\Pr \left[ {{X_i} = 0} \right] = \Pr \left[ {{X_i} = 1} \right] = 1/2\,\,$$ for $$i=1,2,3.$$ Define another random variable $$\,\,Y = {X_1}{X_2} \oplus {X_3},\,\,$$ where $$ \oplus $$ denotes $$XOR.$$ Then $$\Pr \left[ {Y = 0\left| {{X_3} = 0} \right.} \right]$$ =________.

If the following system has non - trivial solution $$$px+qy+rz=0$$$ $$$qx+ry+pz=0$$$ $$$rx+py+qz=0$$$

Then which one of the following Options is TRUE?

Suppose $$𝑈$$ is the power set of the set $$S = \left\{ {1,2,3,4,5,6,} \right\}$$. For any $$T \in U,$$ let $$\left| T \right|$$ denote the number of elements in $$𝑇$$ and $$T'$$ denote the complement of $$𝑇.$$ For any $$T,R \in U,$$ let $$T\backslash R$$ be the set of all elements in $$𝑇$$ which are not in $$𝑅.$$ Which one of the following is true?

The number of $$4$$ digit numbers having their digits in non-decreasing order (from left to right) constructed by using the digits belonging to the set $${1, 2, 3}$$ is____________.

Consider the following policies for preventing deadlock in a system with mutually exclusive resources.

$$\,\,\,\,\,\,\,{\rm I}.$$ $$\,\,\,\,\,\,$$ Processes should acquire all their resources at the beginning of execution. If
$$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$$ any resource is not available, all resources acquired so far are released
$$\,\,\,\,\,{\rm II}.$$ $$\,\,\,\,\,\,$$ The resources are numbered uniquely, and processes are allowed to request
$$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$$ for resources only in increasing resource numbers
$$\,\,\,{\rm III}.$$ $$\,\,\,\,\,\,$$ The resources are numbered uniquely, and processes are allowed to request
$$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$$ for resources only in decreasing resource numbers
$$\,\,\,{\rm IV}.$$ $$\,\,\,\,\,\,$$ The resources are numbered uniquely. A process is allowed to request only
$$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$$ for a resource with resource number larger than its currently held resources

Which of the above policies can be used for preventing deadlock?

For the processes listed in the following table, which of the following scheduling schemes will give the lowest average turnaround time?

Process	Arrival Time	Processing Time
A	0	3
B	1	6
D	4	4
E	6	2

The maximum number of processes that can be in $$Ready$$ state for a computer system with $$n$$ $$CPUs$$ is

Consider the following C program segment.

#include < stdio.h >
int main()
{
    char s1[7] = "1234", *p;
    p = s1 + 2;
   *p = ‘0’;
    printf("%s", s1);
}

What will be printed by the program?

Consider a software program that is artificially seeded with $$100$$ faults. While testing this program, $$159$$ faults are detected, out of which $$75$$ faults are from those artificially seeded faults. Assuming that both real and seeded faults are of same nature and have same distribution, the estimated number of undetected real faults is ____________.

Consider three software items: Program-$$X,$$ Control Flow Diagram of Program-$$Y$$ and Control Flow Diagram of Program-$$Z$$ as shown below

The values of McCabe’s Cyclomatic complexity of Program-$$X,$$ Program-$$Y,$$ and Program-$$Z$$ respectively are

Consider a software project with the following information domain characteristics for calculation of function point metric.

Number of external inputs $$\left( {\rm I} \right) = 30$$
Number of external outputs $$\left( O \right) = 60$$
Number of external inquiries $$\left( E \right) = 23$$
Number of files $$(F) = 08$$
Number of external interfaces $$(N) = 02$$

It is given that the complexity weighting factors for $$I, O, E, F$$ and $$N$$ are $$4, 5, 4, 10$$ and $$7,$$ respectively. It is also given that, out of fourteen value adjustment factors that influence the development effort, four factors are not applicable, each of the other four factors have value $$3,$$ and each of the remaining factors have value $$4.$ The computed value of function point metric is _____________.

Let $$L$$ be the language represented by the regular expression $$\sum {^ * 0011\sum {^ * } } $$ where $$\sum { = \left\{ {0,1} \right\}} .$$ What is the minimum number of states in a $$DFA$$ that recognizes $$\overline L $$ (complement of $$L$$)?

Language $${L_1}$$ is polynomial time reducible to language $${L_2}$$ . Language $${L_3}$$ is polynomial time reducible to $${L_2}$$ , which in turn is polynomial time reducible to language $${L_4}$$ . Which of the following is/are true?

$$\,\,\,\,\,\,\,\,\,\,\,\,\,\,{\rm I}.\,\,\,\,$$ if $$\,\,\,{L_4} \in P,$$ then $$\,\,\,{L_2} \in P$$
$$\,\,\,\,\,\,\,\,\,\,\,\,{\rm I}{\rm I}.\,\,\,\,$$ if $$\,\,\,{L_1} \in P$$ or $$\,\,\,{L_3} \in P,$$ then $$\,\,\,{L_2} \in P$$
$$\,\,\,\,\,\,\,\,\,\,{\rm I}{\rm I}{\rm I}.\,\,\,\,$$ if $$\,\,\,{L_1} \in P,$$ and only $$\,\,\,{L_3} \in P$$
$$\,\,\,\,\,\,\,\,\,\,{\rm I}V.\,\,\,\,$$ if $$\,\,\,{L_4} \in P,$$ then $$\,\,\,{L_1} \in P$$ and $$\,\,\,{L_3} \in P$$

Which of the following languages are context-free? $$$\eqalign{ & {L_1} = \left\{ {{a^m}{b^n}{a^n}{b^m}|m,n \ge 1} \right\} \cr & {L_2} = \left\{ {{a^m}{b^n}{a^m}{b^n}|m,n \ge 1} \right\} \cr & {L_3} = \left\{ {{a^m}{b^n}|m = 2n + 1} \right\} \cr} $$$

In a web server, ten WebPages are stored with the URLs of the form
http://www.yourname.com/$$var$$.html; where, $$var$$ is a different number from $$1$$ to $$10$$ for each Webpage. Suppose, the client stores the Webpage with $$var = 1$$ (say $$W1$$) in local machine, edits and then tests. Rest of the WebPages remains on the web server. $$W1$$ contains several relative URLs of the form “$$var$$.html” referring to the other WebPages. Which one of the following statements needs to be added in $$W1,$$ so that all the relative URLs in $$W1$$ refer to the appropriate WebPages on the web server?