GATE 1990 Computer Science questions

Recent questions tagged gate1990

1
A 32-bit floating-point number is represented by a 7-bit signed exponent, and a 24-bit fractional mantissa. The base of the scale factor is 16, The range of the exponent is ___________, if the scale factor is represented in excess-64 format.
2
The condition for overflow in the addition of two $2's$ complement numbers in terms of the carry generated by the two most significant bits is ___________.
3
Show that the elements of the lattice $(N, \leq)$, where $N$ is the set of positive intergers and $a \leq b$ if and only if $a$ divides $b$, satisfy the distributive property.
4
Show, using resolution, that the following well-formed formula is valid for all interpretations: $\left(\forall x \forall y \left(f \left(x, y \right) \Leftarrow \neg y \left(y, x \right) = \left(\forall x \left(f \left(x, x \right)\right)$
5
Express $T(n)$ in terms of the harmonic number $\displaystyle H_{n}= \sum_{i=1}^{n} \frac{1}{i},\quad n \geq 1$, where $T(n)$ satisfies the recurrence relation, $T(n)=\frac{n+1}{n} T(n - 1)+1$, for $n \geq \sum$ and $T(1) = 1$ What is the asymptotic behaviour of $T(n)$ as a function of $n$ ?
6
Consider the grammar: $G_{2}$: Para $\rightarrow$ Sentence RP/Sentence RP $\rightarrow$ b Sentence RP | b Sentence Sentence $\rightarrow$ Word b Sentence| Word Word $\rightarrow$ letter *word | letter letter $\rightarrow$ id Where $id,,*,.b$ ar terminals Convert ... show how to use a stack algorithm to parse the following string$id*id.b id * id.$ The parse should generate a rightmost derivation.
7
Show that grammar $G1$ is ambiguous using parse trees: $G_{1}: S \rightarrow$ if S then S else S $S \rightarrow$ if S then S
8
Complete the following production rules which generate the language:$L= \left\{a^{n} b^{n} c^{n}\mid a, b, c \in \Sigma \right\}$ where variables $R$ and $Q$ are used to move back and forth over the current string generated $S \rightarrow aYc$ $Y \rightarrow a Yc\mid Q$ ... $Qc \rightarrow cQ$ $Q \rightarrow R'c$ $cR' \rightarrow ...$ $bR' \rightarrow ...$ $aR' \rightarrow a...$
9
Is the language generated by the grammar $G$ regular? If so, give a regular expression for it, else prove otherwise G: $S \rightarrow aB$ $B \rightarrow bC$ $C \rightarrow xB$ $C \rightarrow c$
1 vote
10
The following algorithm (written in pseudo-pascal) work on an undirected graph G program Explore (G) procedure Visit (u) begin if Adj (u) is not empty {comment:Adj (u) is the list of edges incident to u} then begin Select an edge from Adj (u); Let edge ... edges, given that each vertex can be accessed and removed from LIST in constant time. Also show that all edges of the graph are traversed.
11
Consider a hash table with chaining scheme for overflow handling: What is the worst-case timing complexity of inserting $n$ elements into such a table? For what type of instance does this hashing scheme take the worst-case time for insertion?
12
Consider the height-balanced tree $T_{t}$ with values stored at only the leaf nodes, shown in Fig.4. (i) Show how to merge to the tree, $T_{1}$ elements from tree $T_{2}$ shown in Fig.5 using node D of tree $T_{1}$. (ii) What is the time complexity of a merge ... $T_{1}$ and $T_{2}$ are of height $h_{1}$ and $h_{2}$ respectively, assuming that rotation schemes are given. Give reasons.
13
Consider the following problem. Given $n$ positive integers $a_{1}, a_{2}\dots a_n,$ it is required to partition them in to two parts $A$ and $B$ such that $|\sum_{i \in A} a_{i} - \sum_{i \in B} a_{i}|$ is minimised Consider a greedy algorithm ... in that part whose sum in smaller at that step. Give an example with $n=5$ for which the solution produced by the greedy algorithm is not optimal.
14
Consider the following instance of the $0 -1$ Knapsack problem: $\max 6X_{1} + 11X_{2} + 16X_{3} + 21X_{4} + 26X_{5}$ Subject to $4X_{1} + 8X_{2} + 12X_{3} + 16X_{4} + 20 X_{5} < 32$ and $X_{i}=0$ or $1$ for $i=1,\dots,5$. ... . Number the nodes in the tree in the order in which they are expanded and for each node show the bound on the partial solutions and the decision which leads to that node.
15
The following program computes values of a mathematical function $f(x)$. Determine the form of $f(x)$. main () { int m, n; float x, y, t; scanf ("%f%d", &x, &n); t = 1; y = 0; m = 1; do { t *= (-x/m); y += t; } while (m++ < n); printf ("The value of y is %f", y); }
16
What does the following program output? program module (input, output); var a:array [1...5] of integer; i, j: integer; procedure unknown (var b: integer, var c: integer); var i:integer; begin for i := 1 to 5 do a[i] := i; b:= 0; c := 0 for i := 1 to 5 do write (a[i]); writeln(); a[3]:=11; ... (c,b); b := 5; c := 6; end; begin i:=1; j:=3; unknown (a[i], a[j]); for i:=1 to 5 do write (a[i]); end;
17
One giga bytes of data are to be organized as an indexed-sequential file with a uniform blocking factor 8. Assuming a block size of 1 Kilo bytes and a block refrencing pointer size of $32$ bits, find out the number of levels of indexing that would be required ... also the size of the master index. The referencing capability (fanout ratio) per block of index storage may be considered to be $32$.
18
Consider the following relational database: employees (eno, ename, address, basic-salary) projects (pno, pname, nos-of-staffs-allotted) working (pno, eno, pjob) The queries regarding data in the above database are formulated below in SQL. Describe in ENGLISH sentences ... (*) FROM projects)) SELECT pname FROM projects WHERE pno IN (SELECT pno FROM projects MINUS SELECT DISTINCT pno FROM working);
19
Assuming the current disk cylinder to be $50$ and the sequence for the cylinders to be $1, 36, 49, 65, 53, 12, 3, 20, 55, 16, 65$ and $78$ find the sequence of servicing using Shortest seek time first (SSTF) and Elevator disk scheduling policies.
1 vote
20
Assume that an instruction test-and-set (TS) has been provided in a machine whose function is as follows: 'the left most bit of the one byte operand is checked and accordingly the condition code (CC) is set to $1$ or $0$. After checking and setting the condition code, implement a critical region using this instruction.
21
State the Booth's algorithm for multiplication of two numbers. Draw a block diagram for the implementation of the Booth's algorithm for determining the product of two 8-bit signed numbers.
22
A single bus CPU consists of four general purpose register, namely, $R0 ....... R3, ALU, MAR, MDR, PC, SP$ and $IR$ (Instruction Register). Assuming suitable microinstructions, write a microroutine for the instruction, $ADD R0, R1$
23
A certain moving arm disk-storage device has the following specifications: Number of tracks per surface=$404$ Track storage capacity=$130030$ bytes. Disk speed=$3600$ rpm Average seek time=$30$ m secs. Estimate the average latency, the disk storage capacity and the data transfer rate.
24
In a two-level virtual memory, the memory access time for main memory, $t_{M}=10^{-8}$ sec, and the memory access time for the secondary memory, $t_D=10^{-3}$ sec. What must be the hit ratio, $H$ such that the access efficiency is within $80$ percent of its maximum value?
25
A block-set associative cache memory consists of $128$ blocks divided into four block sets. The main memory consists of $16, 384$ blocks and each block contains $256$ eight bit words. How many bits are required for addressing the main memory? How many bits are needed to represent the TAG, SET and WORD fields?
26
For the synchronous counter shown in Fig.3, write the truth table of $Q_{0}, Q_{1}$,and $Q_{2}$ after each pulse, starting from $Q_{0}=Q_{1}=Q_{2}=0$ and determine the counting sequence and also the modulus of the counter.
27
Show with the help of a block diagram how the Boolean function : $f=AB+BC+CA$ can be realised using only a $4:1$ multiplexer.
Find the minimum product of sums of the following expression $f=ABC + \bar{A}\bar{B}\bar{C}$