CS and IT Gate 2016 Set-1 Questions with Answer

Given:
Sender: B
Receiver: A
Message to be sent: m
Message digest: H(m)
Private key of x: K^-_x
Public key of x: K⁺_x (where x ∈ {A, B})
Encryption of message m with key K_x: K_x(m)
To find:
The correct way of sending message m along with the digital signature from B to A.
Solution:
First, let me recall how a digital signature works.
To create a digital signature, the sender computes the hash of the message, which is the message digest H(m).
Now, to prove authenticity and provide non-repudiation, the sender must encrypt this digest using their own private key.
Here, the sender is B, so B must encrypt H(m) using B's private key K^-_B.
So, the digital signature generated by B is K^-_B(H(m)).
Now, B sends the original message m along with this digital signature to A.
Therefore, the package sent to A is {m, K^-_B(H(m))}.
Let me just verify the options to make sure.
Option A uses B's public key, which makes no sense because anyone could have made it.
Option C uses A's private key, which B does not even have access to.
Option D uses A's public key, which is for confidentiality, not a signature by B.
Hence, Option B is definitely the correct one.
Answer:
(B) {m,K^-_B (H(m))}

Given:
Protocols to check: (i) HTTP, (ii) FTP, (iii) TCP, (iv) POP3.
Condition: Stateful protocol at the application layer.
To find:
Which of the given protocols are stateful application layer protocols.
Solution:
Let me check each protocol one by one for two things: layer of operation and whether it is stateful.
First, check (i) HTTP:
HTTP works at the application layer, but by default it is stateless because the server does not retain any information about previous client requests.
So, HTTP is not stateful.
Next, check (ii) FTP:
FTP operates at the application layer and maintains state information (like current directory and user login state) throughout the control connection session.
So, FTP is a stateful application layer protocol.
Next, check (iii) TCP:
TCP is indeed stateful (maintains connection state, sequence numbers, etc.), but it operates at the transport layer, not the application layer.
So, TCP is ruled out.
Finally, check (iv) POP3:
POP3 works at the application layer and maintains state across the session (like authorization, transaction, and update states to keep track of emails marked for deletion).
So, POP3 is also a stateful application layer protocol.
Combining the valid ones, we have (ii) and (iv).
Answer:
(C) (ii) and (iv) only

Given:
Protocols: DNS, ARP, DHCP, RARP.
To find:
The protocol that is NOT used to resolve one form of address to another.
Solution:
Let me check what each protocol does one by one.
First, looking at DNS (Domain Name System):
It resolves a domain name (like www.google.com) to an IP address, so it maps one address format to another.
Now, looking at ARP (Address Resolution Protocol):
It resolves a logical IP address to a physical MAC address on a local network.
Next, looking at RARP (Reverse Address Resolution Protocol):
It does the reverse of ARP, resolving a physical MAC address to an IP address.
Finally, looking at DHCP (Dynamic Host Configuration Protocol):
It is used for dynamic configuration of IP addresses and other network parameters to hosts from a server.
It allocates IP addresses dynamically rather than resolving or mapping one address form to another.
Therefore, DHCP is not an address resolution protocol.
Answer: (C) DHCP

Given:
Four network protocols: DNS, ARP, DHCP, and RARP.
To find:
The protocol that is NOT used to resolve one form of address to another.
Solution:
Let me check what each protocol does one by one.
First, let's look at DNS (Domain Name System).
DNS maps/resolves a host domain name to an IP address (e.g., www.google.com to an IP). So it does resolve one form of address/name to another.
Next, checking ARP (Address Resolution Protocol).
ARP resolves a logical IP address to a physical MAC address on a local network. So it definitely does address resolution.
Next, checking RARP (Reverse Address Resolution Protocol).
RARP resolves a physical MAC address to an IP address. So it also performs address resolution.
Now looking at DHCP (Dynamic Host Configuration Protocol).
DHCP is used to dynamically allocate/assign IP addresses, subnet masks, default gateways, and DNS server IPs to client hosts automatically from a pool.
DHCP doesn't map or resolve one existing address into another form; it simply assigns configuration parameters to a device.
Therefore, DHCP is not an address resolution protocol.
Answer:
(C) DHCP

Given:
An undirected simple graph G = (V, E) with distinct edge weights.
An edge e ∈ E.
Statement I: If e is the lightest edge of some cycle in G, then every MST of G includes e.
Statement II: If e is the heaviest edge of some cycle in G, then every MST of G excludes e.
To find:
Which of the statements I and II is/are TRUE.
Solution:
Let me analyze Statement I first.
Can an edge be the lightest edge in one cycle, but still get excluded from the MST?
Let me try to construct a counterexample with 4 vertices: A, B, C, and D.
Let the edges and their weights be:
(A, C) = 1
(B, C) = 2
(A, B) = 10
(B, D) = 20
(A, D) = 30
Now consider the cycle A-B-D-A with edge weights 10, 20, and 30.
In this cycle, the edge (A, B) with weight 10 is indeed the lightest edge.
Now let me find the unique MST of this entire graph.
Using Kruskal's algorithm, picking edges in increasing order of weight:
Pick (A, C) of weight 1.
Pick (B, C) of weight 2.
Next smallest edge is (A, B) of weight 10, but adding it forms a cycle A-B-C-A, so discard it.
Pick (B, D) of weight 20.
All 4 vertices are now connected, so the MST consists of edges {(A, C), (B, C), (B, D)}.
The edge (A, B) is not present in the MST, even though it was the lightest edge in cycle A-B-D-A.
So Statement I is FALSE.
Now let me analyze Statement II.
This directly relates to the standard Cycle Property of Minimum Spanning Trees.
According to the Cycle Property, for any cycle in a graph, the strictly heaviest edge in that cycle cannot belong to any MST.
Since all edge weights in G are given to be distinct, the heaviest edge of any cycle is strictly greater than all other edges in that cycle.
If this heaviest edge were part of an MST, replacing it with any other edge of the cycle that connects the two resulting components would yield a spanning tree with a strictly smaller weight, which contradicts the minimality of the MST.
Therefore, e can never be a part of any MST.
So Statement II is TRUE.
Answer:
(B) II only

Given:
A binary heap implemented in an array.
Depth of the heap tree = d (edges on the path from the root to the farthest leaf).
Operation: delete(i) to delete the node at index i.
To find:
Time complexity to re-fix the heap efficiently after removing the element.
Solution:
Let me recall how deletion of an arbitrary node at index i works in a binary heap.
First, we replace the element at index i with the last element in the heap array.
Then, we reduce the heap size by 1.
Now, the new element placed at index i might violate the heap property.
It could be smaller than its parent (in a max-heap) or larger than its children, so it needs to move either up or down.
To fix this, we either call heapify-up or heapify-down from index i.
The height of the tree is equal to the depth d.
The maximum distance this element can travel upward is to the root, which is at most d levels.
The maximum distance it can travel downward is to a leaf, which is also at most d levels.
At each level, we do a constant number of comparisons and swaps, which takes O(1) time.
So, the maximum number of operations required is proportional to the depth d.
Hence, the worst-case time complexity to re-fix the heap is O(d).
Since this depends on the tree height and can require traversing all d levels in the worst case, it cannot be done in O(1) time.
Therefore, the time complexity is O(d) but not O(1).
Answer:
(B) O(d) but not O(1)

Given:
A recursive function count(int n) with a static variable static int d = 1, called initially as count(3).
To find:
Output of the program.
Solution:
The variable d is static, so it persists across all recursive calls and gets initialized only once.
Let me trace the calls step by step on a recursion stack.
First, main() calls count(3):
Here n = 3, and d starts at 1.
It prints n and then d:
Output so far: 3 1
Now d increments, so d = 2.
Since n > 1 (3 > 1 is true), it calls count(2).
Inside count(2):
Here n = 2, and current d = 2.
It prints n and d:
Output so far: 3 1 2 2
Now d increments, so d = 3.
Since n > 1 (2 > 1 is true), it calls count(1).
Inside count(1):
Here n = 1, and current d = 3.
It prints n and d:
Output so far: 3 1 2 2 1 3
Now d increments, so d = 4.
Since n > 1 (1 > 1 is false), the if condition fails, so no further call is made.
Now it executes the next statement and prints d:
Output so far: 3 1 2 2 1 3 4
Now count(1) finishes and returns to count(2).
Back in count(2):
It prints d, which is currently 4:
Output so far: 3 1 2 2 1 3 4 4
Now count(2) finishes and returns to count(3).
Back in count(3):
It prints d, which is still 4:
Output so far: 3 1 2 2 1 3 4 4 4
Now count(3) finishes and the program ends.
So the complete printed sequence is: 3 1 2 2 1 3 4 4 4.
Answer:
(A) 3 1 2 2 1 3 4 4 4

Given:
A recursive function count(int n) with a static variable d = 1, called initially as count(3).
To find:
The output printed on the console.
Solution:
Let me trace the function execution call by call.
Notice that d is static, so it is initialized to 1 only once and retains its updated value across all recursive calls.
First call: count(3)
Here, n = 3 and current d = 1.
Printing n gives: 3
Printing d gives: 1
Now incrementing d by 1, so d becomes 2.
Check condition: (n > 1) which is 3 > 1 (True).
So, it makes a recursive call: count(2).
Second call: count(2)
Here, n = 2 and current d = 2.
Printing n gives: 2
Printing d gives: 2
Now incrementing d by 1, so d becomes 3.
Check condition: (n > 1) which is 2 > 1 (True).
So, it makes a recursive call: count(1).
Third call: count(1)
Here, n = 1 and current d = 3.
Printing n gives: 1
Printing d gives: 3
Now incrementing d by 1, so d becomes 4.
Check condition: (n > 1) which is 1 > 1 (False).
Now printing the final line of count(1): printf("%d ", d), which prints: 4
The call count(1) finishes and returns back to count(2).
Back in count(2):
Now executing the line after the recursive call: printf("%d ", d).
Since d is currently 4, it prints: 4
The call count(2) finishes and returns back to count(3).
Back in count(3):
Now executing the line after the recursive call: printf("%d ", d).
Since d is still 4, it prints: 4
The call count(3) finishes and returns to main().
Putting all printed values together in order:
3 1 2 2 1 3 4 4 4
Answer:
(A) 3 1 2 2 1 3 4 4 4

Given:
A weighted connected undirected graph G with distinct positive edge weights.
Every edge weight is increased by the same constant value, say c > 0.
Statement P: Minimum spanning tree (MST) of G does not change.
Statement Q: Shortest path between any pair of vertices does not change.
To find:
Which of the statements P and Q is/are TRUE.
Solution:
Let me check statement P first.
A spanning tree of a graph with V vertices always contains exactly V - 1 edges.
If the weight of each edge increases by c, the total weight of any spanning tree T increases by exactly (V - 1) × c.
Let the original weight of a spanning tree be W(T).
The new weight becomes W'(T) = W(T) + (V - 1)c.
Since (V - 1)c is the same constant for all spanning trees, the tree that had the minimum weight originally will still have the minimum weight.
Alternatively, by Kruskal's algorithm, adding a positive constant c preserves the relative order of edge weights, so the algorithm picks the exact same edges.
So, statement P is TRUE.
Now let me check statement Q with a simple counterexample.
Consider a graph with two vertices u and v connected by two different paths:
Path 1 has 2 edges, each of weight 3. Total weight of Path 1 = 3 + 3 = 6.
Path 2 has 1 edge of weight 7. Total weight of Path 2 = 7.
Originally, Path 1 is the shortest path between u and v because 6 < 7.<br>
Now, let me increase each edge weight by c = 2.
New weight of Path 1 = (3 + 2) + (3 + 2) = 5 + 5 = 10.
New weight of Path 2 = 7 + 2 = 9.
Now, Path 2 is shorter than Path 1 since 9 < 10.<br>
The shortest path has changed because paths can have different numbers of edges, so longer paths in terms of hop count get penalized more.
So, statement Q is FALSE.
Therefore, only statement P is true.
Answer:
(A) P only

Given:
A queue implemented using an array, with operations ENQUEUE and DEQUEUE performed efficiently.
n is the number of elements in the queue.
To find:
The correct statement regarding the time complexity of ENQUEUE and DEQUEUE operations.
Solution:
Let me think about how a queue is implemented using an array efficiently.
If I use a simple linear array without wrapping around, DEQUEUE might require shifting elements, which takes O(n) time.
Wait, but if we use a circular array implementation with two pointers, front and rear, we can avoid shifting.
Let's see what happens during ENQUEUE in a circular array.
We simply advance the rear pointer using modulo arithmetic:
rear = (rear + 1) % capacity
Then we insert the element at rear, which takes O(1) time.
Now let's check DEQUEUE in a circular array.
We just read the element at front and advance the front pointer:
front = (front + 1) % capacity
This also takes O(1) time.
So both operations can be done in O(1) time using a circular array.
Therefore, option A is clearly the correct statement.
Answer: (A) Both operations can be performed in O(1) time