DPPs for GATE CSE

Practise focused daily problems for GATE CSE and check each worked answer after making your own attempt.

Daily practice problems with answers

Asymptotic analysis, stacks, queues and trees

An algorithm performs n + n/2 + n/4 + ... operations. What is its asymptotic running time?
Answer: The geometric sum is less than 2n, so the running time is Θ(n).
Which structure directly supports breadth-first traversal of an unweighted graph?
Answer: A queue. Vertices are processed in the same order in which they are discovered.
What is the worst-case search time in an unbalanced binary search tree containing n distinct keys?
Answer: Θ(n), because the tree can degenerate into a chain.
A full binary tree has 15 internal nodes. How many leaves does it have?
Answer: 16. In a full binary tree every internal node has two children, so the number of leaves equals the number of internal nodes plus one.
Run breadth-first search from a source in an unweighted graph. What does the level of a discovered vertex represent?
Answer: Its shortest-path distance from the source measured in number of edges.
Why is inserting at the front of a singly linked list Θ(1)?
Answer: Only the new node's next pointer and the head pointer change; no traversal is required.

Boolean algebra, caches and pipelining

Simplify X + X'Y.
Answer: X + Y. Use X + X'Y = (X + X')(X + Y) = X + Y.
A direct-mapped cache has 128 lines. How many index bits are required?
Answer: 7 bits, because 128 = 2^7.
Why can data forwarding reduce pipeline stalls?
Answer: It sends a produced value directly to a dependent pipeline stage before the value is written back to the register file.
A byte-addressable system has 32-bit addresses and a cache block size of 64 bytes. How many block-offset bits are used?
Answer: 6 bits, because 64 bytes = 2^6 bytes.
What is the minimum number of flip-flops required for a counter with 10 distinct states?
Answer: 4 flip-flops, because three bits encode only 8 states while four bits encode up to 16.
An ideal five-stage pipeline executes 20 instructions with no stalls. How many cycles are required?
Answer: 24 cycles: k + n - 1 = 5 + 20 - 1.

Scheduling, synchronization and memory

What does a semaphore wait operation do when no permit is available?
Answer: The calling process or thread blocks until another operation makes a permit available.
Which page-replacement anomaly can occur with FIFO but not with stack algorithms such as LRU?
Answer: Belady's anomaly: adding frames can increase the number of page faults.
Can deadlock occur if resources may always be pre-empted safely?
Answer: Not under the four-condition model, because the no-pre-emption condition is absent.
Three processes arrive at time 0 with CPU bursts 2, 4 and 6. Under non-pre-emptive SJF, what is the average waiting time?
Answer: The waiting times are 0, 2 and 6, so the average is 8/3 time units.
With 4 KiB pages, how many offset bits are present in a virtual address?
Answer: 12 bits, because 4 KiB = 4096 bytes = 2^12 bytes.
What is the difference between a process and a thread in the same process?
Answer: Processes have separate address spaces; threads in one process share its address space and resources while retaining their own execution state and stacks.

Keys, normalization, SQL and transactions

If A → B and B → C, what follows by transitivity?
Answer: A → C.
What does a SQL LEFT JOIN preserve?
Answer: Every row from the left table; unmatched right-side columns are returned as NULL.
What property must a conflict-serializable schedule have in its precedence graph?
Answer: The graph must be acyclic. A topological order gives an equivalent serial order.
For R(A,B,C,D) with A → BC and C → D, what is A+?
Answer: A+ = {A,B,C,D}; A determines B and C, and C then determines D.
What is the result of COUNT(column) when some rows contain NULL in that column?
Answer: It counts only non-NULL values. COUNT(*) counts rows regardless of NULL values.
Why is a B+ tree well suited to range queries?
Answer: Its leaf entries are ordered and linked, so after locating the first key the remaining range can be scanned sequentially.

Subnetting, transport and application protocols

How many total IPv4 addresses are in a /28 block?
Answer: 16, because 32 - 28 = 4 host bits and 2^4 = 16.
Why does TCP use sequence numbers?
Answer: To order byte-stream data, detect missing or duplicate data, and support acknowledgements and retransmission.
Which service normally maps a domain name to an IP address?
Answer: DNS.
How long does it take to transmit a 1,000-byte packet onto a 2 Mbps link, ignoring overhead?
Answer: 4 ms. The packet is 8,000 bits, and 8,000 / 2,000,000 = 0.004 seconds.
A router has routes 10.0.0.0/8 and 10.1.0.0/16. Which route matches destination 10.1.2.3?
Answer: Both match, but longest-prefix matching selects 10.1.0.0/16.
Why does UDP not guarantee delivery?
Answer: UDP provides connectionless datagrams without acknowledgements, retransmission or in-order recovery; an application must add such behaviour if needed.