# Recent questions tagged gate2000 1
Let $G$ be an undirected graph. Consider a depth-first traversal of $G$, and let $T$ be the resulting depth-first search tree. Let $u$ be a vertex in $G$ and let $v$ be the first new (unvisited) vertex visited after visiting $u$ in the traversal. Which of the following statement is always true? ... a leaf in $T$ If $\{u, v\}$ is not an edge in $G$ then $u$ and $v$ must have the same parent in $T$
2
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 pair of ... one transaction since it was created. To simplify your query, break it up into 2 steps by defining an intermediate view V.
3
(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,.....10 are inserted, in order, into the tree. Show the tree pictorially after 6 insertions, and after all 10 insertions Do NOT ... . Then what approximately is the average number of keys in each leaf level node. in the normal case, and with the insertion as in (b).
4
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. L1: int R = 0, W = 0; Reader () ... (mutex); ...../*do the write*/ wait( mutex); W=0; signal (mutex); } b. Can the above solution lead to starvation of writers?
5
Consider the syntax directed translation scheme (SDTS) given in the following. Assume attribute evaluation with bottom-up parsing, i.e., attributes are evaluated immediately after a reduction. E$\rightarrow$ E$_{1}$ * T {E.val = E$_{1}$ ... modify the SDTS given, without changing the grammar, to find $E.red$, the number of reductions performed while reducing an input to $E$.
6
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); end begin x : ... mechanism 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?
7
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 needed to sort ... worst case? Give an ordering of elements in the above array so that the minimum number of swaps needed to sort the array is maximum.
8
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 == 1)return 1; ... values. 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)?$
9
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 = count + 1; q[ ... Show that if $set(i)$ has not been called for some $i$, then regardless of what $p[i]$ contains, $is\_set(i)$ will return false.
10
Consider the line $y=\frac{n}{m}x$, where $n$ and $m$ ... s - n*r)⊏⊐ 0 then clash:= true; 7: if(m*q - n*p)⊏⊐ 0 and (m*s - n*r)⊏⊐ 0 then clash:= true; 8: end;
11
Suppose a stack implementation supports, in addition to PUSH and POP, an operation REVERSE, which reverses the order of the elements on the stack. To implement a queue using the above stack implementation, show how to implement ENQUEUE using a single operation and DEQUEUE using a sequence of $3$ operations. The ... $5 \ 2 * 3 \ 4 +$ After evaluating $5 \ 2 * 3 \ 4 + 5 \ 2$ At the end of evaluation
12
An instruction pipeline has five stages where each stage take 2 nanoseconds and all instruction use all five stages. Branch instructions are not overlapped. i.e., the instruction after the branch is not fetched till the branch instruction is completed. Under ... , and 50% of the conditional branch instructions are such that the branch is taken, calculate the average instruction execution time.
13
Consider the following 8085 program segment, where registers B and C contain BCD values: S1: MVI A, 99H MVI D, 00H SUB C ADD B DAA S2: JC S3 MOV E, A MVI A, 99H SUB E MOV E, A JZ S4 MVI D, FFH JMP S4 S3:INC A DAA MOV E, A S4: ......... For the two ... the values in register D and E when control reaches S4. What, in general, is the value of D and E as a function of B and C when control reaches S4?
14
Consider the 8085 instruction IN 09H stored as follows: Memory Address Machine Code 3050 3051 DA 09 and the following incomplete timing diagram for the instruction: Write the contents of the boxes, A, B, C and D in hexadecimal in your answer sheet. Do not draw any ... to put the data on the bus? Answer by completing the following statement in your answer book: By combining signals.........
15
Design a logic circuit to convert a single digit BCD number to the number modulo six as follows (Do not detect illegal input): Write the truth table for all bits. Label the input bits $I_1, I_2, \ldots$ with $I_1$ as the least significant bit. Label the output bits ... truth. Draw one circuit for each output bit using, altogether, two two-input AND gates, one two-input OR gate and two NOT gates.
16
A push down automation (pda) is given in the following extended notation of finite state diagram: The nodes denote the states while the edges denote the moves of the pda. The edge labels are of the form $d$, $s/s'$ where $d$ is the input symbol read and $s, s'$ are the stack ... states in the above notation that accept the language $\left\{0^{n}1^{m} \mid n \leq m \leq 2n\right\}$ by empty stack
17
Construct as minimal finite state machine that accepts the language, over $\{0,1\}$, of all strings that contain neither the sub string $00$ nor the sub string $11$. Consider the grammar S → aSAb S → ∊ A → bA A → ∊ where $S$, $A$ are non-terminal symbols with $S$ being the ... $i, j \geq 0$, where $i$ and $j$ satisfy some condition. What is the condition on the values of $i$ and $j$?
18
Let $S$ be a set of $n$ elements $\left\{1, 2,....., n\right\}$ and $G$ a graph with 2$^{n}$ vertices, each vertex corresponding to a distinct subset of $S$. Two vertices are adjacent iff the symmetric difference of the corresponding sets has exactly $2$ elements ... $G$ has the same degree. What is the degree of a vertex in $G$? How many connected components does $G$ have?
19
A multiset is an unordered collection of elements where elements may repeat any number of times. The size of a multiset is the number of elements in it, counting repetitions. What is the number of multisets of size $4$ that can be constructed from n distinct elements so that at least one element occurs exactly twice? How many multisets can be constructed from n distinct elements?
20
Let $S= \{0, 1, 2, 3, 4, 5, 6, 7\}$ and $⊗$ denote multiplication modulo $8,$ that is, $x ⊗ y= (xy) \mod 8$ Prove that $( \{ 0, 1\}, ⊗)$ is not a group. Write three distinct groups $(G, ⊗)$ where $G ⊂ S$ and $G$ has $2$ elements.
21
Consider the following sequence: $s_1 = s_2 = 1$ and $s_i = 1 + \min \left({s_{i-1}, s_{i-2}}\right) \text{ for } i > 2$. Prove by induction on $n$ that $s_n=⌈\frac{n}{2}⌉$.
22
In SQL, relations can contain null values, and comparisons with null values are treated as unknown. Suppose all comparisons with a null value are treated as false. Which of the following pairs is not equivalent? $x = 5 \quad not (not (x = 5))$ $x = 5 \quad x > 4$ and $x < 6,$ where $x$ is an integer $x ≠ 5 \quad not (x = 5)$ none of the above
23
Given relations r(w, x) and s(y, z) the result of select distinct w, x from r, s is guaranteed to be same as r, provided. r has no duplicates and s is non-empty r and s have no duplicates s has no duplicates and r is non-empty r and s have the same number of tuples
24
Given the following relation instance. ... $Z \rightarrow Y$ $YZ \rightarrow X$ and $Y \rightarrow Z$ $YZ \rightarrow X$ and $X \rightarrow Z$ $XZ \rightarrow Y$ and $Y \rightarrow X$
25
Which of the following is not a valid deadlock prevention scheme? Release all resources before requesting a new resource. Number the resources uniquely and never request a lower numbered resource than the last one requested. Never request a resource after releasing any resource. Request and all required resources be allocated before execution.
26
Suppose the time to service a page fault is on the average $10$ milliseconds, while a memory access takes $1$ microsecond. Then a $99.99\%$ hit ratio results in average memory access time of $1.9999$ milliseconds $1$ millisecond $9.999$ microseconds $1.9999$ microseconds
27
Given the following expression grammar: \begin{align} E &\to E * F \mid F + E \mid F \\[1em] F &\to F - F \mid id \end{align} Which of the following is true? $*$ has higher precedence than $+$ $-$ has higher precedence than $*$ $+$ and $-$ have same precedence $+$ has higher precedence than $*$
The value of $j$ at the end of the execution of the following C program: int incr (int i) { static int count = 0; count = count + i; return (count); } main () { int i, j; for (i = 0; i <= 4; i++) j = incr (i); } is: $10$ $4$ $6$ $7$
Let $G$ be an undirected connected graph with distinct edge weights. Let $e_{max}$ be the edge with maximum weight and $e_{min}$ the edge with minimum weight. Which of the following statements is false? Every minimum spanning tree of $G$ must contain $e_{min}$ ... spanning tree, then its removal must disconnect $G$ No minimum spanning tree contains $e_{max}$ $G$ has a unique minimum spanning tree
Consider the following functions $f(n) = 3n^{\sqrt{n}}$ $g(n) = 2^{\sqrt{n}{\log_{2}n}}$ $h(n) = n!$ Which of the following is true? $h(n)$ is $O(f(n))$ $h(n)$ is $O(g(n))$ $g(n)$ is not $O(f(n))$ $f(n)$ is $O(g(n))$