search
Log In
GATE 1990 Computer Science questions

Recent questions tagged gate1990

8 votes
3 answers
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.
asked Feb 12, 2018 in Digital Logic jothee 1.1k views
11 votes
2 answers
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 ___________.
asked Nov 27, 2016 in Digital Logic makhdoom ghaya 1.3k views
2 votes
2 answers
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.
asked Nov 27, 2016 in Set Theory & Algebra makhdoom ghaya 418 views
0 votes
0 answers
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)$
asked Nov 27, 2016 in Mathematical Logic makhdoom ghaya 211 views
18 votes
2 answers
5
Express $T(n)$ in terms of the harmonic number $H_{n}= \sum_{t=1}^{n} 1/i, 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$ ?
asked Nov 27, 2016 in Algorithms makhdoom ghaya 1.3k views
0 votes
0 answers
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.
asked Nov 26, 2016 in Compiler Design makhdoom ghaya 226 views
18 votes
1 answer
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
asked Nov 26, 2016 in Compiler Design makhdoom ghaya 1.8k views
2 votes
0 answers
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...$
asked Nov 26, 2016 in Theory of Computation makhdoom ghaya 268 views
15 votes
2 answers
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$
asked Nov 26, 2016 in Theory of Computation makhdoom ghaya 993 views
1 vote
0 answers
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.
asked Nov 26, 2016 in Algorithms makhdoom ghaya 292 views
1 vote
1 answer
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?
asked Nov 26, 2016 in Algorithms makhdoom ghaya 608 views
7 votes
2 answers
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.
asked Nov 26, 2016 in DS makhdoom ghaya 1.1k views
3 votes
1 answer
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.
asked Nov 25, 2016 in Algorithms makhdoom ghaya 465 views
0 votes
0 answers
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.
asked Nov 25, 2016 in Algorithms makhdoom ghaya 296 views
4 votes
3 answers
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); }
asked Nov 25, 2016 in Algorithms makhdoom ghaya 597 views
0 votes
2 answers
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;
asked Nov 25, 2016 in Compiler Design makhdoom ghaya 467 views
11 votes
4 answers
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$.
asked Nov 24, 2016 in Databases makhdoom ghaya 1.5k views
16 votes
1 answer
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);
asked Nov 24, 2016 in Databases makhdoom ghaya 793 views
11 votes
1 answer
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.
asked Nov 24, 2016 in Operating System makhdoom ghaya 1k views
1 vote
0 answers
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.
asked Nov 24, 2016 in Operating System makhdoom ghaya 408 views
3 votes
1 answer
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.
asked Nov 24, 2016 in Digital Logic makhdoom ghaya 506 views
3 votes
1 answer
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$
asked Nov 24, 2016 in CO and Architecture makhdoom ghaya 482 views
10 votes
1 answer
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.
asked Nov 24, 2016 in Operating System makhdoom ghaya 2.3k views
40 votes
5 answers
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?
asked Nov 24, 2016 in Operating System makhdoom ghaya 7.3k views
26 votes
1 answer
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?
asked Nov 24, 2016 in CO and Architecture makhdoom ghaya 5.5k views
16 votes
4 answers
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.
asked Nov 24, 2016 in Digital Logic makhdoom ghaya 1.5k views
14 votes
5 answers
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.
asked Nov 24, 2016 in Digital Logic makhdoom ghaya 1.1k views
16 votes
3 answers
28
Find the minimum product of sums of the following expression $f=ABC + \bar{A}\bar{B}\bar{C}$
asked Nov 24, 2016 in Digital Logic makhdoom ghaya 1.6k views
9 votes
2 answers
29
State whether the following statements are TRUE or FALSE with reason: The Link-load-and-go loading scheme required less storage space than the link-and-go loading scheme.
asked Nov 24, 2016 in Compiler Design makhdoom ghaya 1.8k views
4 votes
0 answers
30
State whether the following statements are TRUE or FALSE with reason: Transferring data in blocks from the main memory to the cache memory enables an interleaved main memory unit to operate at its maximum speed.
asked Nov 24, 2016 in CO and Architecture makhdoom ghaya 1.1k views
...