GATE CS question library

Let $p$, $q$ and $r$ be propositions and the expression $\left ( p\rightarrow q \right )\rightarrow r$ be a contradiction. Then, the expression $\left ( r\rightarrow p \right )\rightarrow q$ is

Let $u$ and $v$ be two vectors in $\mathbf{R}^{2}$ whose Euclidean norms satisfy $\left \| u \right \| = 2\left \| v \right \|$. What is the value of $\alpha$ such that $w = u + \alpha v$ bisects the angle between $u$ and $v$?

The value of $\displaystyle \lim_{x\rightarrow 1} \frac{x^{7}-2x^{5}+1}{x^{3}-3x^{2}+2}$

Let $G=\left ( V,E \right )$ be $any$ connected, undirected, edge-weighted graph. The weights of the edges in $E$ are positive and distinct. Consider the following statements: Minimum Spanning Tree of $G$ is always unique. Shortest path between any two vertices of $G$ is always unique. Which of the above statements is/are necessarily true?

A multithreaded program $P$ executes with $x$ number of threads and uses $y$ number of locks for ensuring mutual exclusion while operating on shared memory locations. All locks in the program are non-reentrant, i.e., if a thread holds a lock $l$, then it cannot re-acquire lock $l$ without releasing it. If a thread is unable to acquire a lock, it …

Consider a two-level cache hierarchy with $L1$ and $L2$ caches. An application incurs $1.4$ memory accesses per instruction on average. For this application, the miss rate of $L1$ cache is $0.1$; the $L2$ cache experiences, on average, $7$ misses per $1000$ instructions. The miss rate of $L2$ expressed correct to two decimal places is …

Consider the following CPU processes with arrival times (in milliseconds) and length of CPU bursts (in milliseconds) as given below: …

Consider a database that has the relation schema EMP (EmpId, EmpName, and DeptName). An instance of the schema EMP and a SQL query on it are given below: …

Consider the language $L$ given by the regular expression $(a+b)^{*} b (a+b)$ over the alphabet $\{a,b\}$. The smallest number of states needed in a deterministic finite-state automaton (DFA) accepting $L$ is ___________ .

Let $T$ be a tree with $10$ vertices. The sum of the degrees of all the vertices in $T$ is ________

Consider the Karnaugh map given below, where $X$ represents "don't care" and blank represents $0$. Assume for all inputs $\left ( a,b,c,d \right )$, the respective complements $\left ( \bar{a}, \bar{b}, \bar{c}, \bar{d} \right )$ are also available. The above logic is implemented using $2$-input $\text{NOR}$ gates only. The minimum number of …

Let $X$ be a Gaussian random variable with mean 0 and variance $\sigma ^{2}$. Let $Y$ = $\max\left ( X,0 \right )$ where $\max\left ( a,b \right )$ is the maximum of $a$ and $b$. The median of $Y$ is ______________ .

Threads of a process share

The following functional dependencies hold true for the relational schema $R\left \{V,W,X,Y,Z \right \}$: $V \rightarrow W$ $VW \rightarrow X$ $Y \rightarrow VX$ $Y \rightarrow Z$ Which of the following is irreducible equivalent for this set of functional dependencies?

A sender $S$ sends a message $m$ to receiver $R$, which is digitally signed by $S$ with its private key. In this scenario, one or more of the following security violations can take place. $S$ can launch a birthday attack to replace $m$ with a fraudulent message $A$ third party attacker can launch a birthday attack to replace $m$ with a …

Consider the following C code: #include<stdio.h> int *assignval (int *x, int val) { *x = val; return x; } void main () { int *x = malloc(sizeof(int)); if (NULL == x) return; x = assignval (x,0); if (x) { x = (int *)malloc(sizeof(int)); if (NULL == x) return; x = assignval (x,10); } printf("%d\n", *x); free(x); } The code suffers from which one of the …

Consider the following intermediate program in three address code p = a - b q = p * c p = u * v q = p + q Which one of the following corresponds to a static single assignment form of the above code?

Consider the $C$ struct defined below: struct data { int marks [100]; char grade; int cnumber; }; struct data student; The base address of student is available in register $R1$. The field student.grade can be accessed efficiently using:

Consider the following context-free grammar over the alphabet $\Sigma = \{a,b,c\}$ with $S$ as the start symbol:$$S \rightarrow abScT \mid abcT$$$$T \rightarrow bT \mid b$$Which one of the following represents the language generated by the above grammar?

When two $8\text{-bit}$ numbers $A_{7}\cdots A_{0}$ and $B_{7}\cdots B_{0}$ in $2$'s complement representation (with $A_{0}$ and $B_{0}$ as the least significant bits) are added using a ripple-carry adder, the sum bits obtained are $S_{7}\cdots S_{0}$ and the carry bits are $C_{7}\cdots C_{0}$. An overflow is said to have occurred if