search
Log In

Recent questions tagged gate2000

36 votes
5 answers
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$
asked Nov 16, 2014 in Algorithms Daggerhunt 7k views
2 votes
1 answer
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.
asked Sep 14, 2014 in Databases Kathleen 942 views
3 votes
1 answer
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).
asked Sep 14, 2014 in Databases Kathleen 1.1k views
24 votes
4 answers
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?
asked Sep 14, 2014 in Operating System Kathleen 3.3k views
14 votes
3 answers
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$.
asked Sep 14, 2014 in Compiler Design Kathleen 2.2k views
5 votes
2 answers
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?
asked Sep 14, 2014 in Programming Kathleen 1.4k views
27 votes
4 answers
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.
asked Sep 14, 2014 in Algorithms Kathleen 3.2k views
16 votes
3 answers
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)?$
asked Sep 14, 2014 in Programming Kathleen 1.6k views
14 votes
3 answers
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.
asked Sep 14, 2014 in DS Kathleen 1.8k views
19 votes
2 answers
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
asked Sep 14, 2014 in DS Kathleen 2.2k views
50 votes
7 answers
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.
asked Sep 14, 2014 in CO and Architecture Kathleen 6.5k views
6 votes
0 answers
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?
asked Sep 14, 2014 in CO and Architecture Kathleen 588 views
0 votes
0 answers
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.........
asked Sep 14, 2014 in CO and Architecture Kathleen 365 views
14 votes
2 answers
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.
asked Sep 14, 2014 in Digital Logic Kathleen 1.1k views
24 votes
3 answers
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
asked Sep 14, 2014 in Theory of Computation Kathleen 2k views
20 votes
2 answers
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$?
asked Sep 14, 2014 in Theory of Computation Kathleen 1.5k views
32 votes
5 answers
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?
asked Sep 14, 2014 in Set Theory & Algebra Kathleen 2.3k views
22 votes
5 answers
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?
asked Sep 14, 2014 in Combinatory Kathleen 2.2k views
20 votes
2 answers
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.
asked Sep 14, 2014 in Set Theory & Algebra Kathleen 1.2k views
6 votes
1 answer
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}⌉$.
asked Sep 14, 2014 in Set Theory & Algebra Kathleen 653 views
47 votes
4 answers
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
asked Sep 14, 2014 in Databases Kathleen 7.1k views
39 votes
2 answers
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
asked Sep 14, 2014 in Databases Kathleen 6.5k views
20 votes
5 answers
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$
asked Sep 14, 2014 in Databases Kathleen 3.5k views
22 votes
2 answers
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.
asked Sep 14, 2014 in Operating System Kathleen 5.6k views
22 votes
4 answers
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
asked Sep 14, 2014 in Operating System Kathleen 7.1k views
20 votes
3 answers
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 $*$
asked Sep 14, 2014 in Compiler Design Kathleen 5.4k views
17 votes
3 answers
28
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$
asked Sep 14, 2014 in Programming Kathleen 3.5k views
27 votes
5 answers
29
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
asked Sep 14, 2014 in Algorithms Kathleen 6.1k views
52 votes
9 answers
30
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))$
asked Sep 14, 2014 in Algorithms Kathleen 9.2k views
...