GATE PYQ

GATE CSE 2014 SET-3

Q41.
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 of integers i,j with i \lt j. Given a shortcut i, j if you are at position i on the number line, you may directly move to j. Suppose T(k) denotes the smallest number of steps needed to move from k to 100. suppose further that there is at most 1 shortcut involving any number, and in particular from 9 there is a shortcut to 15. Let y and z be such that T(9) = 1 + min(T(y), T(z)). Then the value of the product yz is_______.

Q42.
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 host has a globally unique IPv4 address. Design a 50-bit globally unique ID for this purpose. After what period (in seconds) will the identifiers generated by a host wrap around?

Q43.
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 A_{1}\subset A_{2} and F1, F2 are Boolean expressions based on the attributes in r?

Q44.
An IP router implementing Classless Inter-domain routing (CIDR) receives a packet with address 131.23.151.76. The router's routing table has the following entries: The identifier of the output interface on which this packet will be forwarded is _____.

Q45.
Consider the relational schema given below, where eId of the relation dependentis a foreign key referring to empId of the relation employee. Assume that every employee has at least one associated dependent in the dependent relation. The above query evaluates to the set of empIds of employees whose age is greater than that of

Q46.
The length of the shortest string NOT in the language (over \Sigma={a,b}) of the following regular expression is _________. ab (ba)* a*

Q47.
Let x and Y be finite sets and f:x\rightarrowY be a function. Which one of the following statements is TRUE?

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

Q49.
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 essential to implement recursion. 3) Dynamic allocation of activation records is essential to implement recursion. 4) Both heap and stack are essential to implement recursion.

Q50.
Consider the following relational schema: Employee (empId, empName, empDept ) Customer (custId,custName, salesRepId, rating) SalesRepId is a foreign key referring to empId of the employee relation. Assume that each employee makes a sale to at least one customer. What does the following query return? SELECT empName FROM employee E WHERE NOT EXISTS (SELECT custId FROM customer C WHERE C. salesRepId = E. empId AND C. rating < > 'GOOD')