# GATE Computer Science Solved Session I 2016 - Part 3

21.       Which of the following is NOT a superkey in a relational schema with attributes V, W, X, Y, Z and primary key V Y ?
(A) V X Y Z                    (B) V W X Z
(C) V W X Y                  (D) V W X Y Z
Explanation:
Option (B) does not include Y which is a part of Primary Key.
A Super Key is simply a non-minimal Candidate Key, that is to say one with additional columns not strictly required to ensure uniqueness of the row.
A Primary Key is a minimal Candidate Key, which is to say all constituent columns are strictly required in order to ensure uniqueness.
22.       Which one of the following is NOT a part of the ACID properties of database transactions?
(A) Atomicity                 (B) Consistency
Explanation:
ACID (Atomicity, Consistency, Isolation, Durability) is a set of properties of database transactions. A transaction is a very small unit of a program and it may contain several low-level tasks. A transaction in a database system must maintain Atomicity, Consistency, Isolation, and Durability in order to ensure accuracy, completeness, and data integrity.
So option D is the answer.
23.       A database of research articles in a journal uses the following schema.
(VOLUME, NUMBER, STARTPGE, ENDPAGE, TITLE, YEAR, PRICE)
The primary key is (VOLUME, NUMBER, STARTPAGE, ENDPAGE) and the following functional dependencies exist in the schema.
(VOLUME, NUMBER, STARTPAGE, ENDPAGE)            → TITLE
(VOLUME, NUMBER)                                                → YEAR
(VOLUME, NUMBER, STARTPAGE, ENDPAGE)            → PRICE
The database is redesigned to use the following schemas.
(VOLUME, NUMBER, STARTPAGE, ENDPAGE, TITLE, PRICE)
(VOLUME, NUMBER, YEAR)
Which is the weakest normal form that the new database satisfies, but the old one does not?
(A) 1NF              (B) 2NF
(C) 3NF             (D) BCNF
Explanation:
There are partial dependencies in the given FD set. So, it is in 1 NF but not in 2NF.
The new design is removing all the partial dependencies. So it is in 2NF.
So the weakest normal form that the new database satisfies, but the old one does not is 2NF.
24.       Which one of the following protocols is NOT used to resolve one form of address to another one?
(A) DNS             (B) ARP
(C) DHCP         (D) RARP
Explanation:
The mapping of host names to IP addresses is handled through a service called Domain Name Service (DNS).
The Address Resolution Protocol (ARP) allows a host to find the MAC address of a node with an IP address on the same physical network, when given the node's IP address.
RARP (Reverse ARP) allows a machine to use its physical address to determine its logical address on the Internet.
Dynamic Host Configuration Protocol (DHCP) is a protocol for assigning dynamic IP addresses to devices on a network.
So DHCP is the answer. All others are used to convert one address to other.
25.       Which of the following is/are example(s) of stateful application layer protocols?
(i)  HTTP
(ii) FTP
(iii) TCP
(iv) POP3
A (i) and (ii) only
B (ii) and (iii) only
C (ii) and (iv) only
D (iv) only
Explanation:
A stateless protocol is a communications protocol that treats each request as an independent transaction. A stateless protocol does not require the server to retain session information or status about each communications partner for the duration of multiple requests.
A protocol that requires keeping of the internal state on the server is known as a stateful protocol.
HTTP is stateless.
FTP is stateful.
TCP is stateful, but not an application layer protocol.
POP3 is stateful.

26.       The coefficient of x12 in (x3 + x4 + x5 + x6 + ...)3 is............
27.       Consider the recurrence relation a1 = 8, an = 6n2 + 2n + an-1. Let a99 = k x 104. The value of K is .................
Explanation:
an=6n2+2n+an−1

=6n2+2n+6(n−1)2+2(n−1)+an−2

=6n2+2n+6(n−1)2+2(n−1)+6(n−2)2+2(n−2)+......+a1

=6n2+2n+6(n−1)2+2(n−1)+6(n−2)2+2(n−2)+......+6.12+2.1

=6(n2+(n−1)2+...+22+12)+2(n+(n−1)+...+2+1)

=6×n(n+1)(2n+1)/6+2×n(n+1)/2

=n(n+1)(2n+1+1)

an=2n(n+1)2

for n=99, a99=2×99×(99+1)2=198×104
So, K=198
28.       A function f : N+ → N+, defined on the set of positive integers N+, satisfies the following properties:
f (n) = f (n/2) if n is even
f (n) = f (n+5) if n is odd
Let R = {i |j : f(j) = i } be the set of distinct values that f takes. The maximum possible size of R is .............
Explanation:
Let us assume: f(1) = x. Then,
f(2) = f(2/2) = f(1) = x
f(3) = f(3+5) = f(8) = f(8/2) = f(4/2) = f(2) = f(2/2) = f(1) = x
Similarly, f(4) = x
f(5) = f(5+5) = f(10) = f(10/2) = f(5) = y. [Let us assume: f(5) = y ]
f(10) = f(10+5) = f(15) = f(15+5) = f(20) = f(20/2) = f(10) = f(10/2) = f(5) = y
So it will have two values. All multiples of 5 will have value y and others will have value x. It will have 2 different values.
29.       Consider the following experiment.
Step 1. Flip a fair coin twice.
Step 2. If the outcomes are (TAILS, HEADS) then output Y and stop.
Step 3. If the outcomes are either (HEADS, HEADS) or (HEADS, TAILS), then output N and stop.
Step 4. If the outcomes are (TAILS, TAILS), then go to Step 1.
The probability that the output of the experiment is Y is (up to two decimal places) ..............
Explanation:
The output will be Y if you get TH on your first trial with chance 1/4.
So P(Y1)=1/4 or
You got TT on the first trial with chance 1/4 and then repeat and get TH on the second. So P(Y2)=(1/4)(1/4) or
You got TT on 1 and 2, and then got TH on the third.
So P(Y3)=(1/4)(1/4)(1/4)
etc.
Since the events are mutually exclusive, you can just add up the probabilities.
Thus P(Y)=P(Y1)+P(Y2)+P(Y3)+
=1/4+(1/4)2+(1/4)3+
It goes on as infinite GP.
Sum of infinite GP = a/(1-r)
here a= 1/4 and r = 1/4
=1/4/(1−1/4)=(1/4)/(3/4)=1/3≈0.33
30.    Consider the two cascaded 2-to-1 multiplexers as shown in the figure.
The minimal sum of products form of the output X is
(A) P’Q’+PQR
(B) P’Q+QR
(C) PQ+ P’Q’R
(D) Q’R’+PQR