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 following query return?
SELECT empName
FROM employee E
WHERE NOT EXISTS (SELECT custId
FROM customer C
WHERE C. salesRepId = E. empId
AND C. rating < > ‘GOOD’)
The outer query will return the value (names of employees) for a tuple in relation E, only if inner query for that tuple will return no tuple (usage of NOT EXISTS).
The inner query will run for every tuple of outer query. It selects cust-id for an employee e, if rating of customer is NOT good. Such an employee should not be selected in the output of outer query.
So the query will return the names of all those employees whose all customers have GOOD rating.
Consider the set of all functions f : {0,1,…..,2014} → {0,1,…..,2014} such that f(f(i)) = I, for 0 ≤ i ≤ 2014. Consider the following statements.
P. For each such function it must be the case that for every i, f(i) = i,
Q. For each such function it must be the case that for some i, f(i) = i,
R. Each such function must be onto.
Which one of the following is CORRECT ?
Let us consider a function (counter example) as
f(0) = 1, f(1) = 0, f(2) = 3, f(3) = 2,…..f(2012) = 2013,
f(2013) = 2012 and f(2014) = 2014
Clearly f(f(i)) = i for 0 ≤ i ≤ 2014
Here f(i) Â i for every i and f(i) = i for some i
Also f is onto
Hence, only Q and R are true.
The value of the integral given below is
= (π2 sinπ + 2πcosπ – 2sinπ) – (0 + 0 + 0) = –2π
With respect to the numerical evaluation of the definite integral, , where a and b are given, which of the following statements is/are TRUE ?
(I) The value of K obtained using the trapezoidal rule is always greater than or equal to the exact value of the definite integral.
(II) The value of K obtained using the Simpson’s rule is always equal to the exact value of the definite integral.
Let a = 0, b = 1
Let n = 4
c
I. By Trapezoidal rule
II. By Simpson’s rule
Exact value
The above synchronous sequential circuit built using JK flip-flops is initialized with
Q2Q1Q0 = 000 The state sequence for this circuit for the next 3 clock cycles is
Consider the pseudocode given below. The function Dosomething () takes as argument a pointer to the root of an arbitrary tree represented by the left Most Child-right Sibling representation. Each node of the tree is of type tree Node.
Typedef struct treeNode* treeptr;
Struct treeNode
{
Treeptr leftMostchild, rightSibling;
};
Int Dosomething (treeptr tree)
Int value = 0;
if (tree! = NULL) {
If (tree → leftMostchild):
Value = value + Dosomething (tree → rightsibiling);
}
Return (value);
When the pointer to the root of a tree is passed as the argument to DoSomething, the value returned by the function corresponds to the
The key to solving such questions is to understand or detect where/by what condition the value (or the counter) is getting incremented each time.
Here, that condition is if (tree → leftMostchild == Null)
Which means if there is no left most child of the tree (or the sub-tree or the current nodeas called in recursion)
⇒ Which means there is no child to that particular node (since if there is no left most child, there is no child at all).
⇒ Which means the node under consideration is a leaf node.
⇒ The function recursively counts, and adds to value, whenever a leaf node is encountered.
⇒ The function returns the number of leaf nodes in the tree.
Consider the decision problem 2CNFSAT defined as follows:
{ϕ | ϕ} is a satisfiable propositional formula in CNF with at most two literal per clause}
For example, is a Boolean formula and it is in 2CNFSAT.
The decision problem 2CNFSAT is
2 SAT is in P. This we can prove by reducing 2 SAT to directed graph reachability problem which is known to be in P.
Procedure for reducing 2 SAT to reachability problem:
1. Let ϕ be CNF with clauses of length 2 and let P be the set of propositional variables(literals) in ϕ
2. Build a graph G = (V, E) with and (x, y) ϵ E if there is a clause in ϕ that is equivalent to x → y (all the clauses are converted to equivalent implications and the graph built is called as implication graph)
3. Observe that ϕ is unsatisfiable if there is a p ϵ P such that there is both a path from and from in G.
This condition can be tested by running the reachability algorithm several times.
Which one of the following problems is undecidable?
There were algorithms to find the membership of CFG (using CYK algorithm) and finiteness of CFG (using CNF graph) and emptiness. But there is no algorithm for ambiguity of CFG, so it is undecidable.
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
The given basic block can be written as
a = b + c a = b + c
c = a + d c = b + c + d
d = b + c ⇒ d = b + b + c + d = 2b + c + d
a = e + b a = b + b + c + d = 2b + c + d
From above simplification it is visible that e is same as c and final value of a is same as d. So the final basic block can be written as follows:
d = 2b + c + d
e = c
a = d
The DAG generated for the above basic block in as
Maximum number of modes and edges in above DAG is (6, 6)
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)
dependent (depId, eId, depName, depAge)
Consider the following relational algebra query
π empId (employee) — πempId (employee (empId = eID) ^ (emp ≤ Age depAge) dependent)
The above query evaluates to the set of empIds of employees whose age is greater than that of
Part A of the above given relational algebra query will give the set of empIds of those employees whose age is less than or equal to the age of some of his/her dependents. Now when set of empIds of all employees minus set of empIds obtained from part A is done, then we get the set of empIds of employees whose age is greater than that of all his/her dependents.