GATE CS question library

There are two elements $x,\:y$ in a group $(G,*)$ such that every element in the group can be written as a product of some number of $x$'s and $y$'s in some order. It is known that $$x*x=y*y=x*y*x*y=y*x*y*x=e$$ where $e$ is the identity element. The maximum number of elements in such a group is ____.

Consider the set of all functions $f:\{0,1, \dots,2014\} \to \{0,1,\dots, 2014\}$ such that $f\left(f\left(i\right)\right)=i$, for all $0 \leq i \leq 2014$. Consider the following statements: $P$. For each such function it must be the case that for every $i,f(i) = i$. $Q$. For each such function it must be the case that for some $i,f(i)=i$. …

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)$ is_____.

With respect to the numerical evaluation of the definite integral, $K = \int \limits_a^b \:x^2 \:dx$, where $a$ and $b$ are given, which of the following statements is/are TRUE? The value of $K$ obtained using the trapezoidal rule is always greater than or equal to the exact value of the definite integral. The value of $K$ obtained using the …

The value of the integral given below is $$\int \limits_0^{\pi} \: x^2 \: \cos x\:dx$$

The above synchronous sequential circuit built using JK flip-flops is initialized with $Q_2Q_1Q_0 = 000$. The state sequence for this circuit for the next $3$ clock cycles is

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 operation with a hit in cache and $10$ nanoseconds for a write operation with a miss in cache. Execution of a sequence of instructions involves $100$ instruction fetch operations, …

An instruction pipeline has five stages, namely, instruction fetch (IF), instruction decode and register fetch (ID/RF), instruction execution (EX), memory access (MEM), and register writeback (WB) with stage latencies $1$ ns, $2.2$ ns, $2$ ns, $1$ ns, and $0.75$ ns, respectively (ns stands for nanoseconds). To gain in terms of frequency, the …

Consider the C function given below. Assume that the array $listA$ contains $n (>0)$ elements, sorted in ascending order. int ProcessArray(int *listA, int x, int n) { int i, j, k; i = 0; j = n-1; do { k = (i+j)/2; if (x <= listA[k]) j = k-1; if (listA[k] <= x) i = k+1; } while (i <= j); if (listA[k] == x) return(k); else return -1; } Which …

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$ representation. Each node of the tree is of type $treeNode$. typedef struct treeNode* treeptr; struct treeNode { treeptr leftMostChild, rightSibling; }; int DoSomething (treeptr …

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 first $3$ insertions?

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 are $m$ such numbers in $T$. If the tightest upper bound on the time to compute the sum is $O(n^a\log^bn+m^c\log^dn)$, the value of …

Consider the decision problem $2CNFSAT$ defined as follows: $$\left\{ \phi \mid \phi \text{ is a satisfiable propositional formula in CNF with at most two literals per clause}\right\}$$ For example, $\phi = (x1 \vee x2) \wedge (x1 \vee \bar{x3}) \wedge (x2 \vee x4)$ is a Boolean formula and it is in $2CNFSAT$. The decision problem $2CNFSAT$ is

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 \:\text{with}\: i <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)$ …

Consider the following languages over the alphabet $\sum = \{0, 1, c\}$ $L_1 = \left\{0^n1^n\mid n \geq 0\right\}$ $L_2 = \left\{wcw^r \mid w \in \{0,1\}^*\right\}$ $L_3 = \left\{ww^r \mid w \in \{0,1\}^*\right\}$ Here, $w^r$ is the reverse of the string $w$. Which of these languages are deterministic Context-free languages?

Which one of the following problems is undecidable?

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 block respectively are

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$ milliseconds to access the physical memory. If the $TLB$ hit ratio is $0.6$, the effective memory access time (in milliseconds) is _________.

An operating system uses shortest remaining time first scheduling algorithm for pre-emptive scheduling of processes. Consider the following set of processes with their arrival times and CPU burst times (in milliseconds): …

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 is _________.