GATE CS question library

Six people are seated around a circular table. There are at least two men and two women. There are at least three right-handed persons. Every woman has a left-handed person to her immediate right. None of the women are right-handed. The number of women at the table is

The probability that a $k$-digit number does NOT contain the digits $0, 5,$ or $9$ is

Find the smallest number $y$ such that $y \times 162$ is a perfect cube.

Rahul, Murali, Srinivas and Arul are seated around a square table. Rahul is sitting to the left of Murali. Srinivas is sitting to the right of Arul. Which of the following pairs are seated opposite each other?

Research in the workplace reveals that people work for many reasons _______________ .

After Rajendra Chola returned from his voyage to Indonesia, he ________ to visit the temple in Thanjavur.

Consider a RISC machine where each instruction is exactly $4$ bytes long. Conditional and unconditional branch instructions use PC-relative addressing mode with Offset specified in bytes to the target location of the branch instruction. Further the Offset is always with respect to the address of the next instruction in the program sequence. Consider the …

Let $A$ be an array of $31$ numbers consisting of a sequence of $0$'s followed by a sequence of $1$'s. The problem is to find the smallest index $i$ such that $A\left [i \right ]$ is $1$ by probing the minimum number of locations in $A$. The worst case number of probes performed by an optimal algorithm is ____________.

The number of integers between $1$ and $500$ (both inclusive) that are divisible by $3$ or $5$ or $7$ is ____________ .

Consider a database that has the relation schema CR(StudentName, CourseName). An instance of the schema CR is as given below. …

The values of parameters for the Stop-and-Wait ARQ protocol are as given below: Bit rate of the transmission channel $= 1$ Mbps. Propagation delay from sender to receiver $= 0.75$ ms. Time to process a frame $= 0.25$ ms. Number of bytes in the information frame $= 1980$. Number of bytes in the acknowledge frame $= 20$. Number of overhead bytes in …

In a RSA cryptosystem, a participant $A$ uses two prime numbers $p = 13$ and $q = 17$ to generate her public and private keys. If the public key of $A$ is $35$, then the private key of $A$ is __________ .

Consider the following grammar: stmt $\rightarrow$ if expr then expr else expr; stmt | $Ò$ expr $\rightarrow$ term relop term | term term $\rightarrow$ id | number id $\rightarrow$ a | b | c number $\rightarrow [0-9]$ where relop is a relational operator $($e.g., $< , >,\ldots),$ $Ò$ refers to the empty statement, and if, then, else …

In a database system, unique timestamps are assigned to each transaction using Lamport's logical clock. Let $TS(T_{1})$ and $TS(T_{2})$ be the timestamps of transactions $T_{1}$ and $T_{2}$ respectively. Besides, $T_{1}$ holds a lock on the resource $R,$ and $T_{2}$ has requested a conflicting lock on the same resource $R.$ The following …

Consider a database that has the relation schemas EMP(EmpId, EmpName, DeptId), and DEPT(DeptName, DeptId). Note that the DeptId can be permitted to be NULL in the relation EMP. Consider the following queries on the database expressed in tuple relational calculus. {$t$ | $\exists$u $\in$ EMP(t[EmpName] = u[EmpName] $\wedge$ $\forall$v $\in$ …

Recall that Belady's anomaly is that the page-fault rate may increase as the number of allocated frames increases. Now, consider the following statements: $S_1$: Random page replacement algorithm (where a page chosen at random is replaced) suffers from Belady's anomaly. $S_2$: LRU page replacement algorithm suffers from Belady's anomaly. Which of the …

Let $A$ and $B$ be finite alphabets and let $\#$ be a symbol outside both $A$ and $B$. Let $f$ be a total function from $A^{*}$ to $B^{*}$. We say $f$ is computable if there exists a Turing machine $M$ which given an input $x \in A^{*}$, always halts with $f(x)$ on its tape. Let $L_{f}$ denote the language …

Consider the following languages over the alphabet $\Sigma = \left \{ a, b, c \right \}$. Let $L_{1} = \left \{ a^{n}b^{n}c^{m}\mid m,n \geq 0 \right \}$ and $L_{2} = \left \{ a^{m}b^{n}c^{n}\mid m,n \geq 0 \right \}$. Which of the following are context-free languages? $L_{1} \cup L_{2}$ $L_{1} \cap L_{2}$

Consider the context-free grammars over the alphabet $\left \{ a, b, c \right \}$ given below. $S$ and $T$ are non-terminals. $G_{1}:S\rightarrow aSb \mid T, T \rightarrow cT \mid \epsilon$ $G_{2}:S\rightarrow bSa \mid T, T \rightarrow cT \mid \epsilon$ The language $L\left ( G_{1} \right )\cap L(G_{2})$ is

Consider the C functions foo and bar given below: int foo(int val) { int x=0; while(val > 0) { x = x + foo(val--); } return val; } int bar(int val) { int x = 0; while(val > 0) { x= x + bar(val-1); } return val; } Invocations of $foo(3)$ and $bar(3)$ will result in: