Recent questions tagged gate1999

Consider the following solution to the producer-consumer problem using a buffer of size 1. Assume that the initial value of count is 0. Also assume that the testing of co...

Write a constant time algorithm to insert a node with data $D$ just before the node with address $p$ of a singly linked list.

Mr. X claims the following: If a relation R is both symmetric and transitive, then R is reflexive. For this, Mr. X offers the following proof:“From xRy, using symme...

Consider the set of relationsEMP (Employee-no. Dept-no, Employee-name, Salary)DEPT (Dept-no. Dept-name, Location)Write an SQL query to:Find all employees names who work i...

Consider a B-tree with degree $m$, that is, the number of children, $c$, of any internal node (except the root) is such that $m \leq c \leq 2m-1$. Derive the maximum and ...

A certain processor provides a 'test and set' instruction that is used as follows:TSET register, flagThis instruction atomically copies flag to register and sets flag to ...

A certain computer system has the segmented paging architecture for virtual memory. The memory is byte addressable. Both virtual and physical address spaces contain $2^{1...

Consider the following program fragment in the assembly language of a certain hypothetical processor. The processor has three general purpose registers $R1, R2$ and $R3$....

What will be the output of the following program assuming that parameter passing iscall by valuecall by referencecall by copy restoreprocedure P{x, y, z}; begin y:y+1; z:...

Show that the formula $\left[(\sim p \vee q) \Rightarrow (q \Rightarrow p)\right]$ is not a tautology.Let $A$ be a tautology and $B$ any other formula. Prove that $(A \ve...

An instruction pipeline consists of $4$ stages – Fetch $(F)$, Decode field $(D)$, Execute $(E)$ and Result Write $(W)$. The $5$ instructions in a certain instruction sequ...

In binary tree, a full node is defined to be a node with $2$ children. Use induction on the height of the binary tree to prove that the number of full nodes plus one is e...

Consider the following algorithms. Assume, procedure $A$ and procedure $B$ take $O (1)$ and $O(1/n)$ unit of time respectively. Derive the time complexity of the algorith...

Let $A$ be an $n \times n$ matrix such that the elements in each row and each column are arranged in ascending order. Draw a decision tree, which finds $1$st, $2$nd and $...

Show that the language $$L = \left\{ xcx \mid x \in \left\{0,1\right\}^* \text{ and }c\text{ is a terminal symbol}\right\}$$ is not context free. $c$ is not $0$ or $1$.

Given that $A$ is regular and $(A \cup B)$ is regular, does it follow that $B$ is necessarily regular? Justify your answer.Given two finite automata $M1, M2$, outline an ...

Let $G$ be a connected, undirected graph. A cut in $G$ is a set of edges whose removal results in $G$ being broken into two or more components, which are not connected wi...

Let $G$ be a finite group and $H$ be a subgroup of $G$. For $a \in G$, define $aH=\left\{ah \mid h \in H\right\}$.Show that $|aH| = |bH|.$Show that for every pair of elem...

Which of the following is/are correct?An SQL query automatically eliminates duplicatesAn SQL query will not work if there are no indexes on the relationsSQL permits attri...

Consider the following $C$ function definitionint Trial (int a, int b, int c) { if ((a>=b) && (c<b)) return b; else if (a>=b) return Trial(a, c, b); else return Trial(b, ...

A certain processor supports only the immediate and the direct addressing modes. Which of the following programming language features cannot be implemented on this proces...

The main difference(s) between a CISC and a RISC processor is/are that a RISC processor typicallyhas fewer instructionshas fewer addressing modeshas more registersis easi...

If $T_1 = O(1)$, give the correct matching for the following pairs:$$\begin{array}{|ll|ll|}\hline & \text{(M) $T_n = T_{n-1} + n$} & \text{(U) $T_n = O(n)$} \\\hline & ...

Arrange the following configuration for CPU in decreasing order of operating speeds:Hard wired control, Vertical microprogramming, Horizontal microprogramming.Hard wired ...

Raid configurations of the disks are used to provideFault-tolerance High speedHigh data density(A) & (B)