GATE Computer Science and Information Technology (CS) Syllabus

Contrast a ripple (asynchronous) counter with a synchronous counter.

In a ripple counter, each flip-flop is clocked by the previous stage's output, so delays accumulate (slower). In a synchronous counter, all flip-flops share a common clock, eliminating cumulative delay and removing decoding glitches.

What is the key difference between a Mealy machine and a Moore machine?

In a Mealy machine, output depends on both the current state and current input. In a Moore machine, output depends only on the current state. Moore typically needs more states but produces glitch-free, synchronous outputs.

What is the range of an $n$-bit unsigned binary number versus a two's complement number?

Unsigned: $0$ to $2^n - 1$. Two's complement (signed): $-2^{n-1}$ to $2^{n-1} - 1$, giving an asymmetric range with one extra negative value.

How do you compute the two's complement of a binary number?

Invert all bits (one's complement) and add $1$. Equivalently, the two's complement of an $n$-bit value $x$ is $2^n - x$. This makes subtraction $A - B = A + (\text{two's complement of } B)$.

Why is two's complement preferred over sign-magnitude and one's complement representations?

Two's complement has a single representation of zero, allows addition/subtraction with the same hardware (no end-around carry), and naturally handles sign. Sign-magnitude and one's complement both have two zeros ($+0$ and $-0$).

In IEEE 754 single-precision, how are the 32 bits allocated?

1 sign bit, 8 exponent bits (bias $127$), and 23 mantissa (fraction) bits. The value is $(-1)^{s} \times 1.M \times 2^{(E - 127)}$ for normalized numbers.

What is the exponent bias in IEEE 754 single and double precision?

Single precision (8 exponent bits): bias $= 127$. Double precision (11 exponent bits): bias $= 1023$. Stored exponent $=$ actual exponent $+$ bias.

What is the implicit (hidden) bit in normalized IEEE 754 floating point?

For normalized numbers the leading mantissa bit is always $1$, so it is not stored. The significand is interpreted as $1.M$, effectively giving 24 bits of precision in single precision from 23 stored bits.

How is overflow detected when adding two's complement numbers?

Overflow occurs when two operands of the same sign produce a result of the opposite sign. Equivalently, overflow $=$ carry-in to the MSB XOR carry-out of the MSB ($C_{in} \oplus C_{out}$).

Name the four general categories of a CPU's functional units / register-level organization.

The datapath (ALU and registers), the control unit (generates control signals), the register file (general-purpose registers, PC, IR, MAR, MBR), and the bus/interconnect linking them to memory and I/O.

What is the purpose of the Program Counter (PC) and Instruction Register (IR)?

The PC holds the address of the next instruction to fetch. The IR holds the currently fetched instruction being decoded and executed.

Define the five classic stages of a RISC instruction pipeline.

IF (instruction fetch), ID (instruction decode/register read), EX (execute/ALU), MEM (memory access), WB (write back). Each stage handles a different instruction concurrently.

What is the ideal speedup of a $k$-stage pipeline, and why is it not achieved in practice?

Ideal speedup approaches $k$ (the number of stages) for a large instruction count. It is not achieved due to pipeline hazards, stage imbalance, pipeline fill/drain overhead, and stalls.

List the three types of pipeline hazards.

Structural hazards (resource conflict), data hazards (instruction depends on a result not yet available), and control hazards (branches changing the instruction flow). Each can cause pipeline stalls.

What is a data hazard, and how does forwarding (bypassing) mitigate it?

A data hazard occurs when an instruction needs a value that a prior instruction hasn't yet written back. Forwarding routes the ALU result directly from one stage to a dependent instruction's input, avoiding a stall instead of waiting for write-back.

Define the three RAW, WAR, and WAW data dependencies.

RAW (read-after-write, true dependency): an instruction reads a register a prior one writes. WAR (write-after-read, anti-dependency): writes after a prior read. WAW (write-after-write, output dependency): two writes to the same register. Only RAW is a true data hazard in in-order pipelines.

Give the formula for the effective CPI of a pipeline with stalls.

$\text{CPI}_{eff} = 1 + \text{stall cycles per instruction}$. Execution time $= \text{Instruction count} \times \text{CPI}_{eff} \times \text{clock cycle time}$.

What is the typical ordering of the memory hierarchy from fastest to slowest?

Registers $\rightarrow$ L1 cache $\rightarrow$ L2 cache $\rightarrow$ L3 cache $\rightarrow$ main memory (DRAM) $\rightarrow$ secondary storage (SSD/disk). Speed and cost per bit decrease, while capacity increases, going down the hierarchy.

State the average memory access time (AMAT) formula.

$\text{AMAT} = \text{Hit time} + \text{Miss rate} \times \text{Miss penalty}$. With multiple levels it is applied recursively for each cache level.

Compare direct-mapped, fully associative, and set-associative cache mapping.

Direct-mapped: each memory block maps to exactly one cache line (fast, high conflict misses). Fully associative: a block can go anywhere (no conflict misses, costly search). Set-associative: a block maps to one set of $k$ lines, balancing the two ($k$-way).

How is a memory address split for cache lookup in a set-associative cache?

The address divides into Tag, Set Index, and Block Offset fields. Offset bits $= \log_2(\text{block size})$, index bits $= \log_2(\text{number of sets})$, and the remaining high-order bits form the tag.

Distinguish write-through from write-back cache policies.

Write-through updates both cache and main memory on every write (simple, consistent, more traffic). Write-back updates only the cache and marks the line dirty, writing to memory only on eviction (less traffic, needs a dirty bit).

Name the three categories of cache misses (the '3 Cs').

Compulsory (cold) misses on first access to a block, Capacity misses when the working set exceeds cache size, and Conflict misses when multiple blocks map to the same set in non-fully-associative caches.

Contrast programmed I/O, interrupt-driven I/O, and DMA.

Programmed I/O: CPU polls the device status (wastes cycles). Interrupt-driven I/O: device signals the CPU when ready (no busy-waiting). DMA: a controller transfers data directly between device and memory, interrupting the CPU only at completion (best for bulk transfer).

What happens during an interrupt service sequence?

The CPU finishes the current instruction, saves the program state (PC and registers), disables/acknowledges the interrupt, jumps to the Interrupt Service Routine via the vector table, executes the ISR, then restores state and resumes the interrupted program.

What is the difference between the storage classes 'static' and 'automatic' in C?

Automatic (local) variables live on the stack, are created on block entry and destroyed on exit. Static variables persist for the program's lifetime in a fixed memory region, retaining value between function calls; file-scope static also limits linkage to that file.

In C, what is the difference between call-by-value and call-by-reference (via pointers)?

Call-by-value copies the argument, so changes inside the function don't affect the caller's variable. C passes a pointer (address) to simulate call-by-reference: dereferencing the pointer (e.g., $*p$) lets the function modify the caller's actual variable.

What does pointer arithmetic $p + n$ compute for a pointer $p$ to type $T$?

It yields the address $p + n \times \text{sizeof}(T)$, advancing by $n$ elements (not $n$ bytes). This is why $a[i]$ is equivalent to $*(a + i)$ for an array $a$.

What two components must every recursive function have to terminate correctly?

A base case (stopping condition that returns without recursing) and a recursive case that moves toward the base case. Each call uses a new stack frame; missing or unreachable base cases cause infinite recursion and stack overflow.

Compare the time and space complexity of array vs. linked-list operations for random access and insertion.

Array: random access $O(1)$, insertion/deletion at arbitrary position $O(n)$ (shifting). Linked list: random access $O(n)$ (traversal), insertion/deletion given the node pointer $O(1)$. Linked lists also use extra space for pointers.

Contrast a stack and a queue by their access discipline and core operations.

A stack is LIFO (last-in first-out) with push and pop at one end (top). A queue is FIFO (first-in first-out) with enqueue at the rear and dequeue at the front. Both basic operations are $O(1)$.

What are the worst-case search, insert, and delete complexities of a balanced BST versus an unbalanced BST?

Balanced BST (e.g., AVL, red-black): $O(\log n)$ for search, insert, and delete. Unbalanced (degenerate/skewed) BST: $O(n)$ because it can degrade into a linked list. In-order traversal of a BST yields sorted order.

State the heap property and the array index relationships for a binary heap.

Max-heap: every parent $\geq$ its children (min-heap: parent $\leq$ children). For a node at index $i$ (0-based): left child $= 2i+1$, right child $= 2i+2$, parent $= \lfloor (i-1)/2 \rfloor$. Insert and extract-min/max are $O(\log n)$; peek is $O(1)$.