Recent questions tagged gate1998

Let $R$ be a binary relation on $A = \{a, b, c, d, e, f, g, h\}$ represented by the following two component digraph. Find the smallest integers $m$ and $n$ such that $m <...

Solve the following recurrence relation$x_n = 2x_{n-1}-1, n>1$$x_1=2$

Compute the post fix equivalent of the following expression $3^*\log(x+1)-\frac{a}{2}$

In a computer system where the ‘best-fit’ algorithm is used for allocating ‘jobs’ to ‘memory partitions’, the following situation was encountered:$$\begin{array}{|l|l|} \...

Give a regular expression for the set of binary strings where every $0$ is immediately followed by exactly $k$ $1$'s and preceded by at least $k$ $1$’s ($k$ is a fixed i...

Consider the following relational database schemes:COURSES (Cno, Name)PRE_REQ(Cno, Pre_Cno)COMPLETED (Student_no, Cno)COURSES gives the number and name of all the availab...

Consider the following database relations containing the attributesBook_idSubject_Category_of_bookName_of_AuthorNationality_of_AuthorWith Book_id as the primary key.What ...

Free disk space can be used to keep track of using a free list or a bit map. Disk addresses require $d$ bits. For a disk with $B$ blocks, $F$ of which are free, state the...

Four jobs are waiting to be run. Their expected run times are $6, 3, 5$ and $x.$ In what order should they be run to minimize the average response time?Write a concurrent...

Let the attribute ‘$val$’ give the value of a binary number generated by $S$ in the following grammar:$S \rightarrow L.L \mid L$$L \rightarrow LB \mid B$$B \rightarrow 0 ...

An identifier in a programming language consists of up to six letters and digits of which the first character must be a letter. Derive a regular expression for the identi...

Derive a recurrence relation for the size of the smallest AVL tree with height $h$.What is the size of the smallest AVL tree with height $8$?

Draw the binary tree with node labels $\text{a, b, c, d, e, f and g}$ for which the inorder and postorder traversals result in the following sequences:Inorder: $\text{a f...

Let $p$ be a pointer as shown in the figure in a single linked list. What do the following assignment state...

Design a synchronous counter to go through the following states:$$1, 4, 2, 3, 1, 4, 2, 3, 1, 4 \dots $$

Let $G_1 = (N, T, P, S_1)$ be a CFG where, $N=\{S_1, A, B\},T=\{a, b\}$ and $P$ is given by$$\begin{array}{l|l}S_1 \rightarrow a S_1 b &S_1 \rightarrow a B b \\S_1 \right...

Let $M=(\{q_0, q_1\}, \{0, 1\}, \{z_0, X\}, \delta, q_0, z_0, \phi)$ be a Pushdown automation where $\delta$ is given by$\delta(q_0, 1, z_0) = \{(q_0, Xz_0)\}$$\delta(q_0...

Let $(A, *)$ be a semigroup, Furthermore, for every $a$ and $b$ in $A$, if $a \neq b$, then $a*b \neq b*a$.Show that for every $a$ in $A$, $a*a=a$Show that for every $a$,...

Suppose $A = \{a, b, c, d\}$ and $\Pi_1$ is the following partition of A$\Pi_1 = \left\{\left\{a, b, c\right\}\left\{d\right\}\right\}$List the ordered pairs of the equiv...

Prove by induction that the expression for the number of diagonals in a polygon of $n$ sides is $\frac{n(n-3)}{2}$

Derive the expressions for the number of operations required to solve a system of linear equations in $n$ unknowns using the Gaussian Elimination Method. Assume that one ...

Find the points of local maxima and minima, if any, of the following function defined in $0\leq x\leq 6$. $$x^3-6x^2+9x+15$$Integrate $$\int_{-\pi}^{\pi} x \cos x dx$$

Suppose we have a database consisting of the following three relations.$\text{FREQUENTS (student, parlor)}$ giving the parlors each student visits.$\text{SERVES (parlor, ...

Consider the grammarS $\rightarrow Aa \mid b$A $\rightarrow Ac \mid Sd \mid \epsilon$Construct an equivalent grammar with no left recursion and with minimum number of pr...

The implication gate, shown below has two inputs ($x \text{ and }y)$; the output is 1 except when $x =1 \text{ and } y=0\text{, realize }f=\bar{x}y+x\bar{y}$ using only f...

Design a deterministic finite state automaton (using minimum number of states) that recognizes the following language:$L=\{w \in \{0, 1\}^* \mid w$ interpreted as binar...