PSEB Assessment Preparation

Digital IC Design & Verification 2026

Complete Descriptive Notes — From First Principles

Covering:
Digital Logic Design • Programming Concepts
Data Structures • Computer Architecture
Analytical Questions

Test Date: 25 April 2026 | Duration: 1 hour

How to Use These Notes
These notes are written as a self-contained study guide. Every concept includes a definition, an intuitive
explanation of why it matters, how it actually works, and worked examples where helpful. You do not need any
other source — read this document cover to cover, and you will be well-prepared for the test.

The test is for Digital IC Design & Verification, which strongly suggests that Digital Logic Design will carry the
highest weight, followed by Computer Architecture. Programming and Data Structures will test fundamentals
rather than advanced topics. Analytical questions test pattern recognition and basic quantitative reasoning
under time pressure.

Recommended Study Plan for Tonight

1. Read Digital Logic Design fully — it is the most important section (allocate ~2 hours).
2. Read Computer Architecture next — it overlaps heavily with Digital Logic (allocate ~1.5 hours).
3. Read Data Structures — focus on complexities and tree traversals (allocate ~1 hour).
4. Skim Programming Concepts — you already have a strong foundation (allocate ~45 minutes).
5. Skim Analytical Questions and try the worked examples (allocate ~30 minutes).
6. Review the final Quick Revision Sheet right before sleeping.
📌 Important: Do not try to memorize everything. Focus on *understanding*. An understood concept sticks; a
memorized fact slips. The exam will reward reasoning, not recitation.
Topic 1 — Digital Logic Design
Digital Logic Design is the foundation of every modern computing device. It is the study of how binary signals (0s
and 1s) are manipulated using logic gates to perform useful computation. Since this test is for IC Design &
Verification, expect this topic to carry the most weight — possibly 35% to 45% of all questions.

1.1 Number Systems

A number system is simply a way of representing quantities using a fixed set of symbols. The number of symbols
is called the base or radix of that system. Humans use the decimal system (base 10) because we have ten
fingers. Digital computers use the binary system (base 2) because transistors have only two stable states: ON
and OFF, which we represent as 1 and 0. Octal (base 8) and hexadecimal (base 16) are useful because they group
binary digits into compact chunks that are easy for humans to read.

The Four Main Number Systems

System Base and Symbols

Binary Base 2: uses 0, 1 — the native language of computers

Octal Base 8: uses 0–7 — one octal digit = 3 binary bits

Decimal Base 10: uses 0–9 — the familiar human system

Hexadecimal Base 16: uses 0–9 and A–F (where A=10, B=11, C=12, D=13, E=14,
F=15) — one hex digit = 4 binary bits

Positional Value and the Weight Concept

Every digit in a number has a positional weight that equals the base raised to the position's power. The
rightmost digit has position 0, the next has position 1, and so on. For decimal number 327, the value is
computed as 3×10² + 2×10¹ + 7×10⁰ = 300 + 20 + 7 = 327. This same principle applies to every number system —
only the base changes.

Binary to Decimal Conversion

To convert binary to decimal, multiply each bit by its positional weight (a power of 2) and sum the results.
💡 Example: Convert binary 10110 to decimal.
Position: 4 3 2 1 0 Bit: 1 0 1 1 0 Weight: 16 8 4 2 1
Value = 1×16 + 0×8 + 1×4 + 1×2 + 0×1 = 16 + 0 + 4 + 2 + 0 = 22

Decimal to Binary Conversion (Division Method)

To convert decimal to binary, repeatedly divide the number by 2 and record the remainders. Reading the
remainders from bottom to top gives the binary equivalent. This works because each division by 2 extracts one
bit of the binary representation.
💡 Example: Convert decimal 45 to binary.
45 ÷ 2 = 22 remainder 1 (LSB) 22 ÷ 2 = 11 remainder 0 11 ÷ 2 = 5 remainder 1 5
÷ 2 = 2 remainder 1 2 ÷ 2 = 1 remainder 0 1 ÷ 2 = 0 remainder 1 (MSB)
Reading bottom-up: 101101 So 45 (decimal) = 101101 (binary)

Binary to Hexadecimal (and Back)

Hex and binary conversions are the fastest because each hex digit represents exactly 4 binary bits. Group the
binary number into sets of 4 starting from the right, and convert each group to its hex equivalent.
💡 Example: Convert binary 11010110 to hexadecimal.
Group into 4-bit chunks: 1101 0110 1101 = 13 = D 0110 = 6 Result: D6 (hexadecimal)

Octal — Similar to Hex but with 3 bits

Octal groups binary into chunks of 3 instead of 4. Octal is used less often today but still appears in Unix file
permissions (e.g., chmod 755).
💡 Example: Convert binary 10110110 to octal.
Pad to multiple of 3 and group: 010 110 110 010 = 2 110 = 6 110 = 6 Result: 266
(octal)

1.2 Representing Signed Numbers

Computers store everything as bits, so we need a convention for representing negative numbers. There are
three classical methods, but only the third (2's complement) is used in modern processors.

Sign-Magnitude Representation
The leftmost bit (MSB) represents the sign: 0 for positive, 1 for negative. The remaining bits store the
magnitude. For example, in 4 bits, +5 is 0101 and −5 is 1101. The problem with this scheme is that there are two
representations of zero (+0 = 0000 and −0 = 1000), which wastes a value and complicates arithmetic.

1's Complement Representation

To negate a number in 1's complement, simply invert every bit. So +5 = 0101 and −5 = 1010. This also has two
zeros (0000 and 1111), and addition requires an end-around carry, which is inefficient in hardware.

2's Complement Representation (Used in All Modern Computers)

To negate a number in 2's complement, invert every bit and then add 1. This elegant scheme produces only one
representation of zero and allows the same adder hardware to perform both addition and subtraction. For this
reason, every modern CPU uses 2's complement for signed integers.
💡 Example: Represent −5 in 4-bit 2's complement.
Step 1: Write +5 in binary → 0101 Step 2: Invert all bits (1's comp) → 1010
Step 3: Add 1 → 1011 So −5 = 1011 in 4-bit 2's complement

Range of 2's Complement Numbers

For n bits in 2's complement, the representable range is from −2^(n−1) to +2^(n−1) − 1. The asymmetry comes
from the fact that one value is reserved for zero, leaving one extra negative value. This is a classic exam
question.
 Bit Width Range (2's Complement)

4 bits −8 to +7

8 bits −128 to +127

16 bits −32,768 to +32,767

32 bits −2,147,483,648 to +2,147,483,647

Overflow in 2's Complement

Overflow occurs when the result of an arithmetic operation exceeds the representable range. The rule for
detecting overflow is: if adding two positives gives a negative result, or adding two negatives gives a positive
result, overflow has occurred. Another way to detect it: overflow occurs when the carry into the MSB differs
from the carry out of the MSB.
💡 Example: In 4-bit 2's complement: 0110 (+6) + 0101 (+5) = 1011 (−5 in 2's comp). Two positives gave a negative
— overflow!

1.3 Boolean Algebra and Logic Gates

Boolean algebra is the mathematics of logic, invented by George Boole in the 19th century and applied to digital
circuits by Claude Shannon. Every variable takes only two values: TRUE (1) or FALSE (0). The three fundamental
operations are AND, OR, and NOT. From these, all other logic functions can be built.

The Three Basic Gates

AND Gate
An AND gate outputs 1 only when ALL of its inputs are 1. It is equivalent to multiplication in boolean algebra: Y =
A · B. You can think of AND as a series circuit with two switches — current flows only if both switches are closed.
Truth Table: A B | Y = A·B ------|--------- 0 0 | 0 0 1 | 0 1 0 | 0 1
1 | 1

OR Gate
An OR gate outputs 1 if ANY of its inputs is 1. It is equivalent to boolean addition: Y = A + B. Think of OR as a
parallel circuit — current flows if either switch is closed.
Truth Table: A B | Y = A+B ------|--------- 0 0 | 0 0 1 | 1 1 0 | 1 1
1 | 1

NOT Gate (Inverter)

A NOT gate simply inverts its single input. It is written as Y = A' (or sometimes as Ā or ¬A). If the input is 0, the
output is 1, and vice versa.
Truth Table: A | Y = A' ---|-------- 0 | 1 1 | 0

Derived Gates
NAND Gate (NOT-AND)
A NAND gate is an AND gate followed by an inverter. Its output is 0 only when ALL inputs are 1 — the exact
opposite of AND. NAND is extremely important because it is a universal gate: any boolean function can be
constructed using only NAND gates. This makes NAND ideal for manufacturing because circuits can be built using
a single gate type.
NOR Gate (NOT-OR)
A NOR gate is an OR gate followed by an inverter. Its output is 1 only when ALL inputs are 0. Like NAND, NOR is
also a universal gate.
XOR Gate (Exclusive OR)
An XOR gate outputs 1 when its inputs are different. It is written as Y = A ⊕ B = A'B + AB'. XOR is the heart of
binary addition, parity checking, and encryption. A nice property: A ⊕ A = 0, and A ⊕ 0 = A.
XNOR Gate (Exclusive NOR)
XNOR outputs 1 when its inputs are equal. It is the complement of XOR. XNOR is used in comparators to check if
two bits are the same.

Summary Truth Table of All Two-Input Gates

Inputs A, B AND, OR, NAND, NOR XOR, XNOR

0, 0 0, 0, 1, 1 0, 1

0, 1 0, 1, 1, 0 1, 0

1, 0 0, 1, 1, 0 1, 0

1, 1 1, 1, 0, 0 0, 1

Laws of Boolean Algebra

These laws let you simplify boolean expressions — which in turn means simpler, faster, cheaper hardware.
Memorize them.
Commutative: A + B = B + A A · B = B · A Associative: (A+B) + C = A
+ (B+C) (A·B)·C = A·(B·C) Distributive: A · (B + C) = A·B + A·C Identity:
A + 0 = A A · 1 = A Null: A + 1 = 1 A · 0
= 0 Idempotent: A + A = A A · A = A Complement: A + A' = 1
A · A' = 0 Double Neg: (A')' = A Absorption: A + (A·B) = A A · (A
+ B) = A Consensus: A·B + A'·C + B·C = A·B + A'·C

De Morgan's Theorems — Critically Important

De Morgan's theorems describe how NOT distributes over AND and OR. They are the single most useful pair of
identities in digital design.
First Theorem: (A · B)' = A' + B' Second Theorem: (A + B)' = A' · B' In words:
'NOT (A AND B)' equals 'NOT A OR NOT B' 'NOT (A OR B)' equals 'NOT A AND NOT B'

These theorems are why NAND and NOR are universal gates — you can use De Morgan to express any AND as a
NOR of inverted inputs, and any OR as a NAND of inverted inputs, which means NAND alone (or NOR alone) is
enough to build anything.
📌 Universal Gates: Both NAND and NOR are universal gates — meaning any logic function, no matter how
complex, can be built using only NAND gates or only NOR gates. This is a very common exam question. The
intuition: NAND can produce NOT (by tying both inputs together), AND (NAND followed by NAND as inverter),
and OR (via De Morgan's). Once you have NOT, AND, and OR, you have everything.

1.4 Canonical Forms: SOP and POS

There are two standard ways to express any boolean function: Sum of Products (SOP) and Product of Sums
(POS). These are called canonical forms because every boolean function has a unique representation in each of
these forms.

Sum of Products (SOP)

An SOP expression is the OR of several AND terms. Each AND term is called a minterm and corresponds to one
row in the truth table where the output is 1. To write the SOP form, pick all rows where the output is 1, write
each as an AND of the inputs (with complements for 0 inputs), and OR them together.
💡 Example: Given a truth table where F=1 when ABC = 001, 100, 111, the SOP is: F = A'B'C + AB'C' + ABC

Product of Sums (POS)

A POS expression is the AND of several OR terms. Each OR term is called a maxterm and corresponds to a row
where the output is 0. To write the POS form, pick all rows where the output is 0, write each as an OR of the
inputs (with complements for 1 inputs), and AND them together.

Karnaugh Maps (K-Maps) — Visual Simplification

A Karnaugh Map is a visual tool for simplifying boolean expressions. It arranges minterms in a grid such that
physically adjacent cells differ in exactly one variable. Grouping adjacent 1s allows you to eliminate variables and
obtain a minimized expression.
Rules for Grouping in K-Maps
7. Groups must contain only 1s (for SOP simplification).
8. Groups must be rectangular and contain a power-of-2 number of cells: 1, 2, 4, 8, or 16.
9. Groups can wrap around the edges and corners of the map (it is a torus, topologically).
10. Larger groups are better — a group of 2 eliminates 1 variable, group of 4 eliminates 2 variables, group of
8 eliminates 3 variables.
11. Every 1 must be covered by at least one group.
12. Use as few groups as possible.
13. Don't-care conditions (X) can be treated as 1s to make groups larger, but need not be covered if
inconvenient.
💡 Example: For F(A,B,C,D) = Σ(0,1,2,3,5,7,8,9,10,11), after grouping on a 4-variable K-map, the minimized
expression simplifies to F = B' + A'D + AD' (approximately — always verify with a truth table).
1.5 Combinational Circuits
A combinational circuit is a digital circuit whose output depends only on its current inputs — it has no memory
of past inputs. The output is purely a boolean function of the input signals. Examples include adders,
multiplexers, decoders, and comparators. These are the building blocks of the arithmetic and control logic inside
every CPU.

Half Adder
A Half Adder adds two single bits and produces a sum bit and a carry bit. It is called 'half' because it cannot
account for a carry coming in from a previous bit position.
Inputs: A, B Outputs: Sum = A ⊕ B Carry = A · B Truth Table: A B | Sum
Carry ------|----------- 0 0 | 0 0 0 1 | 1 0 1 0 | 1 0 1 1 | 0
1

Full Adder
A Full Adder adds three bits: two operand bits (A, B) and a carry-in (Cin) from the previous stage. It produces a
sum bit and a carry-out (Cout). Full adders can be chained to add multi-bit numbers.
Inputs: A, B, Cin Outputs: Sum = A ⊕ B ⊕ Cin Cout = A·B + Cin·(A ⊕ B)
= A·B + A·Cin + B·Cin (equivalent form)

Ripple Carry Adder

To add n-bit numbers, we chain n full adders, with the carry-out of each stage feeding into the carry-in of the
next. This is called a Ripple Carry Adder because the carry 'ripples' through the stages. It is simple but slow —
the delay grows linearly with the number of bits because each stage must wait for the previous stage's carry.

Carry Look-Ahead Adder (CLA)

A CLA solves the ripple carry speed problem by computing all carries in parallel using two signals per bit:
Generate (Gi = Ai · Bi) which indicates this bit generates a carry, and Propagate (Pi = Ai + Bi) which indicates this
bit would propagate an incoming carry. The CLA logic then computes all carries simultaneously, giving nearly
constant delay. CLAs are faster but use more gates.

Multiplexer (MUX)
A multiplexer is a data selector — it takes 2^n data inputs, n select lines, and routes the chosen input to a single
output. A 4-to-1 MUX has 4 data inputs, 2 select lines, and 1 output. MUXes are used everywhere in CPUs to
route data from multiple sources to a single destination (for instance, choosing between the output of the ALU,
a register file, or memory).
4-to-1 MUX: Select | Output S1 S0 | --------|------- 0 0 | I0 0 1 | I1
1 0 | I2 1 1 | I3 Expression: Y = S1'·S0'·I0 + S1'·S0·I1 + S1·S0'·I2 +
S1·S0·I3

Demultiplexer (DEMUX)
A DEMUX is the opposite of a MUX — it takes one input and routes it to one of 2^n outputs based on n select
lines. A 1-to-4 DEMUX has 1 input, 2 select lines, and 4 outputs. DEMUXes are used for distributing data to
multiple destinations, such as enabling one of several memory banks.
Encoder
An encoder converts 2^n input lines into n output lines. If input line k is active (and only one input is active at a
time), the encoder outputs the binary code for k. An 8-to-3 encoder has 8 inputs and 3 outputs. A common
application is a keypad: 16 keys produce a 4-bit code identifying which key was pressed. A priority encoder
handles the case where multiple inputs might be active by outputting the code of the highest-priority active
input.

Decoder
A decoder is the inverse of an encoder — it converts n input lines into 2^n output lines, where exactly one
output is active based on the input binary code. A 3-to-8 decoder has 3 inputs and 8 outputs. Decoders are used
in memory address decoding: the address bits select exactly one memory location.

Comparator
A magnitude comparator compares two binary numbers and produces three outputs: A > B, A = B, and A < B. For
1-bit inputs A and B: A > B is given by A·B'; A = B is given by A XNOR B; A < B is given by A'·B. Multi-bit
comparators chain these together, starting from the most significant bit.

1.6 Sequential Circuits

A sequential circuit is a digital circuit whose output depends on both the current inputs and the current state
(the history of past inputs). Sequential circuits have memory — they remember. This memory is implemented
with flip-flops or latches. Without sequential circuits, computers could not store data or execute programs.

Latches vs Flip-Flops — The Crucial Distinction

A latch is level-sensitive — it responds to its inputs as long as the enable signal is at a particular level (high or
low). This means the output can change multiple times while enable is active, which can cause unpredictable
behavior in complex circuits.

A flip-flop is edge-triggered — it responds to its inputs only at the instant the clock transitions (either the rising
edge or the falling edge, depending on the type). This makes flip-flops synchronous and predictable, which is
why virtually all modern digital designs use flip-flops instead of latches.

SR Flip-Flop (Set-Reset)
The SR flip-flop is the simplest type, built from two cross-coupled NAND or NOR gates. It has two inputs: S (Set)
and R (Reset). Setting S=1 makes Q=1; setting R=1 makes Q=0. The forbidden state S=R=1 is undefined and must
be avoided.
S R | Q(next) ------|-------- 0 0 | Q (hold, no change) 0 1 | 0 (reset) 1 0
| 1 (set) 1 1 | Invalid / Forbidden

D Flip-Flop (Data)
The D flip-flop has a single data input D. On every clock edge, the output Q takes the value of D. It is the most
widely used flip-flop in digital design — most registers are just arrays of D flip-flops. The D flip-flop is so
fundamental that when engineers say 'flip-flop' without qualification, they usually mean a D flip-flop.
D | Q(next) ---|-------- 0 | 0 1 | 1 Behavior: Q takes the value of D on
each rising clock edge.
JK Flip-Flop
The JK flip-flop improves on the SR flip-flop by defining the previously forbidden input combination. When
J=K=1, the output toggles (flips to its opposite). This gives JK flip-flops a useful property for building counters.
J K | Q(next) ------|-------- 0 0 | Q (hold) 0 1 | 0 (reset) 1 0 | 1 (set)
1 1 | Q' (toggle)

T Flip-Flop (Toggle)
The T flip-flop has a single input T. When T=0, the output holds its previous value; when T=1, the output toggles.
T flip-flops are ideal for building frequency dividers and counters.

Timing Parameters — The Heart of IC Design

Timing is the most important topic in IC design. Every flip-flop has strict timing requirements that must be
satisfied for correct operation. Violating these requirements leads to metastability, a condition where the
output becomes unpredictable and may oscillate. Expect exam questions on these parameters.

Parameter Definition and Importance

Setup Time (tsu) The minimum time the data input must be stable BEFORE the active
clock edge. Violating setup causes incorrect capture.

Hold Time (th) The minimum time the data input must remain stable AFTER the
active clock edge. Violating hold causes the new value to leak in
prematurely.

Clock-to-Q Delay (tcq) The time from the active clock edge to when the output Q becomes
stable. This is an intrinsic property of the flip-flop.

Propagation Delay (tp) The time for a signal to travel through combinational logic between
flip-flops.

Metastability An unpredictable state where the output voltage hovers between 0

and 1. Happens when setup or hold is violated.

Clock Skew The difference in clock arrival time between different flip-flops in
the same design. Can cause hold-time violations.

Clock Jitter The variation in the clock period over time. Reduces the effective
clock period.

Maximum Operating Frequency (Fmax)

The maximum clock frequency of a digital system is determined by the longest delay between any two flip-flops,
called the critical path. The formula is:
T_min = tcq + tcomb + tsu + tskew Fmax = 1 / T_min where: tcq = clock-to-Q
delay of launching flip-flop tcomb = propagation delay through combinational
logic tsu = setup time of capturing flip-flop tskew = clock skew between
the two flip-flops

💡 Example: If tcq = 1 ns, tcomb = 5 ns, tsu = 0.5 ns, tskew = 0.2 ns, then T_min = 6.7 ns and Fmax = 1 / 6.7 ns ≈
149 MHz.
Asynchronous vs Synchronous Counters
An asynchronous counter (also called a ripple counter) uses the output of each flip-flop as the clock for the next.
It is simple but slow, because the clock signal ripples through the chain. A 4-bit ripple counter has a delay of
4×tcq before the final output is valid.

A synchronous counter clocks all flip-flops simultaneously using a common clock. The next-state logic is
computed combinationally. Synchronous counters are faster and more reliable, but use more logic.

Shift Registers
A shift register is a chain of flip-flops where data shifts from one stage to the next on each clock edge. There are
four variants depending on how data enters and exits.

Type Behavior

SISO Serial In, Serial Out — one bit enters, bits shift, one bit exits

SIPO Serial In, Parallel Out — serial data fills the register, then all outputs
are read at once

PISO Parallel In, Serial Out — all bits loaded at once, then shifted out
serially

PIPO Parallel In, Parallel Out — essentially a register with a clock

Shift registers are used in serial-to-parallel conversion (UART receive), parallel-to-serial conversion (UART
transmit), and shift-and-add multiplication.

Finite State Machines (FSMs)

A Finite State Machine is an abstract model of a sequential circuit. It has a finite set of states, a current state, a
set of inputs, a set of outputs, and transition logic that determines the next state from the current state and
inputs. FSMs are used to design controllers, protocol handlers, and virtually every non-datapath circuit in an IC.
Mealy Machine
In a Mealy machine, the outputs depend on both the current state AND the current inputs. This usually results in
fewer states (because different input combinations in the same state can produce different outputs) and faster
response (output changes as soon as input changes). However, outputs may glitch because they are not directly
tied to the clock.
Moore Machine
In a Moore machine, the outputs depend ONLY on the current state. This requires more states but gives cleaner,
glitch-free outputs that change only on clock edges. Moore machines are generally preferred in modern IC
design for their predictability.

Aspect Mealy vs Moore

Output depends on Mealy: state + input | Moore: state only

Number of states Mealy: usually fewer | Moore: usually more

 Output timing Mealy: asynchronous, may glitch | Moore: synchronous, glitch-
free

Response speed Mealy: faster (output tracks input) | Moore: one cycle slower

1.7 Verilog HDL — Basics for IC Design

Verilog is a Hardware Description Language (HDL) used to describe digital circuits. Unlike a programming
language that describes instructions executed by a processor, Verilog describes hardware — wires, gates, and
flip-flops that exist in silicon. Understanding Verilog is mandatory for any IC Design & Verification role.

Module Structure
Every Verilog design is organized into modules. A module has a name, a list of input/output ports, and a body
containing the design logic. Here is the simplest possible module — an AND gate:
module and_gate (input a, input b, output y); assign y = a & b; endmodule

Data Types
• wire: Represents a physical wire — used for combinational logic outputs. Cannot store a value.
• reg: Represents a variable that can hold a value. Used in procedural blocks (always blocks). Despite the
name, reg does not always mean a physical register — it only means the variable holds its value until
reassigned.
• Vectors: Declared with bit ranges, e.g. wire [7:0] data is an 8-bit wire.

Procedural Blocks
The always block is the main construct for describing sequential and complex combinational logic. The
sensitivity list determines when the block executes.
// Combinational logic: execute whenever any input changes always @(*) begin y =
a & b; end // Sequential logic: execute on rising clock edge always @(posedge clk)
begin q <= d; end // Asynchronous reset: execute on clock or reset edge always
@(posedge clk or posedge rst) begin if (rst) q <= 0; else q <= d; end

Blocking (=) vs Non-Blocking (<=) Assignments

This is the most common source of bugs for beginners — and a frequent exam question.

• Blocking (=): Executes sequentially, one statement at a time. Use in combinational logic (always @*
blocks).
• Non-blocking (<=): All right-hand sides are evaluated first, then all left-hand sides are updated
simultaneously. Use in sequential logic (always @(posedge clk) blocks).
📌 Golden Rule: Always use non-blocking (<=) in sequential logic, and blocking (=) in combinational logic. Mixing
them causes simulation-synthesis mismatches — bugs that appear in hardware but not in simulation.
💡 Example: Consider two non-blocking assignments in sequence inside a clocked block: a <= b; b <= a;.
Both execute simultaneously — they swap values. If you had used blocking: a = b; b = a;, then a would get
b's value, and then b would get the new a (which is the old b), so both end up with b's value — a bug.
D Flip-Flop in Verilog
module dff ( input wire clk, input wire rst, input wire d, output reg q
); always @(posedge clk or posedge rst) begin if (rst) q <= 1'b0; else
q <= d; end endmodule

4-bit Counter in Verilog

module counter4 ( input wire clk, rst, output reg [3:0] count ); always
@(posedge clk or posedge rst) begin if (rst) count <= 4'b0000;
else if (count == 4'd15) count <= 4'b0000; else count <=
count + 1; end endmodule

1.8 Verification Concepts for IC Design

Verification is the process of ensuring that a digital design works as intended before committing it to silicon.
Since silicon fabrication costs millions of dollars and takes weeks, finding bugs before tapeout is critical.
Verification engineers spend as much time writing testbenches and running simulations as designers spend
writing RTL.

Key Concepts
• DUT (Design Under Test): The circuit being verified.
• Testbench: A Verilog/SystemVerilog program that drives stimulus into the DUT and checks its outputs.
• Simulation: Running the testbench and DUT together in a simulator (like ModelSim, VCS, Xcelium) to
observe behavior.
• Directed Testing: Writing specific test cases to exercise known scenarios.
• Constrained Random Verification: Generating random stimuli within defined constraints to cover corner
cases the designer didn't think of.

Coverage Metrics
• Code Coverage: Measures how much of the RTL code was executed (line, branch, toggle, FSM state
coverage).
• Functional Coverage: User-defined metrics that track whether specific features and scenarios have been
tested.
• Assertion Coverage: Tracks whether assertions fired during simulation.

SystemVerilog Assertions (SVA)

Assertions are statements that describe properties the design must always satisfy. They are automatically
checked during simulation and can also be used in formal verification. Example: 'Whenever request goes high,
grant must follow within 3 cycles.'

UVM (Universal Verification Methodology)

UVM is an industry-standard framework for building reusable, scalable verification environments. It is built on
SystemVerilog and provides a structured class library for creating transactions, drivers, monitors, scoreboards,
and test sequences. Most large IC companies (Intel, Qualcomm, Nvidia, AMD) use UVM.
Simulation vs Synthesis
Simulation verifies the behavior of your Verilog code by running it in a software simulator. Synthesis is the
process of converting your RTL description into a gate-level netlist (a list of actual gates and their connections)
that can be fabricated. Not all Verilog constructs are synthesizable — some are useful only for testbenches (e.g.,
initial blocks, delays).
Topic 2 — Programming Concepts
Programming is the art of expressing solutions to problems in a form a computer can execute. This topic covers
the fundamentals that apply across most languages — C, C++, Java, Python. Focus on understanding, not syntax
memorization.

2.1 What is a Program?

A program is a sequence of instructions that, when executed, solves a problem. The process of writing a
program involves understanding the problem, designing an algorithm, translating the algorithm into code,
testing, and debugging. The translator that converts your code into machine instructions is either a compiler
(like GCC for C++) or an interpreter (like Python's runtime).

Compiled vs Interpreted Languages

A compiled language (C, C++, Rust) translates the entire program into machine code before execution,
producing a standalone executable. Compiled programs run fast but the compile step adds a delay to the
development cycle.

An interpreted language (Python, JavaScript, Ruby) executes code line-by-line through an interpreter.
Interpreted programs are slower but have faster development cycles and are platform-independent.

Java is a hybrid — source code compiles to bytecode, which runs on the Java Virtual Machine (JVM). This gives
Java both performance and portability ('write once, run anywhere').

2.2 Data Types

A data type defines the kind of values a variable can hold and the operations that can be performed on it. Data
types also determine how much memory is allocated and how the bits are interpreted.

Primitive (Built-in) Types in C/C++

Type Size (typical) and Description

char 1 byte — a single ASCII character or small integer (−128 to 127)

int 4 bytes — a whole number; range −2^31 to 2^31 − 1

short 2 bytes — a smaller integer; range −32,768 to 32,767

long 4 or 8 bytes (platform-dependent) — a larger integer

long long 8 bytes — guaranteed to be at least 64 bits

float 4 bytes — single-precision floating point, ~7 decimal digits accurate

double 8 bytes — double-precision floating point, ~15 decimal digits

accurate

bool 1 byte — true or false (C++ only)

 void No size — indicates 'no type'

Derived Types
• Arrays: Contiguous block of elements of the same type. Example: int arr[10].
• Pointers: Variables that store memory addresses.
• References (C++ only): Aliases for existing variables. Cannot be null, cannot be reassigned.
• Functions: Reusable blocks of code.

User-Defined Types
• struct: A collection of fields grouped under a single name. In C++, structs can also have methods and
access specifiers.
• union: Like a struct, but all fields share the same memory. Only one field is valid at a time.
• enum: A type representing a fixed set of named constants.
• class (C++): Like a struct but members are private by default. Used for OOP.
• typedef / using: Creates an alias for an existing type.

2.3 Variables and Scope

A variable is a named storage location in memory. Every variable has a type, a name, a value, and a scope (the
region of the program where it is accessible) and a lifetime (the duration for which it exists in memory).

Scope Types
• Local scope: Variables declared inside a function or block. Destroyed when the block ends.
• Global scope: Variables declared outside any function. Accessible everywhere in the program.
• Block scope: Variables declared inside a {} block — visible only in that block.

Storage Classes (C/C++)

Storage Class Meaning

auto Default for local variables; lifetime = block

static Lifetime = entire program, but scope is local to the block/function

extern Variable defined in another file; tells compiler it exists

register Hint to compiler to store in CPU register for speed (mostly ignored
in modern compilers)

2.4 Control Flow

Control flow statements determine the order in which instructions are executed. Without them, a program
would be a boring linear list of statements.
Conditional Statements
// if-else if (x > 0) { ... } else if (x == 0) { ... } else { ... } // switch-case
switch (day) { case 1: printf("Monday"); break; case 2: printf("Tuesday");
break; default: printf("Unknown"); } // Ternary operator (shorthand for if-else)
result = (x > 0) ? "positive" : "non-positive";

Loops
• for loop: Used when the number of iterations is known in advance. Syntax: for (init; condition;
update) { body }.
• while loop: Executes as long as the condition is true. Check happens before each iteration.
• do-while loop: Like while, but the condition is checked AFTER the body, so the body always executes at
least once.

Loop Control Statements

• break: Exits the innermost loop immediately.
• continue: Skips the rest of the current iteration and goes to the next.
• return: Exits the current function, optionally with a return value.
• goto: Jumps to a labeled statement. Generally considered bad practice.

2.5 Functions
A function is a named block of reusable code that performs a specific task. Functions are the main tool for
decomposing large problems into smaller, manageable pieces. A function has a return type, a name, a
parameter list, and a body.

Parameter Passing
Call by Value
A copy of the argument is passed to the function. Changes made inside the function do not affect the original
variable. This is the default in C, Java, and many other languages.
void increment(int x) { x = x + 1; } int main() { int a = 5; increment(a); //
a is still 5 — the function modified only its local copy }

Call by Reference
The address of the argument is passed, so the function can modify the original variable. In C, this is done with
pointers; in C++, references are cleaner.
// C style with pointers void increment(int *x) { *x = *x + 1; } int main() { int
a = 5; increment(&a); // a is now 6 } // C++ style with references void
increment(int &x) { x = x + 1; }

Recursion
A recursive function is one that calls itself. Every recursive function must have a base case (a condition under
which it stops calling itself) to prevent infinite recursion. Recursion is powerful for problems that can be broken
into smaller subproblems — tree traversal, divide-and-conquer algorithms, mathematical definitions.
💡 Example: Factorial — the classic recursive function:
int factorial(int n) { if (n <= 1) return 1; // base case return n *
factorial(n - 1); // recursive case } // factorial(5) = 5 × 4 × 3 × 2 × 1 = 120

Function Overloading (C++)

Multiple functions can share the same name as long as they have different parameter lists. The compiler selects
the correct function based on the arguments. This is called compile-time polymorphism.
int add(int a, int b) { return a + b; } double add(double a, double b)
{ return a + b; } int add(int a, int b, int c) { return a + b + c; }

2.6 Object-Oriented Programming (OOP)

OOP is a programming paradigm that organizes code around 'objects' — bundles of data (attributes) and
behavior (methods). OOP aims to model real-world entities and enable code reuse through inheritance and
polymorphism. The four pillars of OOP are Encapsulation, Inheritance, Polymorphism, and Abstraction.

Class and Object

A class is a blueprint or template that defines the structure and behavior of objects. An object is an instance of a
class — an actual entity in memory with its own data. If Class is 'Car', then 'my red Honda Civic' is an Object.
class Car { private: string color; int speed; public: Car(string c)
: color(c), speed(0) {} // constructor void accelerate() { speed += 10; }
int getSpeed() { return speed; } }; int main() { Car myCar("red");
[Link](); cout << [Link](); // prints 10 }

Pillar 1: Encapsulation
Encapsulation is the bundling of data and the methods that operate on that data into a single unit (class),
combined with restricting direct access to the internal state. This is achieved through access specifiers: private
(accessible only within the class), protected (accessible in the class and its derived classes), and public
(accessible anywhere). Encapsulation protects object integrity — you cannot directly modify internal state, only
through well-defined methods.

Pillar 2: Inheritance
Inheritance lets a new class (the child or derived class) acquire the properties and methods of an existing class
(the parent or base class). This models 'is-a' relationships: a Dog is an Animal, a Car is a Vehicle. Inheritance
promotes code reuse and establishes class hierarchies.
class Animal { public: void eat() { cout << "eating"; } }; class Dog :
public Animal { // Dog inherits from Animal public: void bark() { cout <<
"woof"; } }; Dog d; [Link](); // inherited [Link](); // own method

Types of Inheritance
• Single inheritance: One parent, one child.
• Multilevel inheritance: A → B → C (C inherits from B which inherits from A).
• Hierarchical inheritance: Multiple children from one parent.
• Multiple inheritance (C++ only): A class inherits from multiple parents. Java replaces this with interfaces
because multiple inheritance of implementation causes the 'diamond problem.'
Pillar 3: Polymorphism
Polymorphism means 'many forms' — the ability of the same interface to behave differently based on the
underlying object type. There are two main kinds:
Compile-time Polymorphism (Static)
The function to call is determined at compile time. Examples: function overloading, operator overloading.
Runtime Polymorphism (Dynamic)
The function to call is determined at runtime based on the actual object type. This is achieved through virtual
functions in C++. The compiler sets up a virtual table (vtable) for each class with virtual functions, and the
correct function is looked up dynamically.
class Animal { public: virtual void speak() { cout << "generic sound"; } };
class Dog : public Animal { public: void speak() override { cout << "woof"; }
}; Animal* a = new Dog(); a->speak(); // prints "woof" — runtime polymorphism

Pillar 4: Abstraction
Abstraction means exposing only the essential features of an object while hiding the complex internal details.
When you drive a car, you use the steering wheel, pedals, and gear stick — you don't need to know how the
engine, transmission, and fuel injection work. In C++, abstraction is achieved through abstract classes (classes
with at least one pure virtual function) and interfaces.
class Shape { public: virtual double area() = 0; // pure virtual — makes
Shape abstract }; class Circle : public Shape { double radius; public:
Circle(double r) : radius(r) {} double area() override { return 3.14159 *
radius * radius; } }; // Shape cannot be instantiated directly; only concrete
subclasses can.

Constructor and Destructor

A constructor is a special method called automatically when an object is created. It typically initializes member
variables. A destructor is called when the object is destroyed and is used for cleanup (freeing memory, closing
files).

• Default constructor: No parameters.

• Parameterized constructor: Accepts arguments.
• Copy constructor: Creates a new object as a copy of an existing object.

2.7 Memory Management

Understanding how memory is organized is fundamental to writing efficient and bug-free code. A running
program's memory is divided into several regions.

Memory Layout of a Running Program

Region Contents

Text (Code) Segment The machine instructions of the program. Read-only.

Data Segment Initialized global and static variables.

 BSS Segment Uninitialized global and static variables. Zeroed at startup.

Heap Dynamically allocated memory (malloc, new). Grows upward.

Stack Function call frames, local variables, return addresses. Grows

downward.

Stack vs Heap — The Most Important Distinction

The stack is managed automatically. When a function is called, its local variables are allocated on the stack;
when the function returns, those variables are automatically deallocated. Stack allocation is extremely fast but
limited in size (typically a few MB). Stack variables have short lifetimes tied to their function.

The heap is managed manually (in C/C++) or by a garbage collector (in Java/Python). Memory allocated on the
heap persists until explicitly freed. Heap allocation is slower than stack but allows much larger objects and
flexible lifetimes. In C, you use malloc/free; in C++, you use new/delete.

Dynamic Memory in C
// Allocate space for 10 integers on the heap int *arr = (int *) malloc(10 *
sizeof(int)); if (arr == NULL) { /* handle allocation failure */ } // Use the
memory... arr[0] = 42; // ALWAYS free when done free(arr); arr = NULL; // good
practice — avoid dangling pointer

Dynamic Memory in C++

int *p = new int(42); // allocate single int int *arr = new int[10]; //
allocate array of 10 ints delete p; // free single object
delete[] arr; // free array — MUST use delete[]

Common Memory Bugs

• Memory leak: Allocating memory but never freeing it. Over time, the program consumes all available
memory.
• Dangling pointer: A pointer that still points to memory that has been freed. Dereferencing it causes
undefined behavior.
• Wild pointer: An uninitialized pointer that points to a random location.
• Double free: Calling free/delete twice on the same pointer. Undefined behavior.
• Buffer overflow: Writing past the end of an allocated buffer. Can corrupt adjacent data or be exploited
as a security vulnerability.

2.8 Pointers — The Heart of C/C++

A pointer is a variable that stores the memory address of another variable. Pointers are the primary reason C/C+
+ is fast and also the primary source of bugs. Understanding pointers deeply is essential.

Pointer Syntax
int x = 10; int *p; // p is a pointer to int p = &x; // & is the
address-of operator int y = *p; // * is the dereference operator — y now equals
10 // Pointer arithmetic p++; // moves to the next int (advances by
sizeof(int), typically 4 bytes)
Special Pointers
• NULL pointer: A pointer that points to nothing. Always check for NULL before dereferencing.
• **Void pointer (void \*)**: A generic pointer that can point to any type. Must be cast before
dereferencing.
• Function pointer: Stores the address of a function. Can be called through the pointer. Useful for
callbacks.
• **Pointer to pointer (int \*\*p)**: A pointer whose value is the address of another pointer.

Arrays and Pointers

In C, an array name decays to a pointer to its first element in most contexts. So arr[i] is equivalent to *(arr
+ i). This is why pointer arithmetic is so useful for traversing arrays.

2.9 Software Development Life Cycle (SDLC)

SDLC is the structured process of developing software from conception to retirement. It provides a framework
for managing complexity, ensuring quality, and delivering on time and budget.

The Six Phases of SDLC

14. Requirement Analysis: Gather what the user wants. Produce a Software Requirements Specification
(SRS) document.
15. System Design: Define system architecture, data flow, and component interactions. Produce High-Level
and Low-Level Design documents.
16. Implementation (Coding): Write the actual source code following the design.
17. Testing: Verify that the code meets requirements. Includes unit, integration, system, and acceptance
testing.
18. Deployment: Release to production. Might involve phased rollout, user training, data migration.
19. Maintenance: Fix bugs, add features, adapt to changing requirements. Often the longest phase.

SDLC Models
Waterfall Model
Each phase is completed before the next begins — like water flowing down a waterfall. It is simple and easy to
manage but inflexible. Once you are in the testing phase, going back to change requirements is expensive.
Waterfall suits projects with well-defined, stable requirements (e.g., safety-critical systems).
Iterative Model
Development happens in repeated cycles. Each iteration produces a more refined version of the system. Easier
to incorporate changes than Waterfall.
Spiral Model
Combines iterative development with risk analysis. Each 'spiral' goes through planning, risk analysis,
development, and evaluation. Suitable for large, high-risk projects.
Agile Model (Scrum, Kanban, XP)
Agile emphasizes short iterations (called sprints, typically 2 weeks), close collaboration with stakeholders, and
continuous delivery of working software. Scrum is the most popular Agile framework, with roles like Product
Owner, Scrum Master, and Development Team. Agile dominates modern software development because it
adapts quickly to changing requirements.
V-Model
An extension of Waterfall where each development phase has a corresponding testing phase. Requirements →
Acceptance Testing; Design → System Testing; Coding → Unit Testing. Shows that testing is not an afterthought
but a parallel activity.
DevOps
DevOps is not strictly an SDLC model but a culture that bridges Development and Operations. It emphasizes
Continuous Integration (CI) — automatic testing on every commit — and Continuous Deployment (CD) —
automatic release to production. Core tools: Git, Jenkins, Docker, Kubernetes.
Topic 3 — Data Structures
A data structure is a way of organizing data in memory so that it can be accessed and modified efficiently.
Choosing the right data structure is often the difference between a program that runs in seconds and one that
runs in hours. This topic is foundational to computer science and always appears in technical assessments.

3.1 Algorithm Analysis and Big-O Notation

Before studying data structures, we need a way to compare their efficiency. This is done using Big-O notation,
which describes how an algorithm's running time (or memory use) grows as the input size grows. Big-O captures
the asymptotic upper bound — how the algorithm behaves for very large inputs.

Common Complexity Classes (Ordered Best to Worst)

Complexity Meaning and Typical Algorithms

O(1) Constant — independent of input size. Array access by index, hash

table lookup (avg).

O(log n) Logarithmic — halves the problem each step. Binary search,

balanced tree operations.

O(n) Linear — touches each element once. Linear search, array traversal.

O(n log n) Linearithmic — divide and conquer. Merge sort, quick sort
(average), heap sort.

O(n²) Quadratic — nested loops over the data. Bubble sort, selection sort,
insertion sort.

O(n³) Cubic — three nested loops. Naive matrix multiplication, Floyd-

Warshall.

O(2^n) Exponential — explores all subsets. Naive recursive Fibonacci,

subset sum.

O(n!) Factorial — explores all permutations. Brute-force travelling

salesman.

Best, Average, and Worst Case

An algorithm's performance can depend on the specific input. Worst case gives the maximum time over all
inputs of size n — this is the Big-O that usually matters. Best case is the minimum time. Average case is the
expected time over random inputs. Quick sort, for example, has average-case O(n log n) but worst-case O(n²)
when the pivot is always the smallest or largest element.
Space Complexity
Space complexity measures how much extra memory an algorithm uses beyond the input itself. For example,
merge sort has space complexity O(n) because it needs a temporary array, while quick sort uses O(log n) for the
recursion stack.

3.2 Linear Data Structures

Array
An array is a contiguous block of memory storing elements of the same type. Elements are accessed by index in
O(1) time because the address of any element can be computed directly: address = base + (index ×
size).

Advantages
• O(1) random access by index — the fastest possible.
• Cache-friendly — contiguous layout maximizes CPU cache hits.
• Simple and memory-efficient — no per-element overhead.
Disadvantages
• Fixed size in static arrays — cannot grow after declaration.
• O(n) insertion/deletion in the middle — requires shifting elements.
• Wasted memory if the array is larger than needed.
Dynamic Arrays (Vectors)
C++'s std::vector, Java's ArrayList, and Python's list are dynamic arrays that automatically resize. When
the array fills up, it allocates a new block (usually twice as large) and copies elements over. This gives amortized
O(1) append performance.

Linked List
A linked list is a sequence of nodes where each node contains data and a pointer (or reference) to the next
node. Unlike arrays, linked list nodes are scattered throughout memory, connected only by pointers.
Types of Linked Lists
• Singly Linked List: Each node has a pointer to the next. Traversal is one-directional.
• Doubly Linked List: Each node has pointers to both next and previous. Allows backward traversal but
uses more memory per node.
• Circular Linked List: The last node points back to the first. No NULL termination.
Complexity

Operation Complexity

Access element at index i O(n) — must traverse

Search for a value O(n)

Insert/delete at head O(1)

 Insert/delete at tail (singly) O(n) if no tail pointer, O(1) if tail pointer maintained

Insert/delete at known node O(1) in doubly linked; O(n) in singly if prev not known

When to Use Linked List vs Array

• Use array when: you need random access, you know the size in advance, or you care about memory
efficiency and cache performance.
• Use linked list when: you frequently insert/delete in the middle, you don't know the size in advance, or
you need to splice lists together.

Stack (LIFO)
A stack is a data structure that follows the Last In, First Out principle. Think of a stack of plates: you add (push)
and remove (pop) plates from the top only. The last plate you put on is the first one you take off.
Stack Operations
• push(x): Add x to the top. O(1).
• pop(): Remove and return the top element. O(1).
• peek() / top(): Return the top element without removing it. O(1).
• isEmpty(): Check if the stack has no elements. O(1).
Applications of Stacks
• Function call management: Every function call pushes a stack frame; returning pops it.
• Expression evaluation: Converting infix to postfix, evaluating postfix expressions.
• Backtracking algorithms: Depth-first search, solving mazes.
• Undo functionality: Each edit pushed onto a stack; undo pops the last edit.
• Parenthesis matching: Check if '(((a+b)*c))' has balanced brackets.

Queue (FIFO)
A queue follows the First In, First Out principle. Think of a line at a bank: the first person in line is the first
person served. Insertions happen at the back (enqueue), removals at the front (dequeue).
Queue Operations
• enqueue(x): Add x to the back. O(1).
• dequeue(): Remove and return the front element. O(1).
• front() / peek(): Return the front element without removing it. O(1).
Types of Queues
• Simple Queue: Basic FIFO.
• Circular Queue: The tail wraps around to the front — more memory-efficient than using a linear array.
• Priority Queue: Each element has a priority; dequeue returns the highest-priority element, not the
oldest. Typically implemented with a heap.
• Deque (Double-Ended Queue): Insertion and removal from both ends. Supports both stack and queue
operations.
Applications of Queues
• Breadth-First Search (BFS) in graphs and trees.
• CPU scheduling: Round-robin, FIFO scheduling.
• Printer queues: Jobs are printed in the order submitted.
• Buffering in I/O operations, network packet handling.

3.3 Trees
A tree is a hierarchical data structure consisting of nodes connected by edges. Unlike linear structures, trees
branch. Trees naturally model hierarchies — file systems, organization charts, HTML/XML documents, decision
trees.

Tree Terminology

Term Meaning

Root The topmost node (has no parent)

Leaf A node with no children

Internal node A non-leaf node

Parent / Child A node connected directly above / below another

Sibling Nodes sharing the same parent

Ancestor / Descendant Any node above / below on the path to root / leaves

Depth of a node Number of edges from the root to that node

Height of a tree Number of edges on the longest root-to-leaf path

Subtree Any node plus all its descendants, treated as a tree

Binary Tree
A binary tree is a tree where each node has at most two children, called left child and right child. Binary trees
are the foundation for many important structures like BSTs and heaps.
Special Types of Binary Trees
• Full binary tree: Every node has either 0 or 2 children (never 1).
• Complete binary tree: All levels are full except possibly the last, which is filled left-to-right.
• Perfect binary tree: All internal nodes have 2 children AND all leaves are at the same depth.
• Balanced binary tree: The heights of the left and right subtrees of every node differ by at most 1.

Binary Search Tree (BST)

A BST is a binary tree with the ordering property: for every node N, all values in the left subtree are less than N,
and all values in the right subtree are greater than N. This property makes search, insert, and delete operations
efficient — O(log n) on average — because you can discard half the tree at each step.
BST Complexity

Operation Average / Worst

Search O(log n) / O(n) — worst when tree is skewed into a line

Insert O(log n) / O(n)

Delete O(log n) / O(n)

📌 Important: A BST is only efficient when balanced. If you insert sorted data into a simple BST, it degenerates
into a linked list with O(n) operations. Self-balancing BSTs (AVL, Red-Black) guarantee O(log n).

AVL Tree
An AVL tree is a self-balancing BST where the heights of the two child subtrees of any node differ by at most 1.
When an insertion or deletion causes imbalance, the tree is rebalanced using rotations (single left, single right,
left-right, right-left). AVL trees guarantee O(log n) for all operations but have more overhead due to rotations.

Red-Black Tree
A Red-Black tree is another self-balancing BST with slightly weaker balance guarantees than AVL but less
rotation overhead. Each node is colored either red or black, and a set of rules about coloring ensures the tree
stays approximately balanced. Red-Black trees are used in the C++ STL (map, set) and the Linux kernel.

Heap
A heap is a complete binary tree that satisfies the heap property. In a max-heap, every parent is greater than or
equal to its children (root is the maximum). In a min-heap, every parent is less than or equal to its children (root
is the minimum). Heaps are usually implemented with arrays, where for a node at index i, the children are at
2i+1 and 2i+2.
Heap Operations
• Insert: Add at end, then bubble up. O(log n).
• Extract max/min: Remove root, move last element to root, then bubble down. O(log n).
• Peek max/min: Look at root. O(1).
• Build heap from an unsorted array: O(n) using bottom-up heapify.
Heap Applications
• Priority queues: Natural fit.
• Heap sort: Build max-heap, repeatedly extract max. O(n log n).
• Dijkstra's algorithm: Min-heap for shortest-path frontier.

Tree Traversals — Must Know!

Traversal means visiting every node exactly once in a specific order. For binary trees, there are four standard
traversals.
Depth-First Traversals (Use Recursion/Stack)
• Pre-order (Root → Left → Right): Visit root first, then recursively traverse left subtree, then right. Useful
for copying a tree.
 • In-order (Left → Root → Right): Traverse left, visit root, traverse right. For a BST, this yields values in
sorted order — a classic exam question!
• Post-order (Left → Right → Root): Traverse both subtrees first, then visit root. Useful for deleting a tree
(you delete children before parent).
Breadth-First Traversal (Uses Queue)
• Level-order (BFS): Visit nodes level by level, from left to right. Uses a queue.
💡 Example: Given the tree below, find all four traversals:
1 / \ 2 3 / \ 4 5 Pre-order (Root-Left-Right):
1, 2, 4, 5, 3 In-order (Left-Root-Right): 4, 2, 5, 1, 3 Post-order (Left-Right-
Root): 4, 5, 2, 3, 1 Level-order (BFS): 1, 2, 3, 4, 5

3.4 Graphs
A graph is a collection of vertices (nodes) connected by edges. Graphs generalize trees — a tree is a connected
acyclic graph. Graphs model relationships: social networks, road maps, web page links, computer networks.

Graph Types
• Directed vs Undirected: In a directed graph (digraph), edges have direction (one-way streets). In an
undirected graph, edges work both ways (two-way streets).
• Weighted vs Unweighted: Edges in a weighted graph have a numerical cost (distance, time, price).
• Cyclic vs Acyclic: Cyclic graphs have at least one cycle; acyclic graphs have none. A DAG (Directed Acyclic
Graph) is especially important — it models dependencies, tasks, precedence.
• Connected vs Disconnected: A connected graph has a path between every pair of vertices.

Graph Representations
Adjacency Matrix
A 2D array where matrix[i][j] = 1 if an edge exists from vertex i to vertex j, else 0 (or the weight for weighted
graphs). Space: O(V²). Good for dense graphs and O(1) edge lookup. Wasteful for sparse graphs.
Adjacency List
An array of lists, where list[i] contains all vertices adjacent to vertex i. Space: O(V + E). Good for sparse graphs.
Iterating neighbors is O(degree), which is much better than O(V) for adjacency matrix.

Graph Traversal Algorithms

Breadth-First Search (BFS)
BFS explores all neighbors of a vertex before moving to the neighbors' neighbors. It uses a queue. BFS naturally
finds the shortest path in an unweighted graph because it explores vertices in order of increasing distance from
the source. Complexity: O(V + E).
Depth-First Search (DFS)
DFS goes as deep as possible along one branch before backtracking. It uses a stack (or recursion, which uses the
call stack). DFS is used for cycle detection, topological sorting, finding connected components, and maze-solving.
Complexity: O(V + E).
Shortest Path Algorithms
Dijkstra's Algorithm
Finds the shortest path from a source vertex to all other vertices in a weighted graph with non-negative edges.
Uses a min-heap (priority queue) to always expand the closest unvisited vertex. Complexity: O((V+E) log V).

Does not work with negative edge weights — if edges can be negative, use Bellman-Ford.
Bellman-Ford Algorithm
Finds shortest paths from a source, and can handle negative edge weights. Detects negative cycles. Complexity:
O(V × E). Slower than Dijkstra but more general.
Floyd-Warshall Algorithm
Finds shortest paths between all pairs of vertices. Uses dynamic programming. Complexity: O(V³). Simple and
elegant, suitable for dense graphs.

Minimum Spanning Tree (MST)

Given a connected, weighted, undirected graph, an MST is a subset of edges that connects all vertices with
minimum total weight and no cycles. MSTs are used in network design (cheapest cabling), clustering,
approximation algorithms.

• Prim's Algorithm: Grow the MST one vertex at a time, always adding the cheapest edge from the tree to
a new vertex. O(E log V) with a heap.
• Kruskal's Algorithm: Sort all edges by weight, add the next cheapest edge that does not create a cycle.
Uses Union-Find. O(E log E).

3.5 Hash Tables

A hash table (also called hash map or dictionary) stores key-value pairs and supports average O(1) insertion,
lookup, and deletion. A hash function maps each key to an index in an underlying array. Hash tables are
everywhere — Python dict, Java HashMap, JavaScript objects.

How Hash Tables Work

When you insert key k with value v, the hash function computes h(k), reduces it modulo the array size, and
places (k, v) at that index. To look up k, you compute h(k) again and find the entry. A good hash function
distributes keys uniformly across the array to minimize collisions.

Collision Handling
A collision occurs when two different keys hash to the same index. There are two main strategies:

• Chaining: Each array slot holds a linked list of all entries that hash there. Simple and effective.
• Open addressing: On collision, probe for the next empty slot. Variants: linear probing (try next slot),
quadratic probing (try i² slots away), double hashing (use a second hash function).

Load Factor
Load factor = (number of entries) / (array size). When it exceeds a threshold (usually 0.7), the table is resized —
typically doubled — and all entries are rehashed. This resize is O(n) but amortizes to O(1) per operation.
3.6 Sorting Algorithms
Sorting is so common that understanding the major algorithms is expected of every software engineer. Each has
different strengths.

Bubble Sort
Repeatedly step through the list, compare adjacent elements, and swap them if they are in the wrong order.
After each pass, the largest unsorted element 'bubbles up' to its correct position. Simple but slow. Best case O(n)
(already sorted, with optimization), average and worst O(n²). Stable.

Selection Sort
Find the minimum element in the unsorted part and swap it with the first unsorted element. Repeat. Always
does O(n²) comparisons but O(n) swaps. Not stable.

Insertion Sort
Build the sorted portion one element at a time by inserting each new element into its correct position in the
sorted portion. Very fast for nearly-sorted data — O(n) best case. Worst case O(n²). Stable.

Merge Sort
A divide-and-conquer algorithm: divide the array in half, recursively sort each half, then merge the two sorted
halves. Always O(n log n), stable, but requires O(n) extra space. Merge sort is preferred when stability is
required or when sorting linked lists (where its merging is natural).

Quick Sort
Another divide-and-conquer: pick a pivot, partition the array so that elements less than the pivot come before
and greater come after, then recursively sort each partition. Average O(n log n), but worst case O(n²) if the pivot
is always the smallest or largest. In-place, not stable. Despite the worst case, quick sort is typically faster than
merge sort in practice due to better cache behavior and lower constants.

Heap Sort
Build a max-heap from the array, then repeatedly extract the maximum and place it at the end. O(n log n) in all
cases, in-place, not stable. Slower than quick sort in practice but has guaranteed performance.

Counting Sort
Non-comparison sort that counts occurrences of each value and uses these counts to produce the sorted
output. Works only when the range of values is small. O(n + k) where k is the range. Stable.

Radix Sort
Non-comparison sort that processes digits one at a time, using a stable sort (like counting sort) on each digit.
O(d × (n + k)) where d is the number of digits. Useful for sorting integers or fixed-length strings.

Sorting Algorithms Summary Table

Algorithm Time (Best / Avg / Worst) Space / Stable?

 Bubble Sort O(n) / O(n²) / O(n²) O(1) / Yes

Selection Sort O(n²) / O(n²) / O(n²) O(1) / No

Insertion Sort O(n) / O(n²) / O(n²) O(1) / Yes

Merge Sort O(n log n) / O(n log n) / O(n log O(n) / Yes
n)

Quick Sort O(n log n) / O(n log n) / O(n²) O(log n) / No

Heap Sort O(n log n) / O(n log n) / O(n log O(1) / No

n)

Counting Sort O(n + k) / O(n + k) / O(n + k) O(k) / Yes

Radix Sort O(d(n+k)) / O(d(n+k)) / O(n + k) / Yes

O(d(n+k))

3.7 Searching Algorithms

Linear Search
Walk through the array from start to end, comparing each element with the target. Works on unsorted data.
O(n) worst case. Simple, no preprocessing needed.

Binary Search
Requires sorted data. Compare the target with the middle element. If equal, done. If target is smaller, repeat on
the left half; if larger, on the right half. Each step halves the search space, giving O(log n) complexity —
dramatically faster than linear search for large arrays.
💡 Example: Searching in a sorted array of 1 million elements: Linear search takes up to 1,000,000 comparisons.
Binary search takes at most 20 (because log₂(1,000,000) ≈ 20).
int binarySearch(int arr[], int n, int target) { int low = 0, high = n - 1;
while (low <= high) { int mid = low + (high - low) / 2; // avoid overflow
if (arr[mid] == target) return mid; if (arr[mid] < target) low = mid + 1;
else high = mid - 1; } return -1; // not found }
Topic 4 — Computer Architecture
Computer Architecture is the study of how the components of a computer — CPU, memory, I/O — are organized
and interact. For an IC Design engineer, understanding architecture is essential because you are often
implementing the very hardware concepts described here.

4.1 The Von Neumann and Harvard Architectures

Von Neumann Architecture
Proposed by John von Neumann in 1945, this architecture uses a single memory for both instructions and data,
connected to the CPU via a single bus. The CPU fetches instructions and data sequentially from this unified
memory. Because the instructions and data share the bus, only one can be fetched at a time — this is called the
Von Neumann bottleneck.

Despite this bottleneck, Von Neumann architecture dominates general-purpose computing (PCs, servers,
smartphones) because the unified memory is flexible — programs can be treated as data (enabling compilers,
interpreters, self-modifying code) and the hardware is simpler.

Harvard Architecture
Harvard architecture uses separate memories and buses for instructions and data. The CPU can fetch an
instruction and read/write data in the same clock cycle, doubling memory bandwidth. This makes Harvard faster
but more complex.

Harvard is common in Digital Signal Processors (DSPs) and microcontrollers (ARM Cortex-M, Atmel AVR), where
predictable, high-speed memory access is crucial. Many modern CPUs use a Modified Harvard architecture —
Von Neumann at the main memory level, but Harvard at the L1 cache level (separate instruction cache and data
cache).

Comparison Table

Feature Von Neumann / Harvard

Memory for code and data Unified / Separate

Bus structure Shared bus (bottleneck) / Separate buses (faster)

Flexibility High — code can be treated as data / Lower — fixed separation

Typical use General-purpose CPUs / DSPs, microcontrollers, cache level

4.2 CPU Organization

Main Components of a CPU
• ALU (Arithmetic Logic Unit): Performs arithmetic operations (add, subtract, multiply, divide) and logical
operations (AND, OR, NOT, XOR, shift, compare). The ALU is the computational heart of the CPU.
 • Control Unit (CU): Fetches instructions, decodes them, and generates control signals to orchestrate the
ALU, registers, and memory. The CU is the 'brain' that directs the rest of the CPU.
• Register File: A small, fast array of storage locations inside the CPU. Registers are the fastest memory in
the system (faster than cache). The number and organization of registers is a key architectural decision.
• Cache: On-chip SRAM that stores recently-used instructions and data to reduce the average memory
access time.
• Bus Interface Unit: Manages the connection between the CPU and external memory/peripherals.

Important Registers

Register Role

PC (Program Counter) Holds the address of the NEXT instruction to be fetched.

Incremented automatically after each fetch; modified by branches
and jumps.

IR (Instruction Register) Holds the currently fetched instruction while it is being decoded
and executed.

MAR (Memory Address Holds the address of the memory location being read or written.
Register)

MDR / MBR (Memory Holds the data being transferred to or from memory.
Data/Buffer Register)

ACC (Accumulator) Primary register for arithmetic operations in simple architectures.

SP (Stack Pointer) Points to the top of the stack in memory. Used for function calls
and local variables.

BP / FP (Base/Frame Pointer) Points to the base of the current stack frame.

Flags / Status Register Holds status bits: Zero (Z), Carry (C), Sign (S), Overflow (O), Parity
(P).

General-Purpose Registers R0 through Rn — used for intermediate computation, parameters,

return values.

4.3 The Instruction Cycle (Fetch-Decode-Execute)

Every instruction goes through a cycle of steps from being fetched from memory to completing its execution.
This cycle is the fundamental rhythm of every CPU.

20. Fetch: The CPU reads the next instruction from memory. The address is in the PC. After the fetch, PC is
incremented to point to the next instruction.
21. Decode: The Control Unit examines the instruction and determines what operation it is (ADD, LOAD,
BRANCH, etc.), what registers/memory are involved, and what control signals to assert.
22. Execute: The operation is performed. For arithmetic, the ALU computes the result. For memory
operations, the address and data are set up.
23. Memory Access (if needed): Read data from memory or write data to memory.
 24. Write Back: The result is stored in the destination register.
This 5-step breakdown (Fetch, Decode, Execute, Memory, Writeback) is used in the classic MIPS pipeline.
Simpler architectures combine some of these stages.

4.4 Instruction Set Architecture — RISC vs CISC

An Instruction Set Architecture (ISA) is the contract between hardware and software — the set of instructions
the processor can execute. There are two major philosophies: RISC and CISC.

CISC — Complex Instruction Set Computer

CISC architectures (x86, x86-64) have a large, rich instruction set with many specialized instructions — some of
which perform complex tasks like 'copy a string of bytes' or 'compute a polynomial' in a single instruction.
Instructions are variable in length (1 to 15 bytes in x86), and a single instruction may take multiple clock cycles to
execute.

CISC was designed in an era when memory was expensive and assembly programming was common — complex
instructions allowed programs to be shorter and more memory-efficient. The trade-off is that the hardware
decoding logic is complex, limiting clock speeds and power efficiency.

RISC — Reduced Instruction Set Computer

RISC architectures (ARM, MIPS, RISC-V, PowerPC) use a small, uniform instruction set where each instruction
performs a simple task and ideally executes in one clock cycle. Instructions are fixed in length (typically 32 bits),
and RISC uses a load-store architecture: arithmetic operates only on registers, and only load/store instructions
access memory.

The simpler, regular instruction set makes decoding fast, allows higher clock speeds, enables deep pipelines, and
is power-efficient. RISC dominates mobile (ARM), embedded, and supercomputing. Modern x86 CPUs actually
translate CISC instructions into RISC-like micro-operations internally.

RISC vs CISC Comparison

Aspect RISC vs CISC

Instruction count Few (~100) vs Many (100s to 1000s)

Instruction complexity Simple, uniform vs Complex, specialized

Instruction length Fixed (32 bits) vs Variable (1–15 bytes)

Cycles per instruction 1 (ideal) vs Multiple

Addressing modes Few vs Many

Registers Many (32+) vs Few (8–16)

Memory access Load-store only vs Memory-to-memory possible

Examples ARM, MIPS, RISC-V vs x86, x86-64, VAX

Typical use Mobile, embedded, DSP vs Desktop, server

4.5 Pipelining
Pipelining is a technique to improve CPU performance by overlapping the execution of multiple instructions.
Think of a car factory assembly line: while one car has wheels being attached, the next has its engine being
installed, and the one after that is getting painted. All stages work in parallel on different cars.

The Classic 5-Stage MIPS Pipeline

Cycle: 1 2 3 4 5 6 7 8 Instr 1: IF | ID | EX | MEM| WB
Instr 2: IF | ID | EX | MEM| WB Instr 3: IF | ID | EX | MEM| WB
Instr 4: IF | ID | EX | MEM| WB Stages: IF = Instruction Fetch
ID = Instruction Decode / Register Read EX = Execute / Address Computation
MEM = Memory Access WB = Write Back

Without pipelining, each instruction takes 5 cycles, and one instruction completes every 5 cycles. With
pipelining, after the pipeline is full, one instruction completes every cycle — a 5x speedup in instruction
throughput. The latency per instruction is still 5 cycles, but throughput is dramatically higher.

Pipeline Hazards
Pipelining seems like magic, but it doesn't always work smoothly. Three classes of hazards can stall the pipeline:
Structural Hazards
Two instructions in different stages need the same hardware resource simultaneously. Example: if the CPU has
only one memory port, an instruction in the MEM stage and another in the IF stage compete. Solution:
Duplicate the resource (e.g., separate instruction and data caches — Harvard-style L1).
Data Hazards
An instruction needs a value that an earlier, still-executing instruction will produce. There are three sub-types
based on the order of reads and writes:

• RAW (Read After Write): True dependency. Instruction 2 reads what Instruction 1 writes. Most
common.
• WAR (Write After Read): Anti-dependency. Instruction 2 writes what Instruction 1 reads.
• WAW (Write After Write): Output dependency. Both instructions write to the same register.
Solutions: Pipeline stalls (bubble), forwarding (bypass the result from an earlier stage directly to the needing
instruction), or compiler instruction reordering.
Control Hazards
Branch instructions change the PC, but the branch's outcome is not known until several stages into the pipeline.
By then, the CPU has already fetched the wrong next instruction. Solutions: Branch prediction (guess which way
the branch will go; modern CPUs are ~95% accurate), delayed branching (put a useful instruction in the pipeline
slot after the branch), or branch target buffers.

Speedup from Pipelining

For a k-stage pipeline and n instructions, total cycles = k + (n − 1), compared to k × n without pipelining. Speedup
approaches k for large n. But hazards reduce the effective speedup — modern CPUs rarely achieve the
theoretical limit.
4.6 Memory Hierarchy
Computer memory is organized in a hierarchy: small, fast, expensive memory close to the CPU, and large, slow,
cheap memory far away. This works because programs exhibit locality of reference — they tend to access the
same memory locations repeatedly (temporal locality) or nearby locations (spatial locality).

The Memory Hierarchy Pyramid

┌─────────────────────────────────┐ │ Registers (bytes, ~0.5 ns) │ Fastest,
smallest, inside CPU ├─────────────────────────────────┤ │ L1 Cache (~32–64 KB,
~1 ns) │ Split I-cache / D-cache ├─────────────────────────────────┤ │ L2 Cache
(~256 KB–1 MB, ~4 ns)│ ├─────────────────────────────────┤ │ L3 Cache (~4–32 MB,
~10 ns) │ Shared across cores ├─────────────────────────────────┤ │ Main Memory
(DRAM) (~GB, ~100 ns)│ ├─────────────────────────────────┤ │ SSD/HDD (~TB,
~0.1–10 ms) │ Slowest, largest, cheapest └─────────────────────────────────┘

Why Does the Hierarchy Work?

• Temporal locality: If a memory location was accessed recently, it is likely to be accessed again soon.
Example: variables in a loop.
• Spatial locality: If a memory location was accessed, nearby locations are likely to be accessed soon.
Example: iterating through an array.
The cache exploits both by storing recently accessed data AND the data around it (in chunks called cache lines,
typically 64 bytes).

Cache Concepts
• Cache hit: The data is found in the cache — fast access.
• Cache miss: The data is not in the cache — fetched from the next level, which is much slower.
• Hit rate: Percentage of accesses that hit. Modern CPUs achieve 95%+ L1 hit rates.
• Cache line: The unit of transfer between levels, typically 64 bytes.

Cache Mapping Schemes

• Direct-mapped: Each memory block maps to exactly one cache line. Simple but prone to conflict misses.
• Fully associative: A block can go anywhere in the cache. Best hit rate but expensive to search.
• Set-associative (n-way): A compromise — each block maps to one of n lines in a specific set. Modern
caches are typically 4-way or 8-way set-associative.

Cache Write Policies

• Write-through: Every write updates both the cache AND main memory. Simple but slow.
• Write-back: Writes update only the cache; memory is updated later when the line is evicted. Faster but
more complex (needs a 'dirty' bit).

Cache Replacement Policies

When a new line must be loaded and the cache is full, which line gets evicted?

• LRU (Least Recently Used): Evict the line that has not been accessed for the longest time. Best hit rate
for most workloads.
 • FIFO (First In First Out): Evict the oldest line. Simpler than LRU.
• Random: Evict a random line. Surprisingly effective and cheap.

4.7 Virtual Memory

Virtual memory is a memory management technique that gives each process the illusion of having a large,
contiguous, private memory space — even when physical RAM is smaller and shared. Each process uses virtual
addresses, which the Memory Management Unit (MMU) translates to physical addresses on the fly.

Why Virtual Memory?

• Isolation: Each process sees its own address space; one process cannot read or corrupt another's
memory.
• Abstraction: Programs don't need to know the actual physical memory layout.
• Larger apparent memory: Parts of the virtual address space can be stored on disk and brought into RAM
only when needed (swapping/paging).
• Protection: Pages can be marked read-only or non-executable.

Paging
Virtual memory is divided into fixed-size pages (typically 4 KB). Physical memory is divided into page frames of
the same size. A page table for each process maps virtual page numbers to physical frame numbers. When the
CPU generates a virtual address, the MMU looks up the page table to find the physical address.

Page Fault
If a required page is not in RAM (maybe it was never loaded, or was swapped to disk), a page fault occurs. The
OS handles it by reading the page from disk into a free frame, updating the page table, and restarting the
faulting instruction. Page faults are very expensive (milliseconds) compared to RAM access (nanoseconds).

Translation Lookaside Buffer (TLB)

The TLB is a small, fast cache for page table entries. Looking up the page table in memory would be slow, so the
TLB caches recent translations. A TLB hit is much faster than a page table walk. A TLB miss triggers a page table
walk (which itself may cause a cache miss).

Thrashing
If physical RAM is too small for the active working set of processes, the system spends more time swapping
pages in and out than doing useful work. Performance drops catastrophically. The solution is to reduce the
multiprogramming level or add more RAM.

4.8 Input/Output (I/O) Techniques

Programmed I/O (Polling)
The CPU repeatedly checks a status register to see if the I/O device is ready. Simple but wastes CPU cycles — the
CPU is busy-waiting.
Interrupt-Driven I/O
The device signals the CPU via an interrupt when it is ready. The CPU suspends its current work, runs an
Interrupt Service Routine (ISR), and resumes. Much more efficient than polling because the CPU does useful
work while the device prepares.

Direct Memory Access (DMA)

A dedicated DMA controller transfers data directly between a device and memory, bypassing the CPU entirely.
The CPU only initiates the transfer and receives an interrupt when done. Essential for high-throughput I/O like
disk and network — the CPU would be overwhelmed if it had to handle every byte.

4.9 Buses
A bus is a shared communication pathway connecting CPU, memory, and peripherals. Classic system buses are
split into three logical parts:

• Data bus: Carries the actual data. Width (e.g., 64 bits) determines how much data can be transferred per
clock.
• Address bus: Carries memory addresses. Width determines the maximum addressable memory (32-bit
address bus = 4 GB).
• Control bus: Carries control signals — read/write, interrupt requests, clock.

4.10 Parallel Processing — Flynn's Taxonomy

Michael Flynn classified computer architectures by the number of instruction streams and data streams they
process concurrently.

Classification Description and Examples

SISD Single Instruction, Single Data — a traditional uniprocessor. One

instruction operates on one piece of data at a time.

SIMD Single Instruction, Multiple Data — one instruction operates on

many data elements in parallel. GPUs, vector processors, SSE/AVX
in x86.

MISD Multiple Instruction, Single Data — rare. Used in fault-tolerant

systems where multiple processors perform the same task for
redundancy.

MIMD Multiple Instruction, Multiple Data — multiple processors, each

executing its own instructions on its own data. Multi-core CPUs,
clusters.

4.11 Multi-core and Multithreading

Modern CPUs contain multiple cores on a single chip. Each core can execute instructions independently,
enabling true parallelism. Multithreading (specifically, Simultaneous Multithreading or Hyper-Threading) allows
a single core to execute instructions from two threads simultaneously, keeping the execution units busier when
one thread is stalled waiting on memory.
Topic 5 — Analytical Questions
Analytical questions test your ability to recognize patterns, reason logically, and perform quantitative
computations under time pressure. The good news: with a bit of practice, most analytical questions become
quick recognition tasks. The key is exposure to common question types.

5.1 Number Series and Sequences

These test pattern recognition. Given a sequence of numbers, identify the rule and predict the next term.
Common patterns:

• Arithmetic progression: Constant difference between consecutive terms (2, 5, 8, 11, → 14).
• Geometric progression: Constant ratio (3, 6, 12, 24, → 48).
• Differences of differences: Second-order patterns (2, 5, 10, 17, 26 — differences are 3, 5, 7, 9 — next is
11, so 37).
• Powers: Squares (1, 4, 9, 16, 25...), cubes (1, 8, 27, 64, 125...).
• Fibonacci-like: Each term is the sum of previous two (1, 1, 2, 3, 5, 8, 13...).
• Alternating patterns: Two interleaved sequences (2, 10, 4, 20, 6, 30 → next pair: 8, 40).
• Primes: 2, 3, 5, 7, 11, 13, 17, 19, 23...
💡 Example: Find the next term: 3, 6, 11, 18, 27, ?

Solution: Differences are 3, 5, 7, 9 — each is 2 more than the previous. Next difference is 11. So next term = 27 +
11 = 38.
💡 Example: Find the next term: 1, 4, 27, 256, ?

Solution: Each term is n^n — 1¹, 2², 3³, 4⁴, so next is 5⁵ = 3125.

5.2 Coding-Decoding
Letters are encoded using a rule (shift, reversal, substitution). Decode the rule and apply it.

Letter Position Coding

💡 Example: If CAT = 3, 1, 20 (A=1, B=2, ..., Z=26), what is DOG?

Solution: D=4, O=15, G=7 → 4, 15, 7.

Shift Ciphers
💡 Example: If BOOK is coded as CPPL, then READ is coded as?

Solution: Each letter shifted by +1. R→S, E→F, A→B, D→E, so SFBE.

Reverse Coding
💡 Example: If CAT is coded as XZG, decode the rule.

Solution: Each letter is replaced by its 'opposite' (A↔Z, B↔Y, C↔X, ...). C→X, A→Z, T→G.
5.3 Logical Reasoning
Syllogisms
Given two or more statements, determine which conclusions necessarily follow. The best method is to draw
Venn diagrams.
💡 Example: Statement 1: All engineers are hardworking. Statement 2: Some hardworking people are rich. Does it
follow that 'Some engineers are rich'?

Solution: Draw three circles. 'Engineers' is entirely inside 'hardworking'. 'Rich' overlaps with 'hardworking' but
we don't know WHERE the overlap is — it might or might not include the 'engineers' region. Therefore the
conclusion does NOT necessarily follow. Answer: Cannot be determined.

Blood Relations
Draw a family tree with +/− symbols for male/female. Trace each relationship carefully.
💡 Example: Pointing to a photograph, A says: 'He is the son of the only son of my father.' Who is in the
photograph?

Solution: 'Only son of my father' = A himself. So the photograph is of A's son.

💡 Example: B's father is A's son. A has only one son. How is A related to B?

Solution: A's only son is B's father, so A is B's grandfather (paternal).

Direction Sense
Draw a compass and trace the path step by step. Remember the four cardinal directions: North (up), South
(down), East (right), West (left). Also the diagonals: NE, NW, SE, SW.
💡 Example: A man walks 5 km North, then 3 km East, then 5 km South. How far is he from the starting point and
in which direction?

Solution: The North and South cancel out. He ends 3 km East of start. Answer: 3 km East.

Seating Arrangements
Given clues about who sits where, deduce the final arrangement. Draw seats and fill in names systematically
based on clues. Start with the most specific clue.

5.4 Quantitative Aptitude — Essential Formulas

Percentages
Basic: x% of N = (x/100) × N Percentage change = ((New − Old) / Old) × 100
Successive changes of a% and b%: Net = a + b + (ab/100) Example: Price rises 20%,
then falls 20%. Net change? Net = 20 + (−20) + (20 × −20 / 100) = 0 − 4 = −4% (a
4% net DECREASE, not 0!)

Profit and Loss

Profit = SP − CP Loss = CP − SP Profit % = (Profit / CP) × 100 Loss % = (Loss
/ CP) × 100 SP = CP × (100 + Profit%) / 100 Discount = Marked Price − Selling Price
Discount % = (Discount / Marked Price) × 100 Example: CP = 500, sold at 600.
Profit% = (100/500) × 100 = 20%

Simple and Compound Interest

Simple Interest: SI = (P × R × T) / 100 Compound Interest: CI = P × (1 + R/100)^T
− P Amount (CI): A = P × (1 + R/100)^T Example: Rs 10,000 at 10% for 2 years
SI = 10000 × 10 × 2 / 100 = Rs 2000 CI = 10000 × 1.21 − 10000 = Rs 2100

Speed, Distance, Time

Distance = Speed × Time Speed = Distance / Time Time = Distance / Speed
Conversion: x km/hr = (x × 5/18) m/s (multiply by 5/18 for km/hr → m/s)
x m/s = (x × 18/5) km/hr Average speed (same distance at speeds x, y): = 2xy / (x
+ y) Relative speed (opposite direction): sum Relative speed (same direction):
difference

Ratio and Proportion

Ratio a : b = a / b Proportion a : b :: c : d means a/b = c/d, so a × d = b × c
Example: If 3 : 5 :: x : 25, then x = (3 × 25) / 5 = 15

Time and Work

If A does work in x days, A's 1-day work = 1/x Combined rate of A and B: 1/x + 1/y
= (x + y) / xy Time together = xy / (x + y) Example: A takes 10 days, B takes 15
days. Together? Time = 10 × 15 / (10 + 15) = 150/25 = 6 days

Averages
Average = Sum / Count Sum = Average × Count Weighted average = (w1·x1 + w2·x2
+ ...) / (w1 + w2 + ...) Example: Class A has 30 students with avg 70. Class B has
20 students with avg 80. Combined avg = (30×70 + 20×80) / 50 = (2100 + 1600) / 50 =
74

5.5 Permutations and Combinations

Permutation: Arrangement where order matters. How many ways to arrange r items out of n? Formula: nPr =
n! / (n−r)!

Combination: Selection where order does not matter. How many ways to choose r items out of n? Formula: nCr
= n! / (r! × (n−r)!)

Factorial: n! = n × (n−1) × (n−2) × ... × 2 × 1. By convention, 0! = 1.

💡 Example: How many ways to arrange 5 books on a shelf? Answer: 5! = 120.
💡 Example: How many ways to choose 3 people from 10? Answer: 10C3 = 10! / (3! × 7!) = 120.

Key Insight
Permutations count arrangements (ABC, ACB, BAC, etc.). Combinations count sets ({A, B, C}). For the same n and
r, permutations are always r! times larger than combinations.

5.6 Probability
Probability is the likelihood of an event, between 0 (impossible) and 1 (certain).
P(Event) = Favorable outcomes / Total outcomes P(not A) = 1 − P(A) For independent
events A and B: P(A and B) = P(A) × P(B) For any two events: P(A or B) = P(A) +
P(B) − P(A and B) Conditional probability: P(A | B) = P(A and B) / P(B)

💡 Example: A die is rolled. What is the probability of getting an even number?

Solution: Even outcomes = {2, 4, 6}, total = 6. P = 3/6 = 1/2.

💡 Example: Two cards drawn from a deck without replacement. Probability both are aces?

Solution: P(first ace) = 4/52. P(second ace | first ace) = 3/51. Total = (4/52) × (3/51) = 12/2652 = 1/221.

5.7 Worked Practice Problems

Problem 1: Digital Circuit
A 4-bit synchronous counter is initialized to 0000. After 37 clock pulses, what is the counter value?

Solution: A 4-bit counter cycles through 16 values (0000 to 1111). After 37 pulses, the counter is at 37 mod 16 =
5. Binary of 5 = 0101.

Problem 2: Memory Addressing

A memory is 64K × 16 bits. How many address lines are needed, and what is the total memory size in bytes?

Solution: 64K = 2¹⁶ words, so 16 address lines. Each word is 16 bits = 2 bytes. Total = 64K × 2 = 128 KB = 131,072
bytes.

Problem 3: Big-O Scaling

An algorithm with time complexity O(n²) takes 4 seconds for n = 1000. How long for n = 10,000?

Solution: n grew 10x, so time grows 10² = 100x. Answer: 400 seconds.

Problem 4: Gate Count

How many 2-input NAND gates are needed to build a 2-input XOR gate?

Solution: XOR using NAND only requires 4 NAND gates in the standard construction.

Problem 5: Pipeline Speedup

A 5-stage pipeline has a clock period of 2 ns. Without pipelining, each instruction takes 10 ns. For 100
instructions, what is the speedup with pipelining?

Solution: Without pipelining: 100 × 10 = 1000 ns. With pipelining: (5 + 99) × 2 = 208 ns. Speedup = 1000 / 208 ≈
4.8×.

Problem 6: Cache Hit Rate

If cache access time is 2 ns, memory access time is 100 ns, and hit rate is 95%, what is the average access time?

Solution: AMAT = Hit × Hit_time + Miss × (Hit_time + Miss_penalty). Approximation: AMAT = 0.95 × 2 + 0.05 ×
100 = 1.9 + 5 = 6.9 ns.
Problem 7: Two's Complement
Represent −45 in 8-bit two's complement.

Solution: +45 = 00101101. Invert: 11010010. Add 1: 11010011. Answer: 11010011.

Problem 8: Flip-Flop Timing

Given tcq = 1.5 ns, tcomb = 6 ns, tsu = 0.5 ns, what is the maximum clock frequency?

Solution: T_min = 1.5 + 6 + 0.5 = 8 ns. Fmax = 1/8 ns = 125 MHz.

Final Quick Revision Sheet
Review this 15 minutes before the exam — do not try to learn anything new from it, just refresh.

Digital Logic Quick Facts

• 2's complement negation: invert all bits + 1. Range for n bits: −2^(n−1) to +2^(n−1)−1.
• Universal gates: NAND and NOR — anything can be built with just one of them.
• De Morgan's: (A·B)' = A' + B' and (A+B)' = A' · B'.
• SOP: from truth table, OR of ANDs for each row where output = 1.
• K-map: group adjacent 1s in powers of 2; larger groups are better.
• Flip-flop timing: Fmax = 1 / (tcq + tcomb + tsu + tskew).
• D flip-flop: Q takes value of D on clock edge.
• JK: J=K=1 toggles. T: T=1 toggles.
• Mealy = output depends on state + input (faster, fewer states); Moore = output depends on state only
(glitch-free).
• Non-blocking (<=) in sequential; blocking (=) in combinational.

Programming Quick Facts

• OOP pillars: Encapsulation, Inheritance, Polymorphism, Abstraction.
• Call by value: copy passed, original unchanged. Call by reference: address passed, original can change.
• Stack = local vars (auto); Heap = malloc/new (manual).
• Pointer: stores address. *p = value at address; &x = address of x.
• Virtual function: enables runtime polymorphism in C++.
• Pure virtual function: makes a class abstract (cannot be instantiated).
• Java has no pointers, no multiple inheritance (uses interfaces), automatic GC.

Data Structures Quick Facts

• Array access: O(1); insert/delete middle: O(n).
• Linked list access: O(n); insert/delete at known node: O(1).
• Stack = LIFO (push/pop at top). Queue = FIFO (enqueue back, dequeue front).
• In-order traversal of BST → sorted output!
• Traversals: Pre (R-L-R), In (L-R-R), Post (L-R-R). Level-order uses queue.
• BFS uses queue (shortest path in unweighted); DFS uses stack/recursion (cycle detection, topological
sort).
• Dijkstra: non-negative weights. Bellman-Ford: handles negatives.
• Binary search: O(log n), requires sorted data.
 • Merge sort: always O(n log n), stable, O(n) space. Quick sort: avg O(n log n), worst O(n²), in-place.
• Hash table average: O(1); worst: O(n).

Computer Architecture Quick Facts

• Von Neumann: unified memory, single bus (bottleneck). Harvard: separate memories and buses.
• Instruction cycle: Fetch → Decode → Execute → Memory → Writeback.
• RISC: few, simple, fixed-size instructions, 1 cycle each. CISC: many, complex, variable-size.
• Pipelining increases throughput; hazards = structural, data (RAW/WAR/WAW), control.
• Locality: temporal (same data soon) + spatial (nearby data soon). Why caches work.
• Cache mapping: direct, fully associative, set-associative. Write policies: through vs back.
• Virtual memory: illusion of large contiguous private memory. Page fault when page not in RAM.
• TLB: cache for page table entries.
• DMA: data transfer without CPU involvement — essential for high-speed I/O.
• Flynn: SISD, SIMD (GPUs), MISD (rare), MIMD (multi-core).

Analytical Quick Facts

• Successive % changes: a + b + (ab/100), not just a + b.
• Average speed (equal distance): 2xy / (x + y).
• Time together: xy / (x + y).
• Permutation (order matters): nPr = n! / (n−r)!.
• Combination (order doesn't matter): nCr = n! / (r!(n−r)!).
• Probability: P(A or B) = P(A) + P(B) − P(A and B).
• km/hr → m/s: multiply by 5/18. m/s → km/hr: multiply by 18/5.
• 1 KB = 2¹⁰; 1 MB = 2²⁰; 1 GB = 2³⁰ bytes.

Common Exam Traps

• Quick sort worst case is O(n²), not O(n log n). Only avg/best are O(n log n).
• Binary search needs sorted data. If data is unsorted, it does not work.
• Synchronous counter is faster than asynchronous (ripple).
• Blocking (=) in sequential Verilog logic is a BUG — always use non-blocking (<=).
• Java does NOT have pointers and does NOT support multiple inheritance of classes.
• Virtual memory ≠ cache. Virtual memory is disk-backed; cache is SRAM on-chip.
• TCP is connection-oriented, UDP is connectionless — if networking questions appear.
• 0! = 1 by convention. Don't treat it as 0.
• Read each MCQ twice — watch for words like 'NOT', 'EXCEPT', 'never', 'always'.
Exam Day Tips
25. Get a full 7–8 hours of sleep tonight. A rested brain recalls much better than a tired one.
26. Eat a light breakfast — something with protein and complex carbs. Avoid heavy/oily food.
27. Reach the test center 20–30 minutes early. Carry ID, registration confirmation, pen, and a watch.
28. Take 30 seconds at the start to skim the paper and identify easy questions.
29. Solve easy questions first. Mark hard ones and return.
30. Do not spend more than 90 seconds on any single question on the first pass.
31. Eliminate obviously wrong answers first — it doubles your odds when guessing.
32. If there is no negative marking, attempt every question. If there is, skip uncertain ones.
33. Reserve the last 5 minutes to review flagged questions and double-check your bubbles/answers.
34. Stay calm. You have prepared well. Trust the work you have done.

Best of luck, Umar!

You have the knowledge. You have prepared.
In sha Allah, you will do great tomorrow.