GATE 1988 Computer Science Questions

# Recent questions tagged gate1988 0 votes
0 answers
1
The following table gives the cost of transporting one tonne of goods from the origins A, B, C to the destinations F, G, H. Also shown are the availabilities of the goods at the origins and the requirements at the destinations. The transportation problem implied by ... question(i). For the solution of (ii) above, calculate the values of the duals and determine whether this is an optimal solution.
0 votes
0 answers
2
If $x \| \underline{x} \| \infty = 1< i^{max} < n \: \: max \: \: ( \mid x1 \mid )$ for the vector $\underline{x} = (x1, x2 \dots x_n)$ ... using a known property of this norm. Although this norm is very easy to calculate for any matrix, explain why the condition number is difficult (i.e. expensive) to calculate.
4 votes
2 answers
3
Assume that the matrix $A$ given below, has factorization of the form $LU=PA$, where $L$ is lower-triangular with all diagonal elements equal to 1, $U$ is upper-triangular, and $P$ is a permutation matrix. For $A = \begin{bmatrix} 2 & 5 & 9 \\ 4 & 6 & 5 \\ 8 & 2 & 3 \end{bmatrix}$ Compute $L, U,$ and $P$ using Gaussian elimination with partial pivoting.
3 votes
1 answer
4
Consider the DFA $M$ and NFA M2 as defined below. Let the language accepted by machine $M$ be $L$. What language machine M2 accepts, if $F2=A$ ? $F2=B$ ? $F2=C$ ? $F2=D$ ? $M=(Q, \Sigma, \delta, q_0, F)$ $M2=(Q2, \Sigma, \delta_2, q_{00}, F2)$ ... $D=\{\langle p, q, r \rangle \mid p \in Q; q \in F\}$
0 votes
0 answers
5
Consider the following well-formed formula: $\exists x \forall y [ \neg \exists z [ p (y, z) \wedge p (z, y) ] \equiv p(x,y)]$ Show using resolution principle that the well-formed formula, given above, cannot be satisfied for any interpretation.
0 votes
1 answer
6
Consider the following well-formed formula: $\exists x \forall y [ \neg \: \exists z [ p (y, z) \wedge p (z, y) ] \equiv p(x,y)]$ Express the above well-formed formula in clausal form.
9 votes
4 answers
7
Solve the recurrence equations: $T(n)= T( \frac{n}{2})+1$ $T(1)=1$
4 votes
2 answers
8
Are the two digraphs shown in the above figure isomorphic? Justify your answer.
15 votes
1 answer
9
If the set $S$ has a finite number of elements, prove that if $f$ maps $S$ onto $S$, then $f$ is one-to-one.
0 votes
0 answers
10
Verify whether the following mapping is a homomorphism. If so, determine its kernel. $f(x)=x^3$, for all $x$ belonging to $G$.
0 votes
0 answers
11
Verify whether the following mapping is a homomorphism. If so, determine its kernel. $\bar{G}=G$
0 votes
0 answers
12
Verify whether the following mapping is a homomorphism. If so, determine its kernel. $G$ is the group of non zero real numbers under multiplication.
3 votes
2 answers
13
Select SNAME from S Where SNOin (select SNO from SP where PNOin (select PNO from P Where COLOUR='BLUE')) What relations are being used in the above SQL query? Given at least two attributes of each of these relations.
4 votes
2 answers
14
Describe the relational algebraic expression giving the relation returned by the following SQL query. Select SNAME from S Where SNOin (select SNO from SP where PNOin (select PNO from P Where COLOUR='BLUE'))
3 votes
1 answer
15
Using Armstrong’s axioms of functional dependency derive the following rules: $\{ x \rightarrow y, \: z \subset y \} \mid= x \rightarrow z$ (Note: $x \rightarrow y$ denotes $y$ is functionally dependent on $x$, $z \subseteq y$ denotes $z$ is subset of $y$, and $\mid =$ means derives).
3 votes
1 answer
16
Using Armstrong’s axioms of functional dependency derive the following rules: $\{ x \rightarrow y, \: wy \rightarrow z \} \mid= xw \rightarrow z$ (Note: $x \rightarrow y$ denotes $y$ is functionally dependent on $x$, $z \subseteq y$ denotes $z$ is subset of $y$, and $\mid =$ means derives).
4 votes
1 answer
17
Using Armstrong’s axioms of functional dependency derive the following rules: $\{ x \rightarrow y, \: x \rightarrow z \} \mid= x \rightarrow yz$ (Note: $x \rightarrow y$ denotes $y$ is functionally dependent on $x$, $z \subseteq y$ denotes $z$ is subset of $y$, and $\mid =$ means derives).
6 votes
1 answer
18
What are the three axioms of functional dependency for the relational databases given by Armstrong.
5 votes
4 answers
19
A number of processes could be in a deadlock state if none of them can execute due to non-availability of sufficient resources. Let $P_i, 0 \leq i \leq 4$ represent five processes and let there be four resources types $r_j, 0 \leq j \leq 3$. Suppose the following data structures have been used ... Is the system currently in a safe state? If yes, explain why.
7 votes
2 answers
20
Given below is solution for the critical section problem of two processes $P_0$ and $P_1$ sharing the following variables: var flag :array [0..1] of boolean; (initially false) turn: 0 .. 1; The program below is for process Pi (i=0 or 1) where ... i]:=false; until false Determine of the above solution is correct. If it is incorrect, demonstrate with an example how it violates the conditions.
0 votes
1 answer
21
Translate the executable statements of the following Pascal Program into quadruples. Assume that integer and real values require four words each. repeat flag[i]:=true; while turn !=i do begin while flag[j] do skip turn:=i; end critical section flag[i]:=false; until false Program Test; var i:integer; a: array [1...10] of real; begin i:=0; While i:<=10 do begin a[i]:=0; i:=i+1 end; end.
0 votes
3 answers
22
Consider the following grammar: $S \rightarrow S$ $S \rightarrow SS \mid a \mid \epsilon$ Indicate the shift-reduce and reduce-reduce conflict (if any) in the various states of the LR(0) parser.
6 votes
2 answers
23
Consider the following grammar: $S \rightarrow S$ $S \rightarrow SS \mid a \mid \epsilon$ Construct the collection of sets of LR (0) items for this grammar and draw its goto graph.
7 votes
1 answer
24
In the program scheme given below indicate the instructions containing any operand needing relocation for position independent behaviour. Justify your answer. ...
1 vote
0 answers
25
The code for the implementation of a sub-routine to convert positive numeric data from binary to appropriate character string in a $PDP-11$ like machine has been given below Note-that $SP$ is the stack pointer and $R_i$ represents $i^{th}$ ...
2 votes
3 answers
26
The following program fragment was written in an assembly language for a single address computer with one accumulator register: LOAD B MULT C STORE T1 ADD A STORE T2 MULT T2 ADD T1 STORE Z Give the arithmetic expression implemented by the fragment.
0 votes
0 answers
27
Consider the following Ada program: Procedure P is BAD-FORMAT: exception Procedure Q is begin ... if S/='b' then raise BAD-FORMAT end if; ... end Q; Procedure R is begin Q; exception when BAD-Format => ... handler body 1 end R; begin R; Q; exception when BAD-FORMAT => ... handler body 2 end P; Under what conditions are the two handler bodies 1 and 2 executed?
0 votes
0 answers
28
Write a LISP function to compute the product of all the numbers in a list. Assume that the list contains only number.
3 votes
2 answers
29
Consider the two program segments below: for i:=1 to f(x) by 1 do S end i:=1; While i<=f(x) do S i:=i+1 end Under what conditions are these two programs equivalent? Treat $S$ as any sequence of statement and f as a function.
2 votes
1 answer
30
Consider the procedure declaration: Procedure P (k: integer) where the parameter passing mechanism is call-by-value-result. Is it correct if the call, P (A[i]), where A is an array and i an integer, is implemented as below. create a new local variable, say z; assign to ... the body of P using z for k; set A [i] to z; Explain your answer. If this is incorrect implementation, suggest a correct one.