What is the chromatic number of an n-vertex simple connected graph which does not contain any odd length cycle? Assume n ≥ 2

**A. ** 2

**B. ** 3

**C. ** n - 1

**D. ** n

**Answer : ****Option A**

**Explaination / Solution: **

No Explaination.

No Explaination.

Workspace

Report

The Gross Domestic Product (GDP) in Rupees grew at 7% during 2012-2013. For
international comparison, the GDP is compared in US Dollars (USD) after conversion based
on the market exchange rate. During the period 2012-2013 the exchange rate for the USD
increased from Rs. 50/ USD to Rs. 60/ USD. India’s GDP in USD during the period 2012-
2013

**A. ** increased by 5 %

**B. ** decreased by 13%

**C. ** decreased by 20%

**D. ** decreased by 11%

**Answer : ****Option D**

**Explaination / Solution: **

Per 100 Rs final value 107 Rs

Per 100 Rs final value 107 Rs

⇒ Per 100/50 Dollars final value 107/60

for 100 dollars____?

= ((100 × 50)/100) × (107/60) = 89.16

Decreased by 11%.

Workspace

Report

Which of the following statement (s) is/are correct regarding Bellman-Ford shortest path algorithm?
P. Always find a negative weighted cycle, if one exists.
Q. Finds whether any negative weighted cycle is reachable from the source.

**A. ** P only

**B. ** Q only

**C. ** Both P and Q

**D. ** Neither P nor Q

**Answer : ****Option B**

**Explaination / Solution: **

No Explaination.

No Explaination.

Workspace

Report

What is the optimized version of the relation algebra expression where
A1, A2 are sets of attributes in with A_{1 }⊂ A_{2 }and F1, F2 are Boolean expressions based on

**A. **

**B. **

**C. **

**D. **

**Answer : ****Option A**

**Explaination / Solution: **

No Explaination.

No Explaination.

Workspace

Report

A prime attribute of a relation scheme R is an attribute that appears

**A. ** in all candidate keys of R.

**B. ** in some candidate key of R.

**C. ** in a foreign keys of R.

**D. ** only in the primary key of R.

**Answer : ****Option B**

**Explaination / Solution: **

A prime attribute or key attribute of a relation scheme R is an attribute that appears in any of the candidate key of R, remaining attributes are known as non-prime or non-key tribute

A prime attribute or key attribute of a relation scheme R is an attribute that appears in any of the candidate key of R, remaining attributes are known as non-prime or non-key tribute

Workspace

Report

Consider the transactions T1, T2, and T3 and the schedules S1 and S2 given below.

**A. ** Only S1 is conflict-serializable.

**B. ** Only S2 is conflict-serializable.

**C. ** Both S1 and S2 are conflict-serializable.

**D. ** Neither S1 nor S2 is conflict-serializable.

**Answer : ****Option A**

**Explaination / Solution: **

Precedence graph for S1 & S2 are as follows

T1 : r1 (X) ; r1 (z) ; w1 (X) ; w1 (z)

T2 : r2 (X) ; r2 (z) ; w2 (z)

T3 : r3 (X) ; r3 (X) ; w3 (Y)

S1: r1(X); r3(Y); r3(X); r2(Y); r2(Z); w3(Y); w2(Z); r1(Z); w1(X); w1(Z)

S2: r1(X); r3(Y); r2(Y); r3(X); r1(Z); r2(Z); w3(Y); w1(X); w2(Z); w1(Z)

Which one of the following statements about the schedules is TRUE?

Precedence graph for S1 & S2 are as follows

∴Only S1 is conflict serializable.

Workspace

Report

Consider the relational schema given below, where eId of the relation dependentis a foreign
key referring to empId of the relation employee. Assume that every employee has at least one
associated dependent in the dependent relation.

**A. ** some dependent.

**B. ** all dependents.

**C. ** some of his/her dependents.

**D. ** all of his/her dependents

**Answer : ****Option D**

**Explaination / Solution: **

employee (__empId__, empName, empAge)

dependent (__depId, eId__, depName, depAge)

Consider the following relational algebra query

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 of his/her
dependents.

Workspace

Report

Consider the decision problem 2CNFSAT defined as follows:

**A. ** NP-Complete.

**B. ** solvable in polynomial time by reduction to directed graph reachability.

**C. ** solvable in constant time since any input instance is satisfiable.

**D. ** NP-hard, but not NP-complete.

**Answer : ****Option B**

**Explaination / Solution: **

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:__

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

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 V= P { p|p P} ∪ ¬ ∈ and (x, y E )∈ iff 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 iff there is a p P ∈ such that there is both a path from p to
to ¬p and from ¬p to p in G.

This condition can be tested by running the reachability algorithm several times.

Workspace

Report

Let R and S be relational schemes such that R={a, b, c} and S={c}. Now consider the following queries
on the database:

**A. ** I and II

**B. ** I and III

**C. ** II and IV

**D. ** III and IV

**Answer : ****Option C**

**Explaination / Solution: **

No Explaination.

Where R.c = S.c

Which of the above queries are equivalent?

No Explaination.

Workspace

Report

Consider the following relational schema: Suppliers (sid:integer, sname: string, city:string, street:
string)
Parts (pid:integer, pname: string, color:string)
Catalog (sid:integer, pid:integer,
cost: real)

**A. ** Find the names of all suppliers who have supplied a non-blue part

**B. ** Find the names of all suppliers who have not supplied a non-blue part

**C. ** Find the names of all suppliers who have supplied only blue parts

**D. ** Find the names of all suppliers who have not supplied only blue part

**Answer : ****Option A**

**Explaination / Solution: **

No Explaination.

Consider the following relational query on the above database:

SELECT S.sname

FROM Suppliers S

WHERE S.sid NOT IN (SELECT C. sid

FROM Catalog C

WHERE C.pid NOT IN (SELECT P.pid

FROM Parts P

WHERE P.color<> ‘blue’))

Assume that relations corresponding to the above schema are not empty. Which one of the following is
the correct interpretation of the above query?

No Explaination.

Workspace

Report