Recent questions tagged gate1996

4 votes

1 answer

1

GATE1996-24-b
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.

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 jothee 1.1k views

27 votes

2 answers

2

GATE1996-27
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 ...

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 determine ...

asked Oct 10, 2014 in Databases Kathleen 2.8k views

30 votes

3 answers

3

GATE1996-26
A computer system has a three-level memory hierarchy, with access time and hit ratios as shown below: $\overset{ \text {Level $1$ (Cache memory)} \\ \text{Access time = $ ... time of less than $100 nsec$? What is the average access time achieved using the chosen sizes of level $1$ and level $2$ memories?

A computer system has a three-level memory hierarchy, with access time and hit ratios as shown below: $\overset{ \text {Level $1$ (Cache memory)} \\ \text{Access time = $ ... 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 and Architecture Kathleen 7.7k views

31 votes

4 answers

4

GATE1996-25
A hard disk is connected to a $50$ MHz processor through a DMA controller. Assume that the initial set-up 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 ... . What fraction of the processor time is consumed by the disk, if the disk is actively transferring $100\%$ of the time?

A hard disk is connected to a $50$ MHz processor through a DMA controller. Assume that the initial set-up 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 ... K bytes. What fraction of the processor time is consumed by the disk, if the disk is actively transferring $100\%$ of the time?

asked Oct 10, 2014 in CO and Architecture Kathleen 5.9k views

15 votes

2 answers

5

GATE1996-24-a
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 flip-flops as given below. ... $} \\\hline \end{array}$

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 flip-flops as given below. ... $} \\\hline \end{array}$

asked Oct 10, 2014 in Digital Logic Kathleen 3.2k views

33 votes

2 answers

6

GATE1996-23
A file system with a one-level directory structure is implemented on a disk with disk block size of $4K$ ... What is the maximum possible number of files? What is the maximum possible file size in blocks

A file system with a one-level directory structure is implemented on a disk with disk block size of $4K$ ... What is the maximum possible number of files? What is the maximum possible file size in blocks

asked Oct 10, 2014 in Operating System Kathleen 5.4k views

19 votes

4 answers

7

GATE1996-22
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$ ... 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$?

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$ ... $P0$ for one unit of resource type $R1$?

asked Oct 10, 2014 in Operating System Kathleen 4.1k views

32 votes

1 answer

8

GATE1996-21
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:

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 precedence graph for $S1$, ... $N$ $S3$ $L2$ : join $M$ $S5$ $L3:S2$ Goto $L1$ $L4:S4$ Goto $L2$ Next:

asked Oct 10, 2014 in Operating System Kathleen 3.6k views

16 votes

2 answers

9

GATE1996-20
Consider the syntax-directed 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 LR-parser executes ... the corresponding production. Draw the parse tree and write the translation for the sentence. $(a+b)*(c+d)$, using SDTS given above.

Consider the syntax-directed 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 LR-parser executes the actions associated with ... 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 Kathleen 1.9k views

3 votes

1 answer

10

GATE1996-19
Consider the following program in pseudo-Pascal syntax. What is printed by the program if parameter $a$ in procedure test1 is passed as call-by-reference parameter call-by-value-result 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

Consider the following program in pseudo-Pascal syntax. What is printed by the program if parameter $a$ in procedure test1 is passed as call-by-reference parameter call-by-value-result parameter program Example (input, output) var b: integer; procedure test2: begin b:=10; end procedure test1 (a:integer ... ('point 2: ', a, b); end begin (*Example*) b:=3; test1(b); writeln('point3: ', b); end

asked Oct 10, 2014 in Programming Kathleen 809 views

17 votes

2 answers

11

GATE1996-18
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;

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:= n; repeat k: ... x) or (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 Kathleen 1.6k views

19 votes

6 answers

12

GATE1996-17
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$?

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 Kathleen 3.7k views

17 votes

1 answer

13

GATE1996-16
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 u-v\mid$ the weight of the edge $(u, v)$ is $u + v$

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 u-v\mid$ the weight of the edge $(u, v)$ is $u + v$

asked Oct 10, 2014 in Algorithms Kathleen 3k views

18 votes

4 answers

14

GATE1996-15
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.

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 Kathleen 3.3k views

27 votes

2 answers

15

GATE1996-14
A two dimensional array $A[1..n][1..n]$ of integers is partially sorted if $\forall i, j\in [1..n-1], 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

A two dimensional array $A[1..n][1..n]$ of integers is partially sorted if $\forall i, j\in [1..n-1], 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 item is deleted. ... __) 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 Kathleen 3k views

13 votes

2 answers

16

GATE1996-13
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\}$

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\}$. Below is ... $\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 Kathleen 2.7k views

32 votes

1 answer

17

GATE1996-12
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).

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$ by adding ... $(L_1.L_2)^*$ by adding only $\varepsilon$ transitions and no new states. (Final states are enclosed in double circles).

asked Oct 10, 2014 in Theory of Computation Kathleen 3.6k views

31 votes

5 answers

18

GATE1996-11
Let $G$ be a context-free 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).

Let $G$ be a context-free 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$ ($\varepsilon$ ... has 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 Kathleen 3.8k views

12 votes

4 answers

19

GATE1996-10
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$.

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 Kathleen 1.6k views

1 vote

1 answer

20

GATE1996-9
The Fibonacci sequence $\{f_1, f_2, f_3 \ldots 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.

The Fibonacci sequence $\{f_1, f_2, f_3 \ldots 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 Combinatory Kathleen 617 views

28 votes

5 answers

21

GATE1996-8
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.

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 Kathleen 2.9k views

30 votes

2 answers

22

GATE1996-7
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.

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 address ... $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 Kathleen 4.1k views

0 votes

1 answer

23

GATE1996-6
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$.

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 and Architecture Kathleen 419 views

16 votes

2 answers

24

GATE1996-5
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. ${\begin{array}{|cc|c|}\hline \textbf{$C_1$}& \textbf{$ ... one $4$ to $1$ Multiplexer, one $2-$input Exclusive OR gate, one $2-$input AND gate, one $2-$input OR gate and one Inverter.

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. ${\begin{array}{|cc|c|}\hline \textbf{$C_1$}& \textbf{$C_2$}& \textbf{F}\\\hline 0&0&\text{$ ... using one $4$ to $1$ Multiplexer, one $2-$input Exclusive OR gate, one $2-$input AND gate, one $2-$input OR gate and one Inverter.

asked Oct 9, 2014 in Digital Logic Kathleen 2k views

39 votes

4 answers

25

GATE1996-4
A binary search tree is used to locate the number $43$ ...

A binary search tree is used to locate the number $43$ ...

asked Oct 9, 2014 in DS Kathleen 12.6k views

19 votes

2 answers

26

GATE1996-3
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.

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 Kathleen 2.4k views

28 votes

5 answers

27

GATE1996-2.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$

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 and Architecture Kathleen 16.2k views

15 votes

4 answers

28

GATE1996-2.24
What is the equivalent Boolean expression in product-of-sums 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})$

What is the equivalent Boolean expression in product-of-sums 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 Kathleen 4.5k views

37 votes

3 answers

29

GATE1996-2.23
Consider the following state table for a sequential machine. The number of states in the minimized machine will be ... $4$ $3$ $2$ $1$

Consider the following state table for a sequential machine. The number of states in the minimized machine will be ... $4$ $3$ $2$ $1$

asked Oct 9, 2014 in Theory of Computation Kathleen 6.4k views

22 votes

2 answers

30

GATE1996-2.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$

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 Kathleen 5.5k views

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

GO Book for GATECSE 2022

Subjects

Network Sites

Recent questions tagged gate1996

Log In

Register

GO Book for GATECSE 2022

Recent Posts

Subjects

Recent Blog Comments

Network Sites

Recent questions tagged gate1996