GATE 2014 CSE & IT

A canonical set of items is given below $$\eqalign{ & S \to L. > R \cr & Q \to R. \cr} $$ On input symbol < the set has

Let the size of congestion window of a TCP connection be 32 KB when a timeout occurs. The round trip time of the connection is 100 msec and the maximum segment size used is 2 KB. T...

Consider two processors ܲ$${P_1}$$ and $${P_2}$$ executing the same instruction set. Assume that under identical conditions, for the same input, a program running on $${P_2}$$ take...

The function $$f(x) =$$ $$x$$ $$sinx$$ satisfies the following equation: $$f$$"$$\left( x \right) + f\left( x \right) + t\,\cos \,x\,\, = \,\,0$$. The value of $$t$$ is ______ .

Which one of the following are used to generate a message digest by the network security protocols? (P) RSA (Q) SHA-1 (R) DES (S) MD5

Consider the following three statements about link state and distance vector routing protocols, for a large network with 500 network nodes and 4000 links [S1] The computational ove...

A pennant is a sequence of numbers, each number being 1 or 2. An n-pennant is a sequence of numbers with sum equal to n. For example, (1,1,2) is a 4-pennant. The set of all possibl...

Match the following: $$1)$$ Waterfall model $$2)$$ Evolutionary model $$3)$$ Component-based software engineering $$4)$$ Spiral development $$a)$$ Specifications can be developed i...

Consider an undirectional graph $$G$$ where self-loops are not allowed. The vertex set of $$G$$ is $$\left\{ {\left( {i,j} \right):\,1 \le i \le 12,\,1 \le j \le 12} \right\}.$$ Th...

The maximum number of edges in a bipartite graph on $$12$$ vertices is _________.

Given the following statements: S1: A foreign key declaration can always be replaced by an equivalent check assertion in SQL. S2: Given the table R(a,b,c) where a and b together fo...

Consider a hash table with 9 slots. The hash function is h(k) = k mod 9. The collisions are resolved by chaining. The following 9 keys are inserted in the order: 5, 28, 19, 15, 20,...

Consider a selective repeat sliding window protocol that uses a frame size of 1 KB to send data on a 1.5 Mbps link with a one-way latency of 50 msec. To achieve a link utilization...

Given the following two statements: $$S1:$$ Every table with two single-valued attributes is in $$1NF, 2NF, 3NF$$ and $$BCNF.$$ $$S2:$$ $$AB \to C,\,\,D \to E,\,\,E \to C$$ is a mi...

Consider the following Boolean expression for $$F:$$ $$F\left( {P,\,Q,\,R,\,S} \right) = PQ + \overline P QR + \overline P Q\overline R S.$$ The minimal sum-of-products form of $$F...

Consider the following program in C language: #include < stdio.h > main() { int i; int *pi = &i; scanf("%d", pi); printf("%d\n", i + 5); } Which one of the following statements is...

Let G be a graph with n vertices and m edges. What is the tightest upper bound on the running time of Depth First Search on G, when G is represented as an adjacency matrix?

Consider a $$6$$-stage instruction pipeline, where all stages are perfectly balanced. Assume that there is no cycle-time overhead of pipelining. When an application is executing on...

Four fair six-sided dice are rolled. The probability that the sum of the results being 22 is X/1296. The value of X is__________

Consider a rooted n node binary tree represented using pointers. The best upper bound on the time required to determine the number of subtrees having exactly 4 nodes O(n a Log b n...

The base (or radix) of the number system such that the following equation holds is __________ $${{312} \over {20}} = 13.1$$

Let the function $$f\left( \theta \right) = \left| {\matrix{ {\sin \,\theta } & {\cos \,\theta } & {\tan \,\theta } \cr {\sin \left( {{\pi \over 6}} \right)} & {\cos \left( {{\pi \...

The minimum number of comparisons required to find the minimum and the maximum of 100 numbers is ________

Consider the following pseudo code. What is the total number of multiplications to be performed? D = 2 for i = 1 to n do for j = i to n do for k = j + 1 to n do D = D * 3

Suppose a polynomial time algorithm is discovered that correctly computes the largest clique in a given graph. In this scenario, which one of the following represents the correct V...

Let P be a QuickSort Program to sort numbers in ascending order using the first element as pivot. Let t 1 and t 2 be the number of comparisons made by P for the inputs {1, 2, 3, 4,...

Which one of the following is FALSE?

The value of the dot product of the eigenvectors corresponding to any pair of different eigen values of a 4-by-4 symmetric positive definite matrix is ____________.

Which one of the following is FALSE?

Which one of the following propositional logic formulas is TRUE when exactly two of $$p, q,$$ and $$r$$ are TRUE ?

Let $$G = \left( {V,E} \right)$$ be a directed graph where $$V$$ is the set of vertices and $$E$$ the set of edges. Then which one of the following graphs has the same strongly con...

Consider the following C functions in which size is the number of elements in the array E: int MyX(int *E, unsigned int size){ int Y = 0; int Z; int i,j,k; for(i = 0; i < size; i++...

Suppose you break a stick of unit length at a point chosen uniformaly at random. Then the expected length of the shorter stick is __________________.

Given the following schema: employees(emp-id, first-name, last-name, hire-date, dept-id, salary) departments(dept-id, dept-name, manager-id, location-id) You want to display the la...

An access sequence of cache block addresses is of length $$N$$ and contains $$n$$ unique block address. The number of unique block addresses between two consecutive accesses to the...

Consider the following set of processes that need to be scheduled on a single $$CPU.$$ All the times are given in milliseconds. Process Name Arrival Time Execution Time A 0 6 B 3 2...

There are 5 bags labeled 1 to 5. All the coins in given bag have the same weight. Some bags have coins of weight 10 gm, other have coins of weight 11 gm. $${\rm I}$$ pick 1, 2, 4,...

Consider the following four schedules due to three transactions (indicated by the subscript) using read and write on a data item x, denoted by r(x) and w(x) respectively. Which one...

Consider the relation schema $$R = \left( {E,\,F,\,G,\,H,\,I,\,J,\,K,L,\,M,\,N} \right)$$ and the set of functional dependencies $$\left\{ {\left\{ {E,F} \right\} \to \left\{ G \ri...

A function $$f(x)$$ is continuous in the interval $$\left[ {0,2} \right]$$. It is known that $$f(0)$$ $$=$$ $$f(2)$$ $$= -1$$ and $$f(1)$$ $$ = 1$$. Which one of the following stat...

Consider the following system of equations: 3x + 2y = 1 4x + 7z = 1 x + y + z =3 x - 2y + 7z = 0 The number of solutions for this system is ______________________

Consider the statement "Not all that glitters is gold" Predicate glitters$$(x)$$ is true if $$x$$ glitters and predicate gold$$(x)$$ is true if $$x$$ is gold. Which one of the foll...

An ordered $$n$$-tuple $$\left( {{d_1},\,\,{d_2},\,....,{d_n}} \right)$$ with $${{d_1} \ge ,\,\,{d_2} \ge .... \ge {d_n}}$$ is called graphic if there exists a simple undirected gr...

Assume that there are $$3$$ page frames which are initially empty. If the page reference string is $$1, 2, 3, 4, 2, 1, 5, 3, 2, 4, 6,$$ the number of page faults using the optimal...

Let S denote the set of all functions $$f:\,{\{ 0,\,1\} ^4}\, \to \,\{ 0,\,1\} $$. Denote by N the number of functions from S to the set {0, 1}. The value of $${\log _2}$$ $${\log...

A machine has a $$32$$-bit architecture, with $$1$$-word long instructions. It has $$64$$ registers, each of which is $$32$$ bits long. It needs to support $$45$$ instructions, whi...

Suppose a disk has 201 cylinders, numbered from 0 to 200. At some time the disk arm is at cylinder 100, and there is a queue of disk access requests for cylinders 30, 85, 90, 100,...

Which one of the following is TRUE?

Let $$L$$ be a language and $$\overline L $$ be its complement. Which one of the following is NOT a viable possibility?

A graphical HTML browser resident at a network client machine Q accesses a static HTML webpage from a HTTP server S. The static HTML page has exactly one static embedded image whic...

The maximum number of superkeys for the relation schema $$R(E, F, G, H)$$ with $$E$$ as key is ______.

Suppose n and p are unsigned int variables in a C program. We wish to set p to $${}^n{C_3}$$. If n is large, which one of the following statements is most likely to set p correctly...

For a C program accessing X[ i ] [ j ] [ k ], the following intermediate code is generated by a compiler. Assume that the size of an integer is 32 bits and the size of a character...

A FAT (file allocation table) based file system is being used and the total overhead of each entry in the FAT is $$4$$ bytes in size. Given a $$100\,\, \times \,\,{10^6}$$ bytes di...

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?

The dual of a Boolean function $$F\left( {{x_1},{x_2},\,....,\,{x_n},\, + , \cdot ,'} \right),$$ written as $${F^D}$$, is the same expression as that of $$F$$ with $$+$$ and $$ \cd...

The product of the non-zero eigenvalues of the matrix $$\left[ {\matrix{ 1 & 0 & 0 & 0 & 1 \cr 0 & 1 & 1 & 1 & 0 \cr 0 & 1 & 1 & 1 & 0 \cr 0 & 1 & 1 & 1 & 0 \cr 1 & 0 & 0 & 0 & 1 \...

Three processes $$A, B$$ and $$C$$ each execute a loop of $$100$$ iterations. In each iteration of the loop, a process performs a single computation that requires $${t_c}\,\,CPU$$...

Suppose a stack implementation supports an instruction REVERSE, which reverses the order of elements on the stack, in addition to the PUSH and POP instructions. Which one of the fo...

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); addTo...

Which one of the following is TRUE about the interior gateway routing protocols – Routing Information Protocol (RIP) and Open Shortest Path First (OSPF)?

Which one of the following is TRUE?

Which one of the following Boolean expressions is NOT A tautology?

The probability that a given positive integer lying between 1 and 100 (both inclusive) is NOT divisible by 2, 3 or 5 is _______________

Consider the tree arcs of a BFS traversal from a source node W in an unweighted, connected, undirected graph. The tree T formed by the tree arcs is a data structure for computing

If the matrix A is such that $$$A = \left[ {\matrix{ 2 \cr { - 4} \cr 7 \cr } } \right]\,\,\left[ {\matrix{ 1 & 9 & 5 \cr } } \right]$$$ then the determinant of A is equal to _____...

Consider the grammar defined by the following production rules, with two operators * and + $$\eqalign{ & S \to T*P \cr & T \to U\,|\,T*U \cr & P \to Q + P\,|\,Q \cr & Q \to id \cr...

The value of a float type variable is represented using the single-precision $$32$$-bit floating point format of $$IEEE-754$$ standard that uses $$1$$ bit for sign, $$8$$ bits for...

The security system at an IT office is composed of 10 computers of which exactly four are working. To check whether the system is functional, the officials inspect four of the comp...

Which one of the following is NOT performed during compilation?

Consider the function func shown below: int func(int num) { int count = 0; while(num) { count++; num >>= 1; } return (count); } The value returned by func(435) is _________.

Consider the following relation on subsets of the set S integers between 1 and 2014. For two distinct subsets U and V of S we say U < V if the minimum element in the symmetric diff...

Consider a main memory system that consists of 8 memory modules attached to the system bus, which is one word wide. When a write request is made, the bus is occupied for $$100$$ na...

Consider two strings A = “qpqrr” and B = “pqprqrp”. Let x be the length of the longest common subsequence (not necessarily contiguous) between A and B and let y be the number of su...

A priority queue is implemented as a Max-Heap. Initially, it has 5 elements. The level-order traversal of the heap is: 10, 8, 5, 3, 2. Two new elements 1 and 7 are inserted into th...

Consider the equation $${\left( {123} \right)_5} = {\left( {x8} \right)_y}$$ with $$x$$ and $$y$$ as unknown. The number of possible solutions is _________.

Suppose P, Q, R, S, T are sorted sequences having lengths 20, 24, 30, 35, 50 respectively. They are to be merged into a single sequence by merging together two sequences at a time....

Which one of the following correctly determines the solution of the recurrence relation with T(1) = 1? T(1) = 2T (n/2) + log n

Which one of the following socket API functions converts an unconnected active TCP socket into a passive socket?

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?

Each of the nine words in the sentence "The Quick brown fox jumps over the lazy dog" is written on a separate piece of paper. These nine pieces of paper are kept in a box. One of t...

Let $$k = {2^n}.$$ A circuit is built by giving the output of an ݊$$n$$-bit binary counter as input to an $$n$$-to-$${2^n}$$ bit decoder. This circuit is equivalent to a

Consider a join (relation algebra) between relations r(R) and s(S) using the nested loop method. There are 3 buffers each of size equal to disk block size, out of which one buffer...

Consider the C function given below. int f(int j) { static int i = 50; int k; if (i == j) { printf("something"); k = f(i); return 0; } else return 0; } Which one of the following i...

A cycle on $$n$$ vertices is isomorphic to its complement. The value of $$n$$ is __________.

A $$4$$-way set-associative cache memory unit with a capacity of $$16KB$$ is built using a block size of $$8$$ words. The word length is $$32$$ bits. The size of the physical addre...

The number of distinct positive integral factors of 2014 is _______ .

SQL allows duplicate tuples in relations, and correspondingly defines the multiplicity of tuples in the result of joins. Which one of the following queries always gives the same an...

A computer has twenty physical page frames which contain pages numbered $$101$$ through $$120.$$ Now a program accesses the pages numbered $$1, 2, …, 100$$ in that order, and repea...

An IP machine Q has a path to another IP machine H via three IP routers R1, R2, and R3. Q—R1—R2—R3—H H acts as an HTTP server, and Q connects to H via HTTP and downloads a file. Se...

Consider the following function double f (double x) { if ( abs (x * x – 3) < 0. 01) return x; else return f (x / 2 + 1.5/x); } Give a value q (to 2 decimals) such that f(q) will re...

Let $${L_1} = \left\{ {w \in \left\{ {0,1} \right\}{}^ * \left| w \right.} \right.$$ has at least as many occurrences of $$(110)'s$$ as $$(011)'s$$$$\left. \, \right\}$$. Let $${L_...

Let $$ < M > $$ be the encoding of a Turing machine as a string over $$\sum { = \left\{ {0,1} \right\}.} $$ Let $$L = \left\{ { < M > \left| M \right.} \right.$$ is a Turing machin...

Let $${L_1} = \left\{ {w \in \left\{ {0,1} \right\}{}^ * \left| w \right.} \right.$$ has at least as many occurrences of $$(110)'s$$ as $$(011)'s$$$$\left. \, \right\}$$. Let $${L_...

Let $$A\,\,{ \le _m}\,\,B$$ denotes that language $$A$$ is mapping reducible (also known as many-to-one reducible) to language $$B.$$ Which one of the following is FALSE?

If $${L_1} = \left\{ {{a^n}\left| {n \ge \left. 0 \right\}} \right.} \right.$$ and $${L_2} = \left\{ {{b^n}\left| {n \ge \left. 0 \right\}} \right.} \right.,$$ consider $$\left. {\...

The CORRECT formula for the sentence, "not all rainy days are cold" is

Let A be a square matrix size $$n \times n$$. Consider the following pseudocode. What is the expected output? C = 100; for i = 0 to n do for j = 1 to n do { Temp = A[ i ][ j ] + C...

let $$G$$ be a group with $$15$$ elements. Let $$L$$ be a subgroup of $$G$$. It is known that $$L \ne G$$ and that the size of $$L$$ is at least $$4$$. The size of $$L$$ is ______.

In the following pairs of OSI protocol layer/sub-layer and its functionality, the INCORRECT pair is

Host A (on TCP/IPv4 network A) sends an IP datagram D to host B (also on TCP/IPv4 network B). Assume that no error occurred during the transmission of D. When D reaches B, which of...

One of the purposes of using intermediate code in compilers is to

A system contains three programs and each requires three tape units for its operation. The Minimum number of tape units which the system must have such that deadlocks never arise i...

Consider the pseudocode given below. The function Dosomething () takes as argument a pointer to the root of an arbitrary tree represented by the leftMostChild-rightSibling represen...

Consider the set of all functions $$f:\left\{ {0,\,1,.....,2014} \right\} \to \left\{ {0,\,1,.....,2014} \right\}$$ such that $$f\left( {f\left( i \right)} \right) = i,\,\,\,$$ for...

Let $$ \oplus $$ denote the exclusive $$OR\left( {XOR} \right)$$ operation. Let $$'1'$$ and $$'0'$$ denote the binary constants. Consider the following Boolean expression for $$F$$...

Consider the following interm expression of $$F:$$ $$F\left( {P,\,Q,\,R,\,S} \right) = \sum {0,2,5,7,8,10,13,15} $$ The minterms $$2, 7, 8$$ and $$13$$ are 'do not care' terms. The...

Consider a hash table with 100 slots. Collisions are resolved using chaining. Assuming simple uniform hashing, what is the probability that the first 3 slots are unfilled after the...

Consider the basic block given below. a = b + c c = a + d d = b + c e = d - b a = e + b The minimum number of nodes and edges present in the DAG representation of the above basic b...

Let S be a sample space and two mutually exclusive events A and B be such that $$A\, \cup \,B = \,S$$. If P(.) denotes the probability of the event, the maximum value of P(A) P(B)...

An instruction pipeline has five stages, namely, instruction fetch $$(IF),$$ instruction decode and register fetch $$(ID/RF)$$ instruction execution $$(EX),$$ memory access $$(MEM)...

If $$G$$ is a forest with $$n$$ vertices and $$k$$ connected components, how many edges does $$G$$ have?

An IP router with a Maximum Transmission Unit (MTU) of 1500 bytes has received an IP packet of size 4404 bytes with an IP header of length 20 bytes. The values of the relevant fiel...

Consider the transactions T1, T2, and T3 and the schedules S1 and S2 given below. T1 : r1 (X) ; r1 (Z) ; w1 (X) ; w1 (Z) T2 : r2 (X) ; r2 (Z) ; w2 (Z) T3 : r3 (X) ; r3 (X) ; w3 (Y)...

Suppose we have a balanced binary search tree T holding n numbers. We are given two numbers L and H and wish to sum up all the numbers in T that lie between L and H. Suppose there...

What is the optimized version of the relation algebra expression $$\pi_{A1}(\pi_{A2}(\sigma_{F1}(\sigma_{F2}(r))))$$, where $$A1, A2$$ are sets of attributes in r with $$A1 \subset...

The value of the integral given below is $$$\int_0^\pi {{x^2}\,\cos \,x\,dx} $$$

Consider a paging hardware with a TLB. Assume that the entire page table and all the pages are in the physical memory. It takes 10 milliseconds to search the TLB and 80 millisecond...

Consider the following relational schema: employee ( empId, empName, empDept ) customer ( custId, custName, salesRepId, rating) SalesRepId is a foreign key referring to empId of th...

The minimum number of arithmetic operations required to evaluate the polynomial P(X) = X 5 + 4X 3 + 6X + 5 for a given value of X using only one temporary variable is _____.

Consider the following statements: P: Good mobile phones are not cheap Q: Cheap mobile phones are not good L: P implies Q M: Q implies P N: P is equivalent to Q Which of the follow...

Consider the decision problem 2CNFSAT defined as follows: { $$\Phi $$ | $$\Phi $$ is a satisfiable propositional formula in CNF with at most two literal per clause} For example, $$...

You have an array of n elements. Suppose you implement quicksort by always choosing the central element of the array as the pivot. Then the tightest upper bound for the worst case...

There are two elements $$x, y$$ in a group $$\left( {G,\, * } \right)$$ such that every elements in the group can be written as a product of some number of $$x's$$ and $$y's$$ in s...

Suppose you want to move from 0 to 100 on the number line. In each step, you either move right by a unit distance or you take a shortcut. A shortcut is simply a pre specified pair...

Which of the following statements are CORRECT? 1) Static allocation of all data areas by a compiler makes it impossible to implement recursion. 2) Automatic garbage collection is e...

Every host in an IPv4 network has a 1-second resolution real-time clock with battery backup. Each host needs to generate up to 1000 unique identifiers per second. Assume that each...

Let $$\delta $$ denote the minimum degree of a vertex in a graph. For all planar graphs on $$n$$ vertices with $$\delta \ge 3$$, which one of the following is TRUE?

Which one of the following statements is TRUE about every $$n\,\, \times \,n$$ matrix with only real eigen values?

Let $$X$$ and $$Y$$ be finite sets and $$f:X \to Y$$ be a function. Which one of the following statements is TRUE?

Consider the C function given below. Assume that the array listA contains n (> 0) elements, sored in ascending order. int ProcessArray(int *listA, int x, int n) { int i, j, k; i =...

An operating system uses $$shortest$$ $$remaining$$ $$time$$ $$first$$ scheduling algorithm for pre-emptive scheduling of processes. Consider the following set of processes with th...

If $${V_1}$$ and $${V_2}$$ are 4-dimensional subspaces of a 6-dimensional vector space V, then the smallest possible dimension of $${V_1}\, \cap \,\,{V_2}$$ is _________________.

Consider the relational schema given below, where eId of the relation dependent is a foreign key referring to empId of the relation employee . Assume that every employee has at lea...

If $$\int_0^{2\pi } {\left| {x\sin x} \right|dx = k\pi ,} $$ then the values of $$k$$ is equal to _________ .

A system uses $$3$$ page frames for storing process pages in main memory. It uses the Least Recently Used $$(LRU)$$ page replacement policy. Assume that all the page frames are ini...

In the context of modular software design, which one of the following combinations is desirable?

A bit-stuffing based framing protocol uses an 8-bit delimiter pattern of 01111110. If the output bit-string after stuffing is 01111100101, then the input bit-string is

A prime attribute of a relation scheme $$R$$ is an attribute that appears

The memory access time is $$1$$ nanosecond for a read operation with a hit in cache, $$5$$ nanoseconds for a read operation with a miss in cache, $$2$$ nanoseconds for a write oper...

Consider the following processors ($$ns$$ stands for nanoseconds). Assume that the pipeline registers have zero latency. $$P1:$$ Four-stage pipeline with stage latencies $$1$$ $$ns...

The length of the shortest string NOT in the language (over $$\sum { = \left\{ {a,\,\,b} \right\}} $$) of the following regular expression is ____________. $$$a{}^ * b{}^ * \left(...

Which one of the following problems is un-decidable?

Consider the following languages over the alphabet $$\sum { = \left\{ {0,\,1,\,c} \right\}:} $$ $$\eqalign{ & {L_1} = \left\{ {{0^n}\,{1^n}\,\left| {n \ge } \right.0} \right\} \cr...

Let $$\sum \, $$ be a finite non - empty alphabet and let $${2^{\sum {{}^ * } }}$$ be the power set of $$\sum {{}^ * .\,} $$ Which one of the following is TRUE ?