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. `forall`d (Rainy (d) ∧ ~ Cold (d))
B. `forall`d (~ Rainy (d) `rightarrow` Cold (d))
C. `exists`d (~ Rainy (d) `rightarrow` Cold (d))
D. `exists`d (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 least`n/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