The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
GATE Overflow
Facebook Login
or
Email or Username
Password
Remember
Login
Register

I forgot my password
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
First time here? Checkout the
FAQ
!
x
×
Close
Use the google search bar on side panel. It searches through all previous GATE/other questions. For hardcopy of previous year questions please see
here
Recent questions tagged gate1996
+1
vote
1
answer
1
GATE199624b
Consider the synchronous sequential circuit in the below figure Given that the initial state of the circuit is S$_4$, identify the set of states, which are not reachable.
asked
Feb 10, 2018
in
Digital Logic
by
jothee
Veteran
(
115k
points)

402
views
gate1996
normal
digitallogic
circuitoutput
+19
votes
2
answers
2
GATE199627
A library relational database system uses the following schema USERS (User#, User Name, Home Town) BOOKS (Book#, Book Title, Author Name) ISSUED (Book#, User#, Date) Explain in one English sentence, what each of the following relational algebra queries is designed to ...
asked
Oct 10, 2014
in
Databases
by
Kathleen
Veteran
(
59.9k
points)

1.1k
views
gate1996
databases
relationalalgebra
normal
+16
votes
2
answers
3
GATE199626
A computer system has a three level memory hierarchy, with access time and hit ratios as shown below: Level $1$ (Cache memory) Access time $= 50$ $nsec/byte$ Size Hit Ratio $8 \ M$ byte $0.80$ $16 \ M$ byte $0.90$ $64 \ M$ byte $0.95$ ... average access time of less than $100 nsec$? What is the average access time achieved using the chosen sizes of level $1$ and level $2$ memories?
asked
Oct 10, 2014
in
CO & Architecture
by
Kathleen
Veteran
(
59.9k
points)

2.9k
views
gate1996
coandarchitecture
cachememory
normal
+20
votes
4
answers
4
GATE199625
A hard disk is connected to a $50$ MHz processor through a DMA controller. Assume that the initial setup of a DMA transfer takes $1000$ clock cycles for the processor, and assume that the handling of the interrupt at DMA completion requires $500$ clock cycles for the processor. ... Kbytes 0.98 16 Kbytes 0.90 16 Kbytes 0.99 64 Kbytes 0.95 64 Kbytes 0.995 Size Hit Ratio 250 M bytes 1.0
asked
Oct 10, 2014
in
CO & Architecture
by
Kathleen
Veteran
(
59.9k
points)

2.9k
views
gate1996
coandarchitecture
iohandling
dma
normal
+10
votes
2
answers
5
GATE199624a
Consider the synchronous sequential circuit in the below figure Draw a state diagram, which is implemented by the circuit. Use the following names for the states corresponding to the values of flipflops as given below. Q1 Q2 Q3 State 0 0 0 S$_0$ 0 0 1 S$_1$             1 1 1 S$_7$
asked
Oct 10, 2014
in
Digital Logic
by
Kathleen
Veteran
(
59.9k
points)

1.5k
views
gate1996
digitallogic
circuitoutput
normal
+20
votes
2
answers
6
GATE199623
A file system with a onelevel directory structure is implemented on a disk with disk block size of $4K$ bytes. The disk is used as follows: Diskblock $0$ File Allocation Table, consisting of one 8bit entry per data block, representing the data block address of ... $3$ Datablock $2$; etc. What is the maximum possible number of files? What is the maximum possible file size in blocks
asked
Oct 10, 2014
in
Operating System
by
Kathleen
Veteran
(
59.9k
points)

2.6k
views
gate1996
operatingsystem
disks
normal
filesystem
+17
votes
4
answers
7
GATE199622
A computer system uses the Banker's Algorithm to deal with deadlocks. Its current state is shown in the table below, where $P0$, $P1$, $P2$ are processes, and $R0$, $R1$, $R2$ are resources types. Maximum Need Current Allocation Available R0 R1 R2 R0 R1 R2 R0 ... that the system can be in this state What will the system do on a request by process $P0$ for one unit of resource type $R1$?
asked
Oct 10, 2014
in
Operating System
by
Kathleen
Veteran
(
59.9k
points)

1.6k
views
gate1996
operatingsystem
resourceallocation
normal
+25
votes
1
answer
8
GATE199621
The concurrent programming constructs fork and join are as below: Fork <label> which creates a new process executing from the specified label Join <variable> which decrements the specified synchronization variable (by $1$) and terminates the process if the new value is not $0$. Show the ... join $N$ $S3$ $L2$ : join $M$ $S5$ $L3:S2$ Goto $L1$ $L4:S4$ Goto $L2$ Next:
asked
Oct 10, 2014
in
Operating System
by
Kathleen
Veteran
(
59.9k
points)

1.9k
views
gate1996
operatingsystem
processsynchronization
normal
+13
votes
2
answers
9
GATE199620
Consider the syntaxdirected translation schema (SDTS) shown below: $E\rightarrow E + E$ {print “+”} $E\rightarrow E * E$ {print “.”} $E\rightarrow id$ {print id.name} $E\rightarrow (E)$ An LRparser executes ... the corresponding production. Draw the parse tree and write the translation for the sentence. $(a+b)*(c+d)$, using SDTS given above.
asked
Oct 10, 2014
in
Compiler Design
by
Kathleen
Veteran
(
59.9k
points)

736
views
gate1996
compilerdesign
syntaxdirectedtranslation
normal
+3
votes
1
answer
10
GATE199619
Consider the following program in pseudoPascal syntax. What is printed by the program if parameter $a$ in procedure test1 is passed as callbyreference parameter callbyvalueresult parameter program Example (input, output) var b: integer; procedure test2: begin b:=10; end procedure test1 (a: ... ('point 2: ', a, b); end begin (*Example*) b:=3; test1(b); writeln('point3: ', b); end
asked
Oct 10, 2014
in
Programming
by
Kathleen
Veteran
(
59.9k
points)

377
views
gate1996
programming
parameterpassing
normal
outofsyllabusnow
+14
votes
2
answers
11
GATE199618
Consider the following program that attempts to locate an element $x$ in an array $a[ ]$ using binary search. Assume $N > 1$. The program is erroneous. Under what conditions does the program fail? var i,j,k: integer; x: integer; a: array; [1..N] of integer; begin i:= 1; j:= ... (i >= j); if (a[k] = x) then writeln ('x is in the array') else writeln ('x is not in the array') end;
asked
Oct 10, 2014
in
Algorithms
by
Kathleen
Veteran
(
59.9k
points)

795
views
gate1996
algorithms
searching
normal
+15
votes
5
answers
12
GATE199617
Let $G$ be the directed, weighted graph shown in below figure We are interested in the shortest paths from $A$. Output the sequence of vertices identified by the Dijkstra’s algorithm for single source shortest path when the algorithm is started at node $A$ Write down sequence of vertices in the shortest path from $A$ to $E$ What is the cost of the shortest path from $A$ to $E$?
asked
Oct 10, 2014
in
Algorithms
by
Kathleen
Veteran
(
59.9k
points)

1.7k
views
gate1996
algorithms
graphalgorithms
normal
+10
votes
1
answer
13
GATE199616
A complete, undirected, weighted graph $G$ is given on the vertex $\{0, 1,\dots, n 1\}$ for any fixed ‘n’. Draw the minimum spanning tree of $G$ if the weight of the edge $(u, v)$ is $\mid uv\mid$ the weight of the edge $(u, v)$ is $u + v$
asked
Oct 10, 2014
in
Algorithms
by
Kathleen
Veteran
(
59.9k
points)

870
views
gate1996
algorithms
graphalgorithms
spanningtree
normal
+16
votes
3
answers
14
GATE199615
Insert the characters of the string $K \ R \ P \ C \ S \ N \ Y \ T \ J \ M$ into a hash table of size $10$. Use the hash function $h(x)=( ord (x) – ord ("a") + 1) \mod 10$ and linear probing to resolve collisions. Which insertions cause collisions? Display the final hash table.
asked
Oct 10, 2014
in
DS
by
Kathleen
Veteran
(
59.9k
points)

1.7k
views
gate1996
datastructure
hashing
normal
+17
votes
2
answers
15
GATE199614
A two dimensional array $A[1..n][1..n]$ of integers is partially sorted if $\forall i, j\in [1..n1], A[i][j] < A[i][j+1] \text{ and } A[i][j] < A[i+1][j]$ Fill in the blanks: The smallest item in the array is at $A[i][j]$ where $i=__$ and $j=__$. The smallest ... do if A[i+1][j] < A[i][j] ___ then begin A[i][j]:=A[i+1][j]; i:=i+1; end else begin _____ end A[i][j]:= ____ end
asked
Oct 10, 2014
in
Algorithms
by
Kathleen
Veteran
(
59.9k
points)

1.3k
views
gate1996
algorithms
sorting
normal
+11
votes
2
answers
16
GATE199613
Let $Q=\left( \left\{q_1,q_2 \right\}, \left\{a,b\right \}, \left\{a,b,\bot \right\}, \delta, \bot, \phi \right)$ be a pushdown automaton accepting by empty stack for the language which is the set of all nonempty even palindromes over the set $\left\{a,b\right\}$. ... $\delta(q_2,b,b) = \left\{(q_2, \epsilon)\right\}$ $\delta(q_2,\epsilon,\bot) = \left\{(q_2, \epsilon)\right\}$
asked
Oct 10, 2014
in
Theory of Computation
by
Kathleen
Veteran
(
59.9k
points)

697
views
gate1996
theoryofcomputation
pushdownautomata
normal
+18
votes
1
answer
17
GATE199612
Given below are the transition diagrams for two finite state machines $M_1$ and $M_2$ recognizing languages $L_1$ and $L_2$ respectively. Display the transition diagram for a machine that recognizes $L_1.L_2$, obtained from transition diagrams for $M_1$ and $M_2$ ... $\varepsilon$ transitions and no new states. (Final states are enclosed in double circles).
asked
Oct 10, 2014
in
Theory of Computation
by
Kathleen
Veteran
(
59.9k
points)

1.2k
views
gate1996
theoryofcomputation
finiteautomata
normal
+21
votes
5
answers
18
GATE199611
Let $G$ be a contextfree grammar where $G=(\{S, A, B, C\}, \{a, b, d\}, P, S)$ with the productions in $P$ given below. $S \rightarrow ABAC$ $A \rightarrow aA \mid \varepsilon$ $B \rightarrow bB \mid \varepsilon$ $C \rightarrow d$ ... no $\varepsilon$ productions and no unit productions. (A unit production is of the form $x \rightarrow y$, and $x$ and $y$ are non terminals).
asked
Oct 10, 2014
in
Compiler Design
by
Kathleen
Veteran
(
59.9k
points)

1.1k
views
gate1996
compilerdesign
grammar
normal
+10
votes
3
answers
19
GATE199610
Let $A = \begin{bmatrix} a_{11} && a_{12} \\ a_{21} && a_{22} \end{bmatrix} \text { and } B = \begin{bmatrix} b_{11} && b_{12} \\ b_{21} && b_{22} \end{bmatrix}$ be two matrices such that $AB=I$. Let $C = A \begin{bmatrix} 1 && 0 \\ 1 && 1 \end{bmatrix}$ and $CD =I$. Express the elements of $D$ in terms of the elements of $B$.
asked
Oct 10, 2014
in
Linear Algebra
by
Kathleen
Veteran
(
59.9k
points)

602
views
gate1996
linearalgebra
matrices
normal
descriptive
+1
vote
1
answer
20
GATE19969
The Fibonacci sequence $\{f_1, f_2, f_3 \dots f_n\}$ is defined by the following recurrence: $f_{n+2} = f_{n+1} + f_n, n \geq 1; f_2 =1:f_1=1$ Prove by induction that every third element of the sequence is even.
asked
Oct 10, 2014
in
Set Theory & Algebra
by
Kathleen
Veteran
(
59.9k
points)

243
views
gate1996
settheory&algebra
recurrence
proof
+19
votes
3
answers
21
GATE19968
Let $F$ be the collection of all functions $f: \{1, 2, 3\} \to \{1, 2, 3\}$. If $f$ and $g \in F$, define an equivalence relation $\sim$ by $f\sim g$ if and only if $f(3) = g(3)$. Find the number of equivalence classes defined by $\sim$. Find the number of elements in each equivalence class.
asked
Oct 10, 2014
in
Set Theory & Algebra
by
Kathleen
Veteran
(
59.9k
points)

1.4k
views
gate1996
settheory&algebra
relations
functions
normal
descriptive
+17
votes
1
answer
22
GATE19967
A demand paged virtual memory system uses $16$ bit virtual address, page size of $256$ bytes, and has $1$ Kbyte of main memory.$LRU$ page replacement is implemented using the list, whose current status (page number is decimal) is For each hexadecimal address in the ... $010D$, $10FF$, $11B0$ indicate the new status of the list page faults, if any, and page replacements, if any.
asked
Oct 10, 2014
in
Operating System
by
Kathleen
Veteran
(
59.9k
points)

2k
views
gate1996
operatingsystem
virtualmemory
normal
0
votes
1
answer
23
GATE19966
An 8052 based system has an output port with address 00H. Consider the following assembly language program. ORG 0100H MVI A, 00H LXI H, 0105H OUT 00H INR A PCHL HLT What does the program do with respect to the output port $00H$ ? Show the waveforms at the three least significant bits of the port $00H$.
asked
Oct 9, 2014
in
CO & Architecture
by
Kathleen
Veteran
(
59.9k
points)

265
views
gate1996
coandarchitecture
8085
outofsyllabusnow
+12
votes
2
answers
24
GATE19965
A logic network has two data inputs $A$ and $B$, and two control inputs $C_0$ and $C_1$. It implements the function $F$ according to the following table. $C_1$ $C_2$ $F$ 0 0 $\overline{A+B}$ 0 1 $A + B$ 1 0 $A \oplus B$ Implement the circuit using one 4 to 1 Multiplexer, one 2input Exclusive OR gate, one 2input AND gate, one 2input OR gate and one Inverter.
asked
Oct 9, 2014
in
Digital Logic
by
Kathleen
Veteran
(
59.9k
points)

858
views
gate1996
digitallogic
normal
digitalcircuits
+25
votes
4
answers
25
GATE19964
A binary search tree is used to locate the number $43$. Which of the following probe sequences are possible and which are not? Explain. (a) $61$ $52$ $14$ $17$ $40$ $43$ (b) $2$ $3$ $50$ $40$ $60$ $43$ (c) $10$ $65$ $31$ $48$ $37$ $43$ (d) $81$ $61$ $52$ $14$ $41$ $43$ (e) $17$ $77$ $27$ $66$ $18$ $43$
asked
Oct 9, 2014
in
DS
by
Kathleen
Veteran
(
59.9k
points)

4.5k
views
gate1996
datastructure
binarysearchtree
normal
+13
votes
2
answers
26
GATE19963
Let $f$ be a function defined by $f(x) = \begin{cases} x^2 &\text{ for }x \leq 1\\ ax^2+bx+c &\text{ for } 1 < x \leq 2 \\ x+d &\text{ for } x>2 \end{cases}$ Find the values for the constants $a$, $b$, $c$ and $d$ so that $f$ is continuous and differentiable everywhere on the real line.
asked
Oct 9, 2014
in
Calculus
by
Kathleen
Veteran
(
59.9k
points)

1.1k
views
gate1996
calculus
continuity
differentiability
normal
descriptive
+20
votes
3
answers
27
GATE19962.25
A micro program control unit is required to generate a total of $25$ control signals. Assume that during any micro instruction, at most two control signals are active. Minimum number of bits required in the control word to generate the required control signals will be: $2$ $2.5$ $10$ $12$
asked
Oct 9, 2014
in
CO & Architecture
by
Kathleen
Veteran
(
59.9k
points)

5.8k
views
gate1996
coandarchitecture
microprogramming
normal
+10
votes
4
answers
28
GATE19962.24
What is the equivalent Boolean expression in productofsums form for the Karnaugh map given in Fig $B\overline{D} + \overline{B}D$ $(B + \overline{C} +D) (\overline{B} + C + \overline{D})$ $(B + {D})(\overline{B} +\overline{ D})$ $(B + \overline{D})(\overline{B} + {D})$
asked
Oct 9, 2014
in
Digital Logic
by
Kathleen
Veteran
(
59.9k
points)

1.4k
views
gate1996
digitallogic
kmap
easy
+26
votes
2
answers
29
GATE19962.23
Consider the following state table for a sequential machine. The number of states in the minimized machine will be Input $0$ $1$ Present State A $D, 0$ $B, 1$ B $A, 0$ $C, 1$ C $A, 0$ $B, 1$ D $A, 1$ $C, 1$ Next state, Output $4$ $3$ $2$ $1$
asked
Oct 9, 2014
in
Theory of Computation
by
Kathleen
Veteran
(
59.9k
points)

2.7k
views
gate1996
theoryofcomputation
normal
finiteautomata
+16
votes
1
answer
30
GATE19962.22
Consider the circuit in figure. $f$ implements $\overline{A} \overline{B}C + \overline{A}B \overline{C} + ABC$ $A + B + C$ $A \oplus B \oplus C$ $AB + BC + CA$
asked
Oct 9, 2014
in
Digital Logic
by
Kathleen
Veteran
(
59.9k
points)

2.2k
views
gate1996
digitallogic
circuitoutput
easy
multiplexer
Page:
1
2
3
next »
Quick search syntax
tags
tag:apple
author
user:martin
title
title:apple
content
content:apple
exclude
tag:apple
force match
+apple
views
views:100
score
score:10
answers
answers:2
is accepted
isaccepted:true
is closed
isclosed:true
Recent Posts
Need suggestions for what to do next after Gate ??
For GATECSE Admissions 2019
Challenge to GATE keys: Question 26, If you also want to challenge the same, as I did!
How to follow Standard Textbooks?
Gate contest link is now open
Follow @csegate
Recent questions tagged gate1996
Recent Blog Comments
Well it is quite nostalgic for me as if I have...
See in recent posts "For GATE CSE Admissions 2019"
which ppt are you referring to, can you share the...
I am not a ranker so you might not believe on my...
What is the status on appsgate website? I...
47,932
questions
52,335
answers
182,384
comments
67,815
users