#### 2014

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 (P, Q) = ((1 oplus P) oplus (P oplus Q)) oplus ((P oplus Q) oplus (Q oplus O))

The equivalent expression for F is

A. P + Q
B. overline(P + Q)
C. P oplus Q
D. overline(P oplus Q)

2

Consider the following relational schema:

Employee (underline(empId), empName, empDept)

Customer (underline(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')

A. Names of all the employees with at least one of their customers having a 'GOOD' rating.
B. Names of all the employees with at most one of their customers having a 'GOOD' rating
C. Names of all the employees with none of their customers having a 'GOOD' rating.
D. Names of all the employees with all their customers having a 'GOOD' rating

3

The CORECT formula for the sentence, "not all rainy days are cold" is

A. foralld (Rainy (d) ∧ ~ Cold (d))
B. foralld (~ Rainy (d) rightarrow Cold (d))
C. existsd (~ Rainy (d) rightarrow Cold (d))
D. existsd (Rainy (d) ∧ ~ Cold (d))

4

Let delta denote the minimum degree of a vertex in a graph. For all planar graphs on n vertices

with delta ge 3,  which one of the following is TRUE?

A. In any planar embedding, the number of faces is at leastn/2 + 2
B. In any planar embedding, the number of faces is less than n/2 + 2
C. There is a planar embedding in which the number of faces is less than n/2 + 2
D. There is a planar embedding in which the number of faces is at most n/(delta + 1)

5

If G is a forest with n vertices and k connected components, how many edges does G have?

A. [n / k]
B. [n / k]
C. n - k
D. n - k + 1