Recent questions tagged gatecse-2014-set3

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 variable...

Consider the following relational schema:employee (empId,empName,empDept) customer (custId,custName,salesRepId,rating) salesRepId is a foreign key referring to empId of t...

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)...

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 plana...

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\r...

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 ...

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 th...

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 ...

The value of the integral given below is$$\int \limits_0^{\pi} \: x^2 \: \cos x\:dx$$$-2\pi$$\pi$$-\pi$$2\pi$

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 cycle...

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 ...

An instruction pipeline has five stages, namely, instruction fetch (IF), instruction decode and register fetch (ID/RF), instruction execution (EX), memory access (MEM), a...

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) { in...

Consider the pseudocode given below. The function $DoSomething()$ takes as argument a pointer to the root of an arbitrary tree represented by the $leftMostChild-rightSibl...

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 unfi...

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$...

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 cla...

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-s...

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 = ...

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 g...

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 abo...

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$ an...

An operating system uses shortest remaining time first scheduling algorithm for pre-emptive scheduling of processes. Consider the following set of processes with their ar...

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 nev...

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 h...

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...

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\t...

Every host in an $\textsf{IPv4}$ network has a $1\text{-second}$ resolution real-time clock with battery backup. Each host needs to generate up to $1000$ unique identifie...

An IP router implementing Classless Inter-domain Routing (CIDR) receives a packet with address $131.23.151.76$. The router's routing table has the following entries:$$\be...