Recent questions tagged descriptive / GATE Overflow for GATE CSE

18 votes

5 answers

2641

GATE CSE 2002 | Question: 3
Let $A$ be a set of $n(>0)$ elements. Let $N_r$ be the number of binary relations on $A$ and let $N_f$ be the number of functions from $A$ to $A$ Give the expression for $N_r,$ in terms of $n.$ Give the expression for $N_f,$ terms of $n.$ Which is larger for all possible $n,N_r$ or $N_f$

Let $A$ be a set of $n(>0)$ elements. Let $N_r$ be the number of binary relations on $A$ and let $N_f$ be the number of functions from $A$ to $A$Give the expression for $...

Kathleen

4.2k views

Kathleen asked Sep 15, 2014

40 votes

1 answer

2642

GATE CSE 2002 | Question: 1.17
In the C language: At most one activation record exists between the current activation record and the activation record for the main The number of activation records between the current activation record and the activation records from the main ... record for the recursive function to be saved in a different stack before the recursive function can be called.

In the C language:At most one activation record exists between the current activation record and the activation record for the mainThe number of activation records betwee...

Kathleen

10.3k views

Kathleen asked Sep 15, 2014

8 votes

3 answers

2643

GATE CSE 2001 | Question: 22
We wish to construct a $B^+$ tree with fan-out (the number of pointers per node) equal to $3$ for the following set of key values: $80, 50, 10, 70, 30, 100, 90$ Assume that the tree is initially empty and the values are added in the order ... need not be shown. The key values $30$ and $10$ are now deleted from the tree in that order show the tree after each deletion.

We wish to construct a $B^+$ tree with fan-out (the number of pointers per node) equal to $3$ for the following set of key values:$80, 50, 10, 70, 30, 100, 90$Assume that...

Kathleen

4.9k views

Kathleen asked Sep 14, 2014

16 votes

2 answers

2644

GATE CSE 2001 | Question: 21-a
Consider a relation examinee (regno, name, score), where regno is the primary key to score is a real number. Write a relational algebra using $( \Pi, \sigma, \rho, \times)$ to find the list of names which appear more than once in examinee.

Consider a relation examinee (regno, name, score), where regno is the primary key to score is a real number.Write a relational algebra using $( \Pi, \sigma, \rho, \times)...

Kathleen

3.8k views

Kathleen asked Sep 14, 2014

40 votes

3 answers

2645

GATE CSE 2001 | Question: 20
Consider a disk with the $100$ tracks numbered from $0$ to $99$ rotating at $3000$ rpm. The number of sectors per track is $100$ and the time to move the head between two successive tracks is $0.2$ millisecond. Consider a set of disk ... at track $0$ and the elevator algorithm is used to schedule disk requests, what is the worse case time to complete all the requests?

Consider a disk with the $100$ tracks numbered from $0$ to $99$ rotating at $3000$ rpm. The number of sectors per track is $100$ and the time to move the head between two...

Kathleen

11.0k views

Kathleen asked Sep 14, 2014

35 votes

3 answers

2646

GATE CSE 2001 | Question: 19
Two concurrent processes $P1$ and $P2$ want to use resources $R1$ and $R2$ in a mutually exclusive manner. Initially, $R1$ and $R2$ ... . Exchange the statements $Q1$ and $Q3$ and statements $Q2$ and $Q4$. Is mutual exclusion guaranteed now? Can deadlock occur?

Two concurrent processes $P1$ and $P2$ want to use resources $R1$ and $R2$ in a mutually exclusive manner. Initially, $R1$ and $R2$ are free. The programs executed by the...

Kathleen

5.6k views

Kathleen asked Sep 14, 2014

20 votes

2 answers

2647

GATE CSE 2001 | Question: 18
Remove left-recursion from the following grammar: $S \rightarrow Sa \mid Sb \mid a \mid b$ Consider the following grammar: $S \rightarrow aSbS\mid bSaS \mid \epsilon$ Construct all possible parse trees for the string abab. Is the grammar ambiguous?

Remove left-recursion from the following grammar: $S \rightarrow Sa \mid Sb \mid a \mid b$Consider the following grammar: $S \rightarrow aSbS\mid bSaS \mid \...

Kathleen

3.7k views

Kathleen asked Sep 14, 2014

8 votes

1 answer

2648

GATE CSE 2001 | Question: 17
The syntax of the repeat-until statement is given by the following grammar $S \rightarrow\text{ repeat }S_1\text{ until }E$ where E stands for expressions, $S$ and $S_1$ stand for statements. The non-terminals $S$ and $S_1$ have an ... Use the operator '\\' to concatenate two strings and the function gen(s) to generate a line containing the string s.

The syntax of the repeat-until statement is given by the following grammar$S \rightarrow\text{ repeat }S_1\text{ until }E$where E stands for expressions, $S$ and $S_1$ st...

Kathleen

2.1k views

Kathleen asked Sep 14, 2014

23 votes

2 answers

2649

GATE CSE 2001 | Question: 16
Consider the following grammar with terminal alphabet $\Sigma =\{a,(,),+,* \}$ and start symbol $E$. The production rules of the grammar are: $ E \rightarrow aA$ $ E \rightarrow (E)$ $A \rightarrow +E$ $A \rightarrow *E$ $A \rightarrow \epsilon $ Compute the FIRST and FOLLOW sets for $E$ and $A$. Complete the LL(1) parse table for the grammar.

Consider the following grammar with terminal alphabet $\Sigma =\{a,(,),+,* \}$ and start symbol $E$. The production rules of the grammar are:$ E \rightarrow aA$$ E \right...

Kathleen

4.9k views

Kathleen asked Sep 14, 2014

29 votes

3 answers

2650

GATE CSE 2001 | Question: 15
Consider a weighted undirected graph with vertex set $V = \{n1, n2, n3, n4, n5, n6 \}$ ... all possible minimum spanning trees of a graph? Is the maximum among the edge weights of a minimum spanning tree unique over all possible minimum spanning tree of a graph?

Consider a weighted undirected graph with vertex set $V = \{n1, n2, n3, n4, n5, n6 \}$ and edge set $E = \{(n1,n2,2), (n1,n3,8), (n1,n6,3), (n2,n4,4), (n2,n5,12), (n3,n4,...

Kathleen

4.6k views

Kathleen asked Sep 14, 2014

33 votes

3 answers

2651

GATE CSE 2001 | Question: 14
Insert the following keys one by one into a binary search tree in the order specified.$15, 32, 20, 9, 3, 25, 12, 1$Show the final binary search tree after the insertions. Draw the binary search tree after deleting $15$ from it. Complete the statements $S1$ ... ; x = depth (t -> left); S1: ___________; S2: if (x > y) return __________; S3: else return _______; }

Insert the following keys one by one into a binary search tree in the order specified.$$15, 32, 20, 9, 3, 25, 12, 1$$Show the final binary search tree after the insertion...

Kathleen

7.0k views

Kathleen asked Sep 14, 2014

31 votes

2 answers

2652

GATE CSE 2001 | Question: 13
Consider the following C program: void abc(char*s) { if(s[0]=='\0')return; abc(s+1); abc(s+1); printf("%c",s[0]); } main() { abc("123"); } What will be the output of the program? If $abc(s)$ is called ... string $s$ of length $n$ characters (not counting the null ('\0') character), how many characters will be printed by $abc(s)$?

Consider the following C program:void abc(char*s) { if(s[0]=='\0')return; abc(s+1); abc(s+1); printf("%c",s[0]); } main() { abc("123"); }What will be the output of the pr...

Kathleen

11.2k views

Kathleen asked Sep 14, 2014

54 votes

2 answers

2653

GATE CSE 2001 | Question: 12
Consider a $5-$stage pipeline - IF (Instruction Fetch), ID (Instruction Decode and register read), EX (Execute), MEM (memory), and WB (Write Back). All (memory or register) reads take place in the second phase of a clock cycle ... Show all data dependencies between the four instructions. Identify the data hazards. Can all hazards be avoided by forwarding in this case.

Consider a $5-$stage pipeline - IF (Instruction Fetch), ID (Instruction Decode and register read), EX (Execute), MEM (memory), and WB (Write Back). All (memory or registe...

Kathleen

18.2k views

Kathleen asked Sep 14, 2014

24 votes

2 answers

2654

GATE CSE 2001 | Question: 11
A sequential circuit takes an input stream of $0's$ and $1's$ and produces an output stream of $0's$ and $1's.$ Initially it replicates the input on its output until two consecutive $0's$ are encountered on the input. From then ... Give the minimized sum-of-product expression for $\text{J}$ and $\text{K}$ inputs of one of its state flip-flops

A sequential circuit takes an input stream of $0's$ and $1's$ and produces an output stream of $0's$ and $1's.$ Initially it replicates the input on its output until two ...

Kathleen

5.3k views

Kathleen asked Sep 14, 2014

26 votes

6 answers

2655

GATE CSE 2001 | Question: 10
Is the $3\text{-variable}$ function $f= \Sigma(0,1,2,4)$ its self-dual? Justify your answer. Give a minimal product-of-sum form of the $b$ output of the following $\text{excess-3}$ to $\text{BCD}$ converter.

Is the $3\text{-variable}$ function $f= \Sigma(0,1,2,4)$ its self-dual? Justify your answer.Give a minimal product-of-sum form of the $b$ output of the following $\text{e...

Kathleen

4.1k views

Kathleen asked Sep 14, 2014

29 votes

2 answers

2656

GATE CSE 2001 | Question: 9
A CPU has $32-bit$ memory address and a $256 \ KB$ cache memory. The cache is organized as a $4-way$ set associative cache with cache block size of $16$ bytes. What is the number of sets in the cache? What is the size (in bits) of ... are required to find the byte offset within a cache block? What is the total amount of extra memory (in bytes) required for the tag bits?

A CPU has $32-bit$ memory address and a $256 \ KB$ cache memory. The cache is organized as a $4-way$ set associative cache with cache block size of $16$ bytes.What is the...

Kathleen

13.2k views

Kathleen asked Sep 14, 2014

44 votes

3 answers

2657

GATE CSE 2001 | Question: 8
Consider a disk with the following specifications: 20 surfaces, 1000 tracks/surface, 16 sectors/track, data density 1 KB/sector, rotation speed 3000 rpm. The operating system initiates the transfer between the disk and the memory sector-wise. Once the head ... What is the maximum percentage of time the CPU is held up for this disk I/O for cycle-stealing DMA transfer?

Consider a disk with the following specifications: 20 surfaces, 1000 tracks/surface, 16 sectors/track, data density 1 KB/sector, rotation speed 3000 rpm. The operating sy...

Kathleen

10.2k views

Kathleen asked Sep 14, 2014

32 votes

3 answers

2658

GATE CSE 2001 | Question: 7
Let a decision problem $X$ be defined as follows: $X$: Given a Turing machine $M$ over $\Sigma$ and any word $w \in \Sigma$, does $M$ loop forever on $w$? You may assume that the halting problem of Turing machine is undecidable but partially decidable. Show that $X$ is undecidable Show that $X$ is not even partially decidable

Let a decision problem $X$ be defined as follows:$X$: Given a Turing machine $M$ over $\Sigma$ and any word $w \in \Sigma$, does $M$ loop forever on $w$?You may assume th...

Kathleen

5.0k views

Kathleen asked Sep 14, 2014

18 votes

2 answers

2659

GATE CSE 2001 | Question: 6
Give a deterministic PDA for the language $L=\{a^ncb^{2n} \mid n \geq 1\}$ over the alphabet $\Sigma = \{a,b,c\}$. Specify the acceptance state.

Give a deterministic PDA for the language $L=\{a^ncb^{2n} \mid n \geq 1\}$ over the alphabet $\Sigma = \{a,b,c\}$. Specify the acceptance state.

Kathleen

5.2k views

Kathleen asked Sep 14, 2014

36 votes

2 answers

2660

GATE CSE 2001 | Question: 5
Construct DFA's for the following languages: $L=\left\{w \mid w \in \{a,b\}^*, \text{ w has baab as a substring } \right\}$ $L=\left\{w \mid w \in \{a,b\}^*, \text{ w has an odd number of a's and an odd number of b's } \right\} $

Construct DFA's for the following languages:$L=\left\{w \mid w \in \{a,b\}^*, \text{ w has baab as a substring } \right\}$$L=\left\{w \mid w \in \{a,b\}^*, \text{ w has ...

Kathleen

5.4k views

Kathleen asked Sep 14, 2014

15 votes

4 answers

2661

GATE CSE 2001 | Question: 4
Consider the function $h: N \times N \rightarrow N$ so that $h(a,b) = (2a +1)2^b - 1$, where $N=\{0,1,2,3,\dots\}$ is the set of natural numbers. Prove that the function $h$ is an injection (one-one). Prove that it is also a Surjection (onto)

Consider the function $h: N \times N \rightarrow N$ so that $h(a,b) = (2a +1)2^b - 1$, where $N=\{0,1,2,3,\dots\}$ is the set of natural numbers.Prove that the function $...

Kathleen

3.3k views

Kathleen asked Sep 14, 2014

11 votes

2 answers

2662

GATE CSE 2001 | Question: 3
Prove that powerset $(A \cap B) = \text{powerset}(A) \cap \text{powerset}(B)$ Let $\text{sum} (n) = 0 + 1 + 2 + ..... + n$ for all natural numbers n. Give an induction proof to show that the following equation is true for all natural numbers $m$ and $n$: $\text{sum}(m+n) = \text{sum}(m) + \text{sum}(n) + mn$

Prove that powerset $(A \cap B) = \text{powerset}(A) \cap \text{powerset}(B)$Let $\text{sum} (n) = 0 + 1 + 2 + ..... + n$ for all natural numbers n. Give an induction pro...

Kathleen

2.3k views

Kathleen asked Sep 14, 2014

6 votes

1 answer

2663

GATE CSE 2000 | Question: 22
Consider a bank database with only one relation transaction (transno, acctno, date, amount) The amount attribute value is positive for deposits and negative for withdrawals. Define an SQL view TP containing the information (acctno,T1.date,T2.amount) for every ... since it was created. To simplify your query, break it up into 2 steps by defining an intermediate view V.

Consider a bank database with only one relation transaction (transno, acctno, date, amount)The amount attribute value is positive for deposits and negative for withdrawa...

Kathleen

2.6k views

Kathleen asked Sep 14, 2014

12 votes

2 answers

2664

GATE CSE 2000 | Question: 21
(a) Suppose you are given an empty $B^+$ tree where each node (leaf and internal) can store up to $5$ key values. Suppose values $1, 2,\ldots 10$ are inserted, in order, into the tree. Show the tree pictorially after $6$ insertions, and ... what approximately is the average number of keys in each leaf level node. in the normal case, and with the insertion as in (b).

(a) Suppose you are given an empty $B^+$ tree where each node (leaf and internal) can store up to $5$ key values. Suppose values $1, 2,\ldots 10$ are inserted, in order, ...

Kathleen

4.0k views

Kathleen asked Sep 14, 2014

31 votes

4 answers

2665

GATE CSE 2000 | Question: 20
a. Fill in the boxes below to get a solution for the reader-writer problem, using a single binary semaphore, mutex (initialized to $1$) and busy waiting. Write the box numbers ($1$, $2$ and $3$), and their contents in your answer book. int R = 0, W = ... ...../*do the write*/ wait( mutex); W=0; signal (mutex); } b. Can the above solution lead to starvation of writers?

a. Fill in the boxes below to get a solution for the reader-writer problem, using a single binary semaphore, mutex (initialized to $1$) and busy waiting. Write the box nu...

Kathleen

9.9k views

Kathleen asked Sep 14, 2014

15 votes

3 answers

2666

GATE CSE 2000 | Question: 19
Consider the syntax directed translation scheme $\textsf{(SDTS)}$ ... given, without changing the grammar, to find $E.red$, the number of reductions performed while reducing an input to $E$.

Consider the syntax directed translation scheme $\textsf{(SDTS)}$ given in the following. Assume attribute evaluation with bottom-up parsing, i.e., attributes are evaluat...

Kathleen

8.3k views

Kathleen asked Sep 14, 2014

6 votes

2 answers

2667

GATE CSE 2000 | Question: 18
Consider the following program is pseudo-Pascal syntax program main; var x: integer; procedure Q (z: integer); begin z := z+x; writeln(z); end; procedure P (y: integer); var x: integer; begin x := y+2; Q(x); writeln(x); ... is call-by-value and the scope rule is static scoping? the parameter passing mechanism is call-by-reference and the scope rule is dynamic scoping?

Consider the following program is pseudo-Pascal syntaxprogram main; var x: integer; procedure Q (z: integer); begin z := z+x; writeln(z); end; procedure P (y: integer);...

Kathleen

3.1k views

Kathleen asked Sep 14, 2014

42 votes

6 answers

2668

GATE CSE 2000 | Question: 17
An array contains four occurrences of $0$, five occurrences of $1$, and three occurrences of $2$ in any order. The array is to be sorted using swap operations (elements that are swapped need to be adjacent). What is the minimum number of swaps ... ? Give an ordering of elements in the above array so that the minimum number of swaps needed to sort the array is maximum.

An array contains four occurrences of $0$, five occurrences of $1$, and three occurrences of $2$ in any order. The array is to be sorted using swap operations (elements t...

Kathleen

11.1k views

Kathleen asked Sep 14, 2014

26 votes

3 answers

2669

GATE CSE 2000 | Question: 16
A recursive program to compute Fibonacci numbers is shown below. Assume you are also given an array $f [ 0\ldots m]$ with all elements initialized to $0.$ fib(n) { if (n > M) error (); if (n == 0) return 1; if (n = ... Write the box number and the corresponding contents in your answer book. What is the time complexity of the resulting program when computing $fib(n)?$

A recursive program to compute Fibonacci numbers is shown below. Assume you are also given an array $f [ 0\ldots m]$ with all elements initialized to $0.$fib(n) { if (n ...

Kathleen

4.9k views

Kathleen asked Sep 14, 2014

21 votes

3 answers

2670

GATE CSE 2000 | Question: 15
Suppose you are given arrays $p [1......N]$ and $q [1......N]$ both uninitialized, that is, each location may contain an arbitrary value), and a variable count, initialized to $0$. Consider the following procedures $set$ and $is\_set$: set(i) { count ... $set(i)$ has not been called for some $i$, then regardless of what $p[i]$ contains, $is\_set(i)$ will return false.

Suppose you are given arrays $p [1......N]$ and $q [1......N]$ both uninitialized, that is, each location may contain an arbitrary value), and a variable count, initiali...

Kathleen

4.9k views

Kathleen asked Sep 14, 2014

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