search
Log In

Recent questions tagged gate2014-3

29 votes
6 answers
1
Let $\oplus$ denote the exclusive OR (XOR) operation. Let '1' and '0' denote the binary constants. Consider the following Boolean expression for $F$ over two variables $P$ and $Q$ ... $F$ is $P+Q$ $\overline{P+Q}$ $P \oplus Q$ $\overline {P \oplus Q}$
asked Sep 28, 2014 in Digital Logic jothee 4k views
28 votes
7 answers
2
Consider the following relational schema: employee (empId,empName,empDept) customer (custId,custName,salesRepId,rating) salesRepId is a foreign key referring to empId of the employee relation. Assume that each employee makes a sale to at least one customer. What does the ... of their customers having a 'GOOD' rating. Names of all the employees with all their customers having a 'GOOD' rating.
asked Sep 28, 2014 in Databases jothee 5.8k views
23 votes
10 answers
3
The CORRECT formula for the sentence, "not all Rainy days are Cold" is $\forall d (\text{Rainy}(d) \wedge \text{~Cold}(d))$ $\forall d ( \text{~Rainy}(d) \to \text{Cold}(d))$ $\exists d(\text{~Rainy}(d) \to \text{Cold}(d))$ $\exists d(\text{Rainy}(d) \wedge \text{~Cold}(d))$
asked Sep 28, 2014 in Mathematical Logic jothee 3k views
15 votes
2 answers
4
Let $\delta$ denote the minimum degree of a vertex in a graph. For all planar graphs on $n$ vertices with $\delta \geq 3$, which one of the following is TRUE? In any planar embedding, the number of faces is at least $\frac{n}{2}+2$ In any planar embedding, the number of faces ... is less than $\frac{n}{2}+2$ There is a planar embedding in which the number of faces is at most $\frac {n}{\delta+1}$
asked Sep 28, 2014 in Graph Theory jothee 3.2k views
43 votes
11 answers
5
If $G$ is the forest with $n$ vertices and $k$ connected components, how many edges does $G$ have? $\left\lfloor\frac {n}{k}\right\rfloor$ $\left\lceil \frac{n}{k} \right\rceil$ $n-k$ $n-k+1$
asked Sep 28, 2014 in Graph Theory jothee 6.9k views
49 votes
4 answers
6
There are two elements $x,\:y$ in a group $(G,*)$ such that every element in the group can be written as a product of some number of $x$'s and $y$'s in some order. It is known that $x*x=y*y=x*y*x*y=y*x*y*x=e$ where $e$ is the identity element. The maximum number of elements in such a group is ____.
asked Sep 28, 2014 in Set Theory & Algebra jothee 6.5k views
52 votes
4 answers
7
Consider the set of all functions $f:\{0,1, \dots,2014\} \to \{0,1,\dots, 2014\}$ such that $ f\left(f\left(i\right)\right)=i$, for all $0 \leq i \leq 2014$. Consider the following statements: $P$. For each such function it must be the case that for every $i,f(i) = i$. ... one of the following is CORRECT? $P, Q$ and $R$ are true Only $Q$ and $R$ are true Only $P$ and $Q$ are true Only $R$ is true
asked Sep 28, 2014 in Set Theory & Algebra jothee 6.5k views
22 votes
4 answers
8
Let $S$ be a sample space and two mutually exclusive events $A$ and $B$ be such that $A \cup B = S$. If $P(.)$ denotes the probability of the event, the maximum value of $P(A)P(B)$ is_____.
asked Sep 28, 2014 in Probability jothee 3.3k views
22 votes
4 answers
9
The value of the integral given below is $\int \limits_0^{\pi} \: x^2 \: \cos x\:dx$ $-2\pi$ $\pi$ $-\pi$ $2\pi$
asked Sep 28, 2014 in Calculus jothee 2.9k views
5 votes
1 answer
10
With respect to the numerical evaluation of the definite integral, $K = \int \limits_a^b \:x^2 \:dx$, where $a$ and $b$ are given, which of the following statements is/are TRUE? The value of $K$ obtained using the trapezoidal rule is always greater than or equal ... using the Simpson's rule is always equal to the exact value of the definite integral. I only II only Both I and II Neither I nor II
asked Sep 28, 2014 in Numerical Methods jothee 1.4k views
22 votes
5 answers
11
The above synchronous sequential circuit built using JK flip-flops is initialized with $Q_2Q_1Q_0 = 000$. The state sequence for this circuit for the next $3$ clock cycles is $001, 010, 011$ $111, 110, 101$ $100, 110, 111$ $100, 011, 001$
asked Sep 28, 2014 in Digital Logic jothee 6k views
45 votes
4 answers
12
The memory access time is $1$ $nanosecond$ for a read operation with a hit in cache, $5$ $nanoseconds$ for a read operation with a miss in cache, $2$ $nanoseconds$ for a write operation with a hit in cache and $10$ $nanoseconds$ for a write operation ... operations. The cache hit-ratio is $0.9$. The average memory access time (in nanoseconds) in executing the sequence of instructions is ______.
asked Sep 28, 2014 in CO and Architecture jothee 10.7k views
36 votes
7 answers
13
An instruction pipeline has five stages, namely, instruction fetch (IF), instruction decode and register fetch (ID/RF), instruction execution (EX), memory access (MEM), and register writeback (WB) with stage latencies $1$ ns, $2.2 $ ns, $2$ ns, $1$ ns, and $0.75$ ... times of this program on the old and the new design are $P$ and $Q$ nanoseconds, respectively. The value of $P/Q$ is __________.
asked Sep 28, 2014 in CO and Architecture jothee 9.4k views
39 votes
8 answers
14
Consider the C function given below. Assume that the array $listA$ contains $n (>0)$ elements, sorted in ascending order. int ProcessArray(int *listA, int x, int n) { int i, j, k; i = 0; j = n-1; do { k = (i+j)/2; if (x <= listA[k]) j = k-1; ... $listA$. It will return −$1$ even when $x$ is present in $listA$.
asked Sep 28, 2014 in DS jothee 5.9k views
36 votes
5 answers
15
Consider the pseudocode given below. The function $DoSomething()$ takes as argument a pointer to the root of an arbitrary tree represented by the $leftMostChild-rightSibling$ representation. Each node of the tree is of type $treeNode$. typedef struct treeNode* treeptr; struct ... tree. height of the tree. number of nodes without a right sibling in the tree. number of leaf nodes in the tree
asked Sep 28, 2014 in DS jothee 8.2k views
29 votes
3 answers
16
Consider a hash table with $100$ slots. Collisions are resolved using chaining. Assuming simple uniform hashing, what is the probability that the first $3$ slots are unfilled after the first $3$ insertions? $(97 \times 97 \times 97) / 100^3$ $(99 \times 98 \times 97) / 100^3$ $(97 \times 96 \times 95) / 100^3$ $(97 \times 96 \times 95 / (3! \times 100^3)$
asked Sep 28, 2014 in DS jothee 7.8k views
77 votes
6 answers
17
Suppose we have a balanced binary search tree $T$ holding $n$ numbers. We are given two numbers $L$ and $H$ and wish to sum up all the numbers in $T$ that lie between $L$ and $H$. Suppose there are $m$ such numbers in $T$. If the tightest upper bound on the time to compute the sum is $O(n^a\log^bn+m^c\log^dn)$, the value of $a+10b+100c+1000d$ is ______.
asked Sep 28, 2014 in DS jothee 14.5k views
9 votes
3 answers
18
Consider the decision problem $2CNFSAT$ defined as follows: $\left\{ \phi \mid \phi \text{ is a satisfiable propositional formula in CNF with at most two literals per clause}\right\}$ ... polynomial time by reduction to directed graph reachability. solvable in constant time since any input instance is satisfiable. NP-hard but not NP-complete.
asked Sep 28, 2014 in Theory of Computation jothee 1.7k views
43 votes
3 answers
19
Suppose you want to move from $0$ to $100$ on the number line. In each step, you either move right by a unit distance or you take a shortcut. A shortcut is simply a pre-specified pair of integers $i,\:j \:\text{with}\: i <j$. Given a shortcut $(i,j)$, if you are at position $i$ on the ... $15$. Let $y$ and $z$ be such that $T(9) = 1 + \min(T(y),T(z))$. Then the value of the product $yz$ is _____.
asked Sep 28, 2014 in Algorithms jothee 4k views
22 votes
3 answers
20
Consider the following languages over the alphabet $\sum = \{0, 1, c\}$ $L_1 = \left\{0^n1^n\mid n \geq 0\right\}$ $L_2 = \left\{wcw^r \mid w \in \{0,1\}^*\right\}$ $L_3 = \left\{ww^r \mid w \in \{0,1\}^*\right\}$ Here, ... the reverse of the string $w$. Which of these languages are deterministic Context-free languages? None of the languages Only $L_1$ Only $L_1$ and $L_2$ All the three languages
asked Sep 28, 2014 in Theory of Computation jothee 2.8k views
24 votes
3 answers
21
Which one of the following problems is undecidable? Deciding if a given context-free grammar is ambiguous. Deciding if a given string is generated by a given context-free grammar. Deciding if the language generated by a given context-free grammar is empty. Deciding if the language generated by a given context-free grammar is finite.
asked Sep 28, 2014 in Theory of Computation jothee 3k views
49 votes
5 answers
22
Consider the basic block given below. a = b + c c = a + d d = b + c e = d - b a = e + b The minimum number of nodes and edges present in the DAG representation of the above basic block respectively are $6$ and $6$ $8$ and $10$ $9$ and $12$ $4$ and $4$
asked Sep 28, 2014 in Compiler Design jothee 12.8k views
29 votes
2 answers
23
Consider a paging hardware with a $TLB$. Assume that the entire page table and all the pages are in the physical memory. It takes $10$ milliseconds to search the $TLB$ and $80$ milliseconds to access the physical memory. If the $TLB$ hit ratio is $0.6$, the effective memory access time (in milliseconds) is _________.
asked Sep 28, 2014 in Operating System jothee 5.6k views
13 votes
3 answers
24
An operating system uses shortest remaining time first scheduling algorithm for pre-emptive scheduling of processes. Consider the following set of processes with their arrival times and CPU burst times (in milliseconds): ... The average waiting time (in milliseconds) of the processes is ______.
asked Sep 28, 2014 in Operating System jothee 2.7k views
17 votes
5 answers
25
A system contains three programs and each requires three tape units for its operation. The minimum number of tape units which the system must have such that deadlocks never arise is _________.
asked Sep 28, 2014 in Operating System jothee 4.8k views
41 votes
3 answers
26
Consider the relational schema given below, where eId of the relation dependent is a foreign key referring to empId of the relation employee. Assume that every employee has at least one associated dependent in the dependent relation. employee (empId, empName, empAge) ... whose age is greater than that of some dependent. all dependents. some of his/her dependents. all of his/her dependents.
asked Sep 28, 2014 in Databases jothee 4.7k views
21 votes
2 answers
27
Consider the transactions $T1, T2, \:\text{and} \:T3$ and the schedules $S1 \:\text{and} \:S2$ given below. $T1: r1(X); r1(Z); w1(X); w1(Z) $ $T2: r2(Y); r2(Z); w2(Z) $ $T3: r3(Y); r3(X); w3(Y) $ ... schedules is TRUE? Only $S1$ is conflict-serializable. Only $S2$ is conflict-serializable. Both $S1$ and $S2$ are conflict-serializable. Neither $S1$ nor $S2$ is conflict-serializable.
asked Sep 28, 2014 in Databases jothee 3.4k views
38 votes
9 answers
28
An $IP$ router with a $\text{Maximum Transmission Unit (MTU)}$ of $1500$ bytes has received an $IP$ packet of size $4404\text{ bytes}$ with an $IP$ header of length $20\text{ bytes}$. The values of the relevant fields in the header of the third $IP$ fragment generated by the ... $1,$ Datagram Length$: 1500;$ Offset$: 370$ $\text{MF bit}$: $0,$ Datagram Length$: 1424;$ Offset$: 2960$
asked Sep 28, 2014 in Computer Networks jothee 9.2k views
54 votes
8 answers
29
Every host in an IPv4 network has a $1-second$ resolution real-time clock with battery backup. Each host needs to generate up to $1000$ unique identifiers per second. Assume that each host has a globally unique IPv4 address. Design a $50-bit$ globally unique ID for this purpose. After what period (in seconds) will the identifiers generated by a host wrap around?
asked Sep 28, 2014 in Computer Networks jothee 9.8k views
34 votes
6 answers
30
An IP router implementing Classless Inter-domain Routing (CIDR) receives a packet with address $131.23.151.76$ ... The identifier of the output interface on which this packet will be forwarded is ______.
asked Sep 28, 2014 in Computer Networks jothee 7k views
...