GATE CS 2013

A binary operation [Tex]\\oplus[/Tex] on a set of integers is defined as x [Tex]\\oplus[/Tex] y = x² + y². Which one of the following statements is TRUE about [Tex]\\oplus[/Tex]?

The smallest integer that can be represented by an 8-bit number in 2’s complement form is

In the following truth table, V = 1 if and only if the input is valid. What function does the truth table represent?

Which one of the following is the tightest upper bound that represents the number of swaps required to sort n numbers using selection sort?

Which one of the following is the tightest upper bound that represents the time complexity of inserting an object into a binary search tree of n nodes?

Consider the languages L1 = [Tex]\\phi [/Tex]and L2 = {a}. Which one of the following represents L1 L2^* U L1^*

What is the maximum number of reduce moves that can be taken by a bottom-up parser for a grammar with no epsilon- and unit-production (i.e., of type A -> є and A -> a) to parse a string with n tokens?

A scheduling algorithm assigns priority proportional to the waiting time of a process. Every process starts with priority zero (the lowest priority). The scheduler re-evaluates the process priorities every T time units and decides the next process to schedule. Which one of the following is TRUE if the processes have no I/O operations and all arrive at time zero?

Match the problem domains in GROUP I with the solution technologies in GROUP II

GROUP I                                         GROUP II
(P) Service oriented computing                 (1) Interoperability
(Q) Heterogeneous communicating systems        (2) BPMN
(R) Information representation                 (3) Publish-find-bind
(S) Process description                        (4) XML 

Three concurrent processes X, Y, and Z execute three different code segments that access and update certain shared variables. Process X executes the P operation (i.e., wait) on semaphores a, b and c; process Y executes the P operation on semaphores b, c and d; process Z executes the P operation on semaphores c, d, and a before entering the respective code segments. After completing the execution of its code segment, each process invokes the V operation (i.e., signal) on its three semaphores. All semaphores are binary semaphores initialized to one. Which one of the following represents a deadlock-free order of invoking the P operations by the processes?