search
Log In

Recent questions tagged gate1997

1 vote
0 answers
1
In this GATE ques- Part a) For Size balanced tree the recurrence (max height) is T(h)=T(h-1) +T(h-2) +1, solving which we get T(0)=1, T(1)=2,T(2)=1+2+1=4, T(3)=4+2+1=7 Here, T(0),T(1),T(2) are of the form 2h but T(3) is not equal to 23 then how can we claim that "size-balance binary tree of height 'h' contain at least 2h nodes." ?
asked Mar 14, 2018 in DS Mamta Satywali 329 views
8 votes
1 answer
2
Consider the following relational database schema: EMP (eno name, age) PROJ (pno name) INVOLVED (eno, pno) EMP contains information about employees. PROJ about projects and involved about which employees involved in which projects. The underlined attributes are the primary keys for the ... $E$ ($\rho$ is called the rename operator))
asked Feb 8, 2018 in Databases jothee 750 views
4 votes
1 answer
3
Let * be defined as x*y= x'+y. Let z = x*y. Value of z*x is (a) x +y (b) x (c) 0 (d) 1
asked Nov 29, 2017 in Digital Logic Prateek K 1.8k views
1 vote
0 answers
4
4 votes
0 answers
5
Which of the following is essential for converting an infix expression into postfix? a - An operator stack b - An operand stack c - both a and b d - A parse tree I understand that you do not require an operand stack; only operator stack can do the job. But don't the parse tree also qualify for the answer?
asked Jul 11, 2017 in DS Hardik1997 393 views
1 vote
3 answers
6
A computer has six tape drivers, with n processes competing for them. Each process may need two drivers. What is the maximum value of n for the system to be deadlock free? a] 6 b] 5 c] 4 d] 3
asked Jan 16, 2016 in Operating System Cruise Device 267 views
9 votes
3 answers
7
Consider the following relational database schema: EMP (eno name, age) PROJ (pno name) INVOLVED (eno, pno) EMP contains information about employees. PROJ about projects and involved about which employees involved in which projects. The underlined attributes are the primary keys ... which is equivalent to SQL query. select eno from EMP|INVOLVED where EMP.eno=INVOLVED.eno and INVOLVED.pno=3
asked Oct 15, 2015 in Databases jothee 1.6k views
30 votes
4 answers
8
An operating system handles requests to resources as follows. A process (which asks for some resources, uses them for some time and then exits the system) is assigned a unique timestamp are when it starts. The timestamps are monotonically increasing with time. Let us denote the timestamp of a ... ? If yes, show how. If not prove it. Can a process P ever starve? If yes, show how. If not prove it.
asked Oct 15, 2015 in Operating System jothee 3.1k views
26 votes
2 answers
9
A program $P$ reads and processes $1000$ consecutive records from a sequential file $F$ stored on device $D$ without using any file system facilities. Given the following Size of each record $= 3200$ bytes Access time of $D = 10$ ... organized using a blocking factor of $2$ (i.e., each block on D contains two records of $F$) and $P$ uses one buffer?
asked Oct 15, 2015 in Operating System jothee 3.3k views
4 votes
3 answers
10
A concurrent system consists of $3$ processes using a shared resource $R$ in a non-preemptible and mutually exclusive manner. The processes have unique priorities in the range $1 \dots 3$, $3$ being the highest priority. It is required to synchronize the processes such ... priority]:=true; else begin V(proceed [priority]); busy:=true; end V(mutex) Give the pseudo code for the procedure release_R.
asked Oct 15, 2015 in Operating System jothee 624 views
11 votes
1 answer
11
Following floating point number format is given $f$ is a fraction represented by a $6-bit$ mantissa (includes sign bit) in sign magnitude form, $e$ is a $4-bit$ exponent (includes sign hit) in sign magnitude form and $n=(f, e) = f. 2^e$ is a floating point ... point addition of $A$ and $B.$ What is the percentage error (up to one position beyond decimal point) in the addition operation in (b)?
asked Oct 15, 2015 in Digital Logic jothee 797 views
16 votes
1 answer
12
Let $f=(\bar{w} + y)(\bar{x} +y)(w+\bar{x}+z)(\bar{w}+z)(\bar{x}+z)$ Express $f$ as the minimal sum of products. Write only the answer. If the output line is stuck at $0$, for how many input combinations will the value of $f$ be correct?
asked Oct 15, 2015 in Digital Logic jothee 1k views
15 votes
1 answer
13
Following is a state table for time finite state machine. ... for the equivalent states. For example if states $X$ and $Y$ are equivalent then use $XY$ as the name for the equivalent state in the minimal machine).
asked Oct 15, 2015 in Theory of Computation jothee 2.1k views
0 votes
0 answers
14
asked Sep 29, 2014 in Others Kathleen 213 views
4 votes
0 answers
15
The language $L,$ defined by the following grammar, allows use of real or integer data in expressions and assignment statements. <assign-stmt> :: <LHS> := <E> <E> ::= <E> + <T>|<T> <T> ::= <T> * <V>|<V> <V> ::= id|(<E>) (LHS) :: ... the postfix form. You may assume that the name and type of variable can be obtained by making the function calls' give_name $(id)$ and give_type $(id)$ respectively.
asked Sep 29, 2014 in Compiler Design Kathleen 736 views
0 votes
0 answers
16
asked Sep 29, 2014 in Others Kathleen 122 views
27 votes
2 answers
17
Given that $L$ is a language accepted by a finite state machine, show that $L^P$ and $L^R$ are also accepted by some finite state machines, where $L^P = \left\{s \mid ss' \in L \text{ some string }s'\right\}$ $L^R = \left\{s \mid s \text{ obtained by reversing some string in }L\right\}$
asked Sep 29, 2014 in Theory of Computation Kathleen 1.9k views
17 votes
1 answer
18
Construct a finite state machine with minimum number of states, accepting all strings over $(a,b)$ such that the number of $a$'s is divisible by two and the number of $b$'s is divisible by three.
asked Sep 29, 2014 in Theory of Computation Kathleen 2.2k views
28 votes
4 answers
19
A $B^+$ - tree of order $d$ is a tree in which each internal node has between $d$ and $2 d$ key values. An internal node with $M$ key values has $M + 1$ children. The root (if it is an internal node) has between $1$ and $2d$ key values. The distance of a node from the ... tree of order $4$ with $52$ leaves? What is the minimum number of leaves in a $B^+$-tree of order $d$ and height $h(h\geq 1)$?
asked Sep 29, 2014 in Databases Kathleen 6.2k views
16 votes
3 answers
20
Consider the following piece of 'C' code fragment that removes duplicates from an ordered list of integers. Node *remove-duplicates (Node* head, int *j) { Node *t1, *t2; *j=0; t1 = head; if (t1! = NULL) t2 = t1 ->next; else return head; *j = ... number of times statements marked $S2$ get executed? What is the significance of the value in the integer pointed to by $j$ when the function completes?
asked Sep 29, 2014 in DS Kathleen 1.8k views
17 votes
2 answers
21
An array $A$ contains $n \geq 1$ positive integers in the locations $A[1], A[2], \dots A[n]$. The following program fragment prints the length of a shortest sequence of consecutive elements of $A$, $A[i], A[i+1], \dots,A[j]$ such that the sum of their values is $\geq M$, a given positive ... +1; sum:= ◻ end else begin if(j-i) < min then min:=j-i; sum:=sum -A[i]; i:=i+1; end writeln (min +1); end.
asked Sep 29, 2014 in DS Kathleen 1.5k views
16 votes
3 answers
22
A size-balanced binary tree is a binary tree in which for every node the difference between the number of nodes in the left and right subtree is at most $1$. The distance of a node from the root is the length of the path from the root to the node. The height of a ... tree of height $h \geqslant 1$, how many nodes are at distance $h-1$ from the root? Write only the answer without any explanations.
asked Sep 29, 2014 in DS Kathleen 1.6k views
7 votes
3 answers
23
Consider the following function. Function F(n, m:integer):integer; begin If (n<=0 or (m<=0) then F:=1 else F:F(n-1, m) + F(n, m-1); end; Use the recurrence relation ... What is the value of $F(n, m)$? How many recursive calls are made to the function $F$, including the original call, when evaluating $F(n, m)$.
asked Sep 29, 2014 in Algorithms Kathleen 937 views
11 votes
3 answers
24
Let $R$ be a reflexive and transitive relation on a set $A$. Define a new relation $E$ on $A$ as $E=\{(a, b) \mid (a, b) \in R \text{ and } (b, a) \in R \}$ Prove that $E$ is an equivalence relation on $A$. Define a relation $\leq$ on the equivalence classes of $E$ as $E_1 \leq E_2$ if $\exists a, b$ such that $a \in E_1, b \in E_2 \text{ and } (a, b) \in R$. Prove that $\leq$ is a partial order.
asked Sep 29, 2014 in Set Theory & Algebra Kathleen 1.2k views
27 votes
3 answers
25
Let $F$ be the set of one-to-one functions from the set $\{1, 2, \dots, n\}$ to the set $\{1, 2,\dots, m\}$ where $m\geq n\geq1$. How many functions are members of $F$? How many functions $f$ in $F$ satisfy the property $f(i)=1$ for some $i, 1\leq i \leq n$? How many functions $f$ in $F$ satisfy the property $f(i)<f(j)$ for all $i,j \ \ 1\leq i \leq j \leq n$?
asked Sep 29, 2014 in Set Theory & Algebra Kathleen 2.3k views
33 votes
6 answers
26
Consider a hash table with $n$ buckets, where external (overflow) chaining is used to resolve collisions. The hash function is such that the probability that a key value is hashed to a particular bucket is $\frac{1}{n}$. The hash table is initially empty and $K$ ... has occurred in any of the $K$ insertions? What is the probability that the first collision occurs at the $K^{th}$ insertion?
asked Sep 29, 2014 in DS Kathleen 3.9k views
17 votes
4 answers
27
Consider the grammar $S \rightarrow bSe$ $S \rightarrow PQR$ $P \rightarrow bPc$ $P \rightarrow \varepsilon$ $Q \rightarrow cQd$ $Q \rightarrow \varepsilon$ $R \rightarrow dRe$ $R \rightarrow \varepsilon$ where $S, P, Q, R$ are non-terminal symbols with $S$ being the start symbol ... $i, j, k, m$? Find the smallest string that has two parse trees.
asked Sep 29, 2014 in Compiler Design Kathleen 1.7k views
5 votes
1 answer
28
Consider the following program in Pseudo-Pascal syntax. program what: var z: integer procedure recur(x): begin if x <= 40 then begin x:x+z recur(x); z:=x+10 end end(*recur*) begin(*what*) z=10; recur(z); writeln(z) end Suppose the parameter ... value is printed by program? How many times is &lsquo;recur&rsquo; called? What value is printed by the program if the parameter is passed by reference?
asked Sep 29, 2014 in Programming Kathleen 1.1k views
23 votes
4 answers
29
Consider a graph whose vertices are points in the plane with integer co-ordinates $(x,y)$ such that $1 \leq x \leq n$ and $1 \leq y \leq n$, where $n \geq 2$ is an integer. Two vertices $(x_1, y_1)$ and $(x_2, y_2)$ are adjacent ... ? Write only the answer without any explanations. What is the weight of a maximum weight-spanning tree in this graph? Write only the answer without any explanations.
asked Sep 29, 2014 in Algorithms Kathleen 2.7k views
0 votes
0 answers
30
asked Sep 29, 2014 in Others Kathleen 170 views
...