GATE CS 2024 Set 1

Take a proper colouring with exactly \(k\) colours. Its colour classes are independent sets that split the \(n\) vertices into \(k\) groups.

• (B) True: the largest of the \(k\) classes has at least \(n/k\) vertices.
• (C) True: every two colour classes must be joined by at least one edge, otherwise they could share a colour and \(k - 1\) colours would do. That gives at least \(\binom{k}{2} = k(k - 1)/2\) edges.
• (A) False: the 5-cycle needs 3 colours but contains no triangle.
• (D) False: the complete graph \(K_{k}\) has chromatic number \(k\), yet every vertex has degree \(k - 1\).

Answer: B, C

• (A) False: \((a \mathbin{\lozenge} b) \mathbin{\lozenge} c = a + 2b + 2c\), but \(a \mathbin{\lozenge} (b \mathbin{\lozenge} c) = a + 2(b + 2c) = a + 2b + 4c\).
• (B) True: \(\square\) is ordinary multiplication, which is associative.
• (C) False: \(a \mathbin{\lozenge} (b \mathbin{\square} c) = a + 2bc\), while \((a \mathbin{\lozenge} b) \mathbin{\square} (a \mathbin{\lozenge} c) = (a + 2b)(a + 2c)\). For \(a = b = c = 1\) these are 3 and 9.
• (D) True: \(a \mathbin{\square} (b \mathbin{\lozenge} c) = a(b + 2c) = ab + 2ac = (a \mathbin{\square} b) \mathbin{\lozenge} (a \mathbin{\square} c)\). It also holds from the right, since \((b + 2c)a = ba + 2ca\).

So multiplication distributes over \(\lozenge\), because \(\lozenge\) is a linear combination of its operands, but not the other way round.

Answer: B, D

• (A) False: on a read miss in a full set, LRU picks the victim without looking at its dirty bit. In a write back cache that block may be dirty, and it is then written back before the new block is brought in.
• (B) True: write through updates main memory on every write, so no cache block is ever newer than memory and evicting one needs no write back.
• (C) True: a write hit in a write back cache updates only the cache and sets the dirty bit, which changes it from 0 to 1 if the block was clean.
• (D) False: in a write through cache the victim already matches main memory, so it is simply overwritten. Nothing is written back first (and with no-write-allocate the missed block is not loaded at all).

Answer: B, C

A cylinder is the set of tracks at one arm position, one track on each of the 32 surfaces.

• Bytes per track: \(4096 \times 1024 = 2^{12} \times 2^{10} = 2^{22}\) bytes (4 MB).
• Bytes per cylinder: \(32 \times 2^{22} = 2^{5} \times 2^{22} = 2^{27}\) bytes (128 MB).
• Number of cylinders: \(2^{39} / 2^{27} = 2^{12} = 4096\), since \(512\ \text{GB} = 2^{9} \times 2^{30} = 2^{39}\) bytes.

The number of cylinders is the same as the number of tracks on one surface.

Answer: 4096

Of the 100 ns, 10 ns is serial and 90 ns can be shared. With \(p\) cores the shared part takes \(90/p\) ns, and each of the \(p - 1\) additional cores costs 10 ns:

\[T(p) = 10 + \frac{90}{p} + 10(p - 1)\]

This gives \(T(1) = 100\), \(T(2) = 65\), \(T(3) = 60\), \(T(4) = 62.5\) and \(T(5) = 68\) ns. A fourth core saves only \(30 - 22.5 = 7.5\) ns on the parallel part but adds 10 ns of overhead, so the time is smallest with 3 cores.

Charging the overhead for every core (\(10p\)) raises each time by 10 ns and still gives 3. The 2 GHz clock rate plays no part.

Answer: 3

Every instruction is fetched, so each one accesses the instruction cache once, while only the 25% load/store instructions also access the data cache. Memory stall cycles per instruction:

\[1 \times 0.02 \times 100 + 0.25 \times 0.08 \times 100 = 2 + 2 = 4\]

The real CPI is therefore \(2 + 4 = 6\), while a perfect cache gives the ideal CPI of 2. The instruction count and clock are the same in both cases, so the speedup is \(6 / 2 = 3.00\).

Applying the 8% data miss rate to every instruction gives a CPI of 12 and a speedup of 6, which overcounts the data accesses.

Answer: 3.00

After each fork(), the parent and the new child both call printf once and then continue the loop with the same value of x. So every pass doubles the number of processes, and each of them prints once:

• \(x = 3\): 2 processes print.
• \(x = 2\): 4 processes print.
• \(x = 1\): 8 processes print.

The total is \(2 + 4 + 8 = 14\). wait(NULL) only makes a parent wait for its children; it changes the order of execution, not the count. (More than 14 copies of "hello" can finally appear, because fork() copies unflushed output; the question counts executions of the statement.)

Answer: 14

A router sends each packet by the longest prefix that matches its destination. In the last byte, 10.1.1.128/25 covers 128–255, 10.1.1.64/26 covers 64–127, 10.1.1.192/26 covers 192–255, and the /24 matches every 10.1.1.x address.

• 10.1.1.16 matches only the /24: R1.
• 10.1.1.72 matches the /24 and 10.1.1.64/26: R3.
• 10.1.1.132 and 10.1.1.191 match the /24 and the /25 but not 10.1.1.192/26 (191 is just below 192): R2.
• 10.1.1.205 matches the /24, the /25 and 10.1.1.192/26; the /26 is the longest: R4.

Two hosts are reached via R2, so \(2 \times 20 = 40\) packets go through it.

Answer: 40

In Chomsky Normal Form every rule has the form \(A \rightarrow BC\) or \(A \rightarrow a\), and \(|w| = 90\).

• Each \(A \rightarrow BC\) step adds one symbol to the sentential form. Growing from the single symbol \(S\) to 90 symbols takes exactly 89 such steps.
• Each \(A \rightarrow a\) step turns one variable into one terminal, and every one of the 90 terminals is produced this way: 90 steps.

The derivation therefore has \(89 + 90 = 179\) steps. In general a CNF derivation of a string of length \(n \ge 1\) takes \(2n - 1\) steps; the 10 variables do not affect the count.

Answer: 179

A DFS of an undirected graph grows one tree for each connected component: a new tree starts only when no unvisited vertex is reachable from the earlier ones. So the number of trees in the DFS forest equals the number of components.

A tree on \(t\) vertices has \(t - 1\) edges, so a forest with \(n\) vertices and \(c\) trees has \(n - c\) edges:

\[100 - c = 40 \quad\Rightarrow\quad c = 60\]

Edges of \(G\) that are not in the forest (back edges) do not change this, so \(G\) has 60 connected components.

Answer: 60