What topics are covered on Page 3 of GATE 2014 CS/IT Set 1?

Page 3 contains Questions 27 to 39. The page is dominated by DBMS topics including functional dependencies, keys, foreign keys, conflict serializability, normal forms and SQL. It also includes Quicksort, multiplexers, Boolean minimization, propositional and predicate logic, combinatorics and functions.

What is a key for relation R in GATE 2014 Question 28?

For the given relation and functional dependencies, {E,F,H} is a key because its closure determines all attributes of R.

Which transaction schedule is conflict serializable in GATE 2014?

Schedule D is conflict serializable among the four schedules listed in the question.

Does the SQL query for latest hires execute correctly?

Yes. The query executes and returns the latest hires for their respective departments at location 1700.

Which Quicksort input requires more comparisons when the first element is the pivot?

The already sorted input [1,2,3,4,5] requires more comparisons than [4,1,5,3,2], so t1 is greater than t2.

How many 10-pennants are there in GATE 2014 Question 38?

The number of sequences consisting of 1s and 2s whose sum is 10 is 89.

What is log2(log2 N) in the function-counting question?

For the function sets defined in Question 39, the value of log2(log2 N) is 16.

CS and IT Gate 2014 Set-1 Questions with Answer

1 2 3 4 5

Ques 27 GATE 2014 SET-1

Consider the following pseudocode. What is the total number of multiplications to be performed?
D = 2
for i = 1 to n do
for j = i to n do
for k = j + 1 to n do
D = D * 3

Half of the product of the 3 consecutive integers.

One-third of the product of the 3 consecutive integers.

One-sixth of the product of the 3 consecutive integers.

None of the above.

Ques 28 GATE 2014 SET-1

Consider the relation scheme
R = (E, F, G, H, I, J, K, L, M, N)
and the set of functional dependencies {{E, F} → {G}, {F} → {I, J}, {E, H} → {K, L}, {K} → {M}, {L} → {N}}. Which of the following is a key for R?

{E, F}

{E, F, H}

{E, F, H, K, L}

{E}

(b) is the correct answer.

Ques 29 GATE 2014 SET-1

Given the following statements:
S1: A foreign key declaration can always be replaced by an equivalent check assertion in SQL.
S2: Given the table R(a, b, c) where a and b together form the primary key, the following is a valid table definition.
CREATE TABLE S(
d INT,
e INT,
PRIMARY KEY (d),
FOREIGN KEY (a) REFERENCES R
)
Which one of the following statements is CORRECT?

S1 is TRUE and S2 is FALSE.

Both S1 and S2 are TRUE.

S1 is FALSE and S2 is TRUE.

Both S1 and S2 are FALSE.

(d) is the correct answer.

Ques 30 GATE 2014 SET-1

Consider the following four schedules due to three transactions (indicated by the subscript) using read and write on a data item x, denoted by r(x) and w(x) respectively. Which one of them is conflict serializable?
(A) r1(x); r2(x); w1(x); r3(x); w2(x)
(B) r2(x); r1(x); w2(x); r3(x); w1(x)
(C) r3(x); r2(x); r1(x); w2(x); w1(x)
(D) r2(x); w2(x); r3(x); r1(x); w1(x)

(d) is the correct answer.

Ques 31 GATE 2014 SET-1

Given the following two statements:
S1: Every table with two single-valued attributes is in 1NF, 2NF, 3NF and BCNF.
S2: AB → C, D → E, E → C is a minimal cover for the set of functional dependencies AB → C, D → E, AB → E, E → C.
Which one of the following is CORRECT?

S1 is TRUE and S2 is FALSE.

Both S1 and S2 are TRUE.

S1 is FALSE and S2 is TRUE.

Both S1 and S2 are FALSE.

(a) is the correct answer.

Ques 32 GATE 2014 SET-1

Given the following schema:
employees(emp-id, first-name, last-name, hire-date, dept-id, salary)
departments(dept-id, dept-name, manager-id, location-id)
You want to display the last names and hire dates of all latest hires in their respective departments in the location ID 1700. You issue the following query:
SQL> SELECT last-name, hire-date
FROM employees
WHERE (dept-id, hire-date) IN (SELECT dept-id, MAX(hire-date) FROM employees JOIN departments USING(dept-id) WHERE location-id = 1700 GROUP BY dept-id);
What is the outcome?

It executes but does not give the correct result.

It executes and gives the correct result.

It generates an error because of pairwise comparison.

It generates an error because the GROUP BY clause cannot be used with table joins in a sub-query.

(b) is the correct answer.

Ques 33 Gate 2014 Set-1

Let P be a QuickSort Program to sort numbers in ascending order using the first element as pivot. Let t1 and t2 be the number of comparisons made by P for the inputs [1, 2, 3, 4, 5] and [4, 1, 5, 3, 2] respectively. Which one of the following holds?

t1 = 5

t1 < t2

t1 > t2

t1 = t2

(Sorting Algorithm) is the correct answer.

The question asks us to compare the number of comparisons made by QuickSort when the first element is always chosen as the pivot.
Analyze the Options:
Input 1: [1, 2, 3, 4, 5]
The first element, 1, is the smallest element, so every other element is compared with the pivot. This creates the worst-case pattern, where the list is divided as 0 and 4, then 0 and 3, and so on.
Comparisons = 4 + 3 + 2 + 1 = 10.
Input 2: [4, 1, 5, 3, 2]
The first pivot is 4. The elements 1, 3, and 2 go to the left, while 5 goes to the right. The resulting subarrays are smaller and require fewer comparisons than the first input.
Comparisons = 4 + 3 + 1 = 8.
Comparison:
t₁ = 10 and t₂ = 8.
Therefore, t₁ > t₂.
Correct Answer: c) t1 > t2

Ques 34 GATE 2014 SET-1

Consider the 4-to-1 multiplexer with two select lines S1 and S0 given below.

The minimal sum-of-products form of the Boolean expression for the output F of the multiplexer is

P'Q + QP' + P'QR

P'Q + P'QP' + PQP' + P'QR

P'QR + P'QP' + QP' + P'QR

PQP'

(a) is the correct answer.

Ques 35 GATE 2014 SET-1

Which one of the following propositional logic formulas is TRUE when exactly two of p, q, and r are TRUE?

((p ↔ q) ∧ r) ∨ (p ∧ q ∧ ¬r)

(¬(p ↔ q) ∧ r) ∨ (p ∧ q ∧ ¬r)

((p → q) ∧ r) ∨ (p ∧ q ∧ ¬r)

(¬(p ↔ q) ∧ r) ∧ (p ∧ q ∧ ¬r)

(b) is the correct answer.

Ques 36 Gate 2014 Set-1

Consider the following Boolean expression for F:

F(P, Q, R, S) = PQ + P'QR + P'QR'S

The minimal sum-of-products form of F is__________

PQ + QR + QS

P + Q + R + S

P’ + Q’ + R’ + S’

P’R + P’R’S + P

(a) is the correct answer.

Given Boolean Expression:
F(P, Q, R, S) = PQ + P'QR + P'QR'S
Simplify the last two terms using the absorption law.
• Focus on P'QR + P'QR'S.
• Factor out the common term P'Q:
    P'Q(R + R'S)
• Apply the Boolean identity (X + X'Y = X + Y). Here, X = R and Y = S.
    So, (R + R'S) simplifies to (R + S).
• Substitute this back:
    P'Q(R + S) = P'QR + P'QS
• The expression now becomes:
    F = PQ + P'QR + P'QS
Simplify the first two terms using the absorption law.
• Focus on PQ + P'QR.
• Factor out the common term Q:
    Q(P + P'R)
• Apply the Boolean identity (X + X'Y = X + Y). Here, X = P and Y = R.
    So, (P + P'R) simplifies to (P + R).
• Substitute this back:
    Q(P + R) = PQ + QR
• The expression now becomes:
    F = PQ + QR + P'QS
Simplify the remaining expression.
• We have F = PQ + QR + P'QS.
• Factor out the common term Q from all terms:
    F = Q(P + R + P'S)
• Focus on the terms inside the parenthesis: (P + R + P'S).
• Rearrange to group P with P'S: (P + P'S + R).
• Apply the Boolean identity (X + X'Y = X + Y). Here, X = P and Y = S.
    So, (P + P'S) simplifies to (P + S).
• Substitute this back into the parenthesis:
    (P + S + R)
• Now substitute this back into the full expression for F:
    F = Q(P + S + R)
• Distribute Q:
    F = QP + QS + QR
• Rearrange the terms for standard form:
    F = PQ + QR + QS

Ques 37 Gate 2014 Set-1

Consider the statement

“Not all that glitters is gold”

Predicate glitters(x) is true if x glitters and predicate gold(x) is true if x is gold. Which one of the following logical formulae represents the above statement?

∃x: gold(x) => ¬ glitters(x)

∃x: glitters(x) => ¬ gold(x)

∀x: gold(x) => glitters(x)

∀x: glitters(x) =>¬ gold(x)

(a) is the correct answer.

Identify the Predicates:
• `glitters(x)`: x glitters.
• `gold(x)`: x is gold.

Translate the Statement:
"All that glitters is gold" means:
    ∀x (glitters(x) → gold(x))

Therefore, "Not all that glitters is gold" is:
    ¬∀x (glitters(x) → gold(x))

Using the equivalence:
    ¬∀x P(x) ≡ ∃x ¬P(x)
we get:
    ∃x ¬(glitters(x) → gold(x))

Since:
    ¬(A → B) ≡ A ∧ ¬B
the formula becomes:
    ∃x (glitters(x) ∧ ¬gold(x))

This means: "There exists at least one thing that glitters but is not gold."

Compare with the Given Options:
• A) ∃x: gold(x) ⇒ ¬glitters(x)
    Means there exists something such that if it is gold, it does not glitter.

• B) ∃x: glitters(x) ⇒ ¬gold(x)
    This is the intended answer among the given options, but strictly speaking, it is not logically equivalent to the required formula because an implication can be true when `glitters(x)` is false.

• C) ∀x: gold(x) ⇒ glitters(x)
    Means "All gold things glitter."

• D) ∀x: glitters(x) ⇒ ¬gold(x)
    Means "Nothing that glitters is gold," which is stronger than the given statement.

Conclusion:
The mathematically precise formula is:

∃x (glitters(x) ∧ ¬gold(x))

Since this exact formula is not provided, Option B is the intended answer in the given choices.

Ques 38 GATE 2014 SET-1

A pennant is a sequence of numbers, each number being 1 or 2. An n-pennant is a sequence of numbers with sum equal to n. For example, (1, 1, 2) is a 4-pennant. The set of all possible 1-pennants is {(1)}, the set of all possible 2-pennants is {(2), (1, 1)} and the set of all 3-pennants is {(2, 1), (1, 1, 1), (1, 2)}. Note that the pennant (1, 2) is not the same as the pennant (2, 1). The number of 10-pennants is _______.

(89) is the correct answer.

Ques 39 GATE 2014 SET-1

Let S denote the set of all functions f: {0, 1}⁴ → {0, 1}. Denote by N the number of functions from S to the set {0, 1}. The value of log₂log₂N is _______.

(16) is the correct answer.

1 2 3 4 5

Total Unique Visitors

Loading......

CS/IT Gate Yearwise

CS and IT Gate 2014 Set-1 Questions with Answer

Question Options

Sign in to ExamPrev