All topic notes are available here, including when JavaScript or 3D is unavailable. Teaching notes and examples are original study aids; the linked official PDFs define the exam scope.
EM · Engineering Mathematics 30 topics
Reason about structures, change, uncertainty, and the mathematics behind computation. Official syllabus ↗
Propositional logic
Propositions have truth values, and logical connectives combine them into formulas. Truth tables and equivalence laws help establish whether an argument is valid or a formula is always true.
- p → q is equivalent to ¬p ∨ q.
- A tautology is true under every assignment.
- The contrapositive ¬q → ¬p is equivalent to p → q.
Worked example: When is p → q false?
- Replace the implication with ¬p ∨ q.
- A disjunction is false only when both terms are false.
- Thus p must be true and q false.
Answer: Only when p is true and q is false.
Watch out: The converse q → p is not generally equivalent to p → q.
First-order logic
Predicate logic describes properties of objects and adds quantifiers over a specified domain. The order of quantifiers matters because a witness may depend on variables quantified earlier.
- ∀ means every object; ∃ means at least one.
- ¬∀x P(x) is equivalent to ∃x ¬P(x).
- Always state the domain before interpreting a quantified formula.
Worked example: Negate: every integer has a larger integer.
- Write the statement as ∀x ∃y (y > x).
- Negate each quantifier and the inner relation.
- Obtain ∃x ∀y (y ≤ x).
Answer: There exists an integer x such that every integer y satisfies y ≤ x.
Watch out: Negating a quantified statement changes both the quantifiers and the predicate.
Sets and relations
Sets describe collections, while binary relations specify which ordered pairs are related. Equivalence relations group objects into disjoint classes; other relations need not have that structure.
- An equivalence relation is reflexive, symmetric, and transitive.
- A relation on a set of n elements is a subset of n² possible pairs.
- Inclusion–exclusion corrects double counting of overlapping sets.
Worked example: If |A|=8, |B|=7, and |A∩B|=3, find |A∪B|.
- Add the separate counts: 8+7=15.
- The intersection was counted twice.
- Subtract 3 to get 12.
Answer: 12.
Watch out: Symmetric and antisymmetric are different properties; one is not the negation of the other.
Functions
A function assigns exactly one output to each input in its domain. Injective functions preserve distinct inputs, surjective functions reach the entire codomain, and bijections have inverses.
- Injective means f(x)=f(y) implies x=y.
- Surjectivity depends on the chosen codomain.
- Composition applies the inner function first.
Worked example: Is f: Z → Z given by f(x)=2x bijective?
- If 2x=2y then x=y, so it is injective.
- Odd integers have no preimage.
- Therefore it is not onto Z and is not bijective.
Answer: No: it is injective but not surjective.
Watch out: Changing the codomain can change whether the same formula is surjective.
Partial orders and lattices
A partial order is reflexive, antisymmetric, and transitive, but it may leave some elements incomparable. In a lattice, each pair has a unique greatest lower bound and least upper bound.
- A Hasse diagram omits reflexive and transitively implied edges.
- A least element is below every element; a minimal element need not be.
- In divisibility lattices, meet and join often correspond to gcd and lcm.
Worked example: For positive divisors of 12 ordered by divisibility, find meet and join of 4 and 6.
- Their common divisors are 1 and 2, with greatest 2.
- Their common multiples within the set contain 12.
- Thus gcd(4,6)=2 and lcm(4,6)=12.
Answer: Meet = 2; join = 12.
Watch out: A partial order does not require every pair to be comparable.
Monoids and groups
A monoid has a closed associative binary operation and an identity element. A group additionally gives each element an inverse, while commutativity is a separate property.
- Associativity changes parentheses, not operand order.
- A group identity and each element's inverse are unique.
- A commutative group is also called an abelian group.
Worked example: What is the additive inverse of 3 in integers modulo 7?
- An inverse x must satisfy 3+x ≡ 0 (mod 7).
- 3+4=7, which is congruent to 0.
- Thus the inverse is 4.
Answer: 4.
Watch out: Nonzero integers under multiplication do not form a group because most multiplicative inverses are not integers.
Graph connectivity
An undirected graph is connected when every pair of vertices has a path between them. Directed graphs distinguish strong connectivity from connectivity after edge directions are ignored.
- A connected component is a maximal connected vertex set.
- A bridge is an edge whose removal increases the component count.
- A tree is connected and acyclic.
Worked example: A tree has 9 vertices. How many edges does it have?
- A finite tree on n vertices has n−1 edges.
- Substitute n=9.
- The result is 8.
Answer: 8 edges.
Watch out: The n−1 edge count alone does not prove a graph is a tree; connectivity or acyclicity is also needed.
Graph matching
A matching is a set of edges with no shared endpoints. Maximum matching asks for the largest such set, whereas a maximal matching merely cannot be extended by adding an edge.
- A perfect matching covers every vertex.
- Every maximum matching is maximal; the reverse need not hold.
- In a bipartite graph, Hall's condition characterizes a matching that saturates one side.
Worked example: Find a maximum matching in path 1—2—3—4.
- Choose edges that share no endpoint.
- The first and third edges cover all four vertices.
- No matching can exceed floor(4/2)=2 edges.
Answer: {(1,2),(3,4)}, of size 2.
Watch out: Do not confuse the number of matched edges with the number of covered vertices.
Graph coloring
A proper vertex coloring assigns different colors to adjacent vertices. The chromatic number is the smallest number of colors that permits such an assignment.
- A bipartite graph with an edge has chromatic number 2.
- An odd cycle requires 3 colors.
- A clique of size k gives a lower bound of k colors.
Worked example: How many colors does a cycle of length 5 need?
- Alternating two colors fails when the cycle closes.
- Use two colors on the first four vertices.
- A third color on the fifth completes a proper coloring.
Answer: 3.
Watch out: A graph's degree bound is not necessarily its exact chromatic number.
Counting principles
Counting problems begin by deciding whether order matters and whether repetition is allowed. Product rules, combinations, permutations, inclusion–exclusion, and pigeonhole arguments address different constraints.
- Choose r unordered objects from n using C(n,r).
- Arrange r distinct objects from n using n!/(n−r)!.
- For disjoint alternatives, add counts; for successive independent choices, multiply.
Worked example: How many committees of 3 can be chosen from 5 people?
- Order within a committee does not matter.
- Use C(5,3)=5!/(3!2!).
- Evaluate to 10.
Answer: 10.
Watch out: Do not use permutations when rearranging the same selection does not create a new outcome.
Recurrence relations
A recurrence defines a sequence using earlier terms and requires initial values to specify a unique solution. Expansion, characteristic roots, and induction are useful methods, depending on the recurrence.
- Initial conditions matter as much as the recurrence.
- Homogeneous linear recurrences with constant coefficients admit characteristic equations.
- Verify a proposed formula against both recurrence and initial conditions.
Worked example: Solve a₀=1 and aₙ=2aₙ₋₁+1 for n≥1.
- Let bₙ=aₙ+1, giving bₙ=2bₙ₋₁.
- Since b₀=2, bₙ=2ⁿ⁺¹.
- Subtract 1 to recover aₙ.
Answer: aₙ=2ⁿ⁺¹−1.
Watch out: A recurrence solution without the initial-condition constants is incomplete.
Generating functions
An ordinary generating function stores a sequence as coefficients of a formal power series. Multiplication combines coefficient choices, making generating functions useful for counting and solving recurrences.
- The coefficient of xⁿ represents the nth sequence value.
- 1/(1−x)=1+x+x²+… as a formal power series.
- Products correspond to convolution of coefficient sequences.
Worked example: Find the coefficient of x³ in 1/(1−x)².
- Write the expression as (1+x+x²+…)(1+x+x²+…).
- Pairs of exponents summing to 3 are (0,3),(1,2),(2,1),(3,0).
- Each contributes 1, yielding 4.
Answer: 4.
Watch out: A formal generating function can be used algebraically without interpreting x as a numerical probability.
Matrices
Matrices represent linear transformations and systems of linear equations. Matrix multiplication combines transformations and is defined only when the inner dimensions agree.
- An m×n matrix multiplied by an n×p matrix gives an m×p matrix.
- Matrix multiplication generally does not commute.
- The rank is the dimension of the column space and also the row space.
Worked example: Compute [[1,2],[0,1]] times the column vector [3,4].
- First component: 1×3+2×4=11.
- Second component: 0×3+1×4=4.
- Write the resulting two-component column vector.
Answer: [11,4].
Watch out: Do not multiply matrices entry by entry when ordinary matrix multiplication is required.
Determinants and invertibility
The determinant of a square matrix measures signed volume scaling and detects singularity. A matrix is invertible exactly when its determinant is nonzero.
- For [[a,b],[c,d]], determinant = ad−bc.
- Swapping two rows changes the determinant's sign.
- The determinant of a triangular matrix is the product of its diagonal entries.
Worked example: Find det([[2,1],[4,3]]).
- Compute the diagonal product 2×3=6.
- Compute the opposite product 1×4=4.
- Subtract: 6−4=2.
Answer: 2.
Watch out: Row operations have different effects on the determinant; track scaling and swaps explicitly.
Systems of linear equations
A system Ax=b is consistent when b lies in the column space of A. Row reduction reveals whether the system has no solution, one solution, or free variables.
- Consistency requires rank(A)=rank([A|b]).
- A consistent system with n unknowns has a unique solution when rank(A)=n.
- Free variables occur when the rank is smaller than the number of unknowns.
Worked example: Solve x+y=5 and x−y=1.
- Add the two equations to get 2x=6.
- Therefore x=3.
- Substitute into x+y=5 to obtain y=2.
Answer: x=3, y=2.
Watch out: A singular coefficient matrix does not automatically mean no solution; it may mean infinitely many.
Eigenvalues and eigenvectors
An eigenvector is a nonzero vector whose direction is preserved by a linear transformation. Its eigenvalue is the scaling factor, found from det(A−λI)=0.
- Zero is not an eigenvector.
- The sum of eigenvalues with algebraic multiplicity equals the trace.
- The product of eigenvalues with algebraic multiplicity equals the determinant.
Worked example: Find eigenvalues of the diagonal matrix diag(2,5).
- The characteristic determinant is (2−λ)(5−λ).
- Set it equal to zero.
- The coordinate basis vectors are corresponding eigenvectors.
Answer: 2 and 5.
Watch out: Repeated eigenvalues do not guarantee enough independent eigenvectors for diagonalization.
LU decomposition
LU factorization expresses a matrix as a lower triangular matrix times an upper triangular matrix. Gaussian elimination produces the factors; row pivoting may be needed, giving a permuted form PA=LU.
- Solve Ly=b first and then Ux=y.
- Elimination multipliers populate L when its diagonal is chosen as 1.
- Not every nonsingular matrix has an unpivoted LU factorization.
Worked example: Factor A=[[2,1],[4,3]] without pivoting.
- Eliminate the 4 below the first pivot using multiplier 4/2=2.
- Subtract twice row 1 from row 2 to obtain [0,1].
- Store multiplier 2 below L's unit diagonal.
Answer: L=[[1,0],[2,1]], U=[[2,1],[0,1]].
Watch out: Do not assume row swaps can be ignored when elimination encounters a zero pivot.
Limits and continuity
A limit describes the value approached near a point, even if the function is not defined at that point. Continuity additionally requires the function value to equal the two-sided limit.
- A two-sided limit requires equal left and right limits.
- A removable discontinuity can be repaired by redefining one value.
- Algebraic simplification may reveal a limit hidden by a 0/0 expression.
Worked example: Find lim(x→1) (x²−1)/(x−1).
- Factor x²−1=(x−1)(x+1).
- For x≠1 the quotient equals x+1.
- Take the limit of x+1 to obtain 2.
Answer: 2.
Watch out: The expression 0/0 is indeterminate, not a numerical answer.
Differentiability
A derivative measures the local rate of change and the slope of a tangent. Differentiability at a point implies continuity there, but continuity alone does not guarantee a derivative.
- Apply product, quotient, and chain rules according to expression structure.
- A derivative is defined through a limit of difference quotients.
- Corners can make left and right derivatives disagree.
Worked example: Is f(x)=|x| differentiable at x=0?
- For x<0, f(x)=−x and the slope is −1.
- For x>0, f(x)=x and the slope is 1.
- The one-sided derivatives differ at 0.
Answer: No.
Watch out: A continuous graph can still have a nondifferentiable corner.
Extrema and mean value theorem
Optimization finds the largest or smallest function values on the stated domain. The mean value theorem connects an interval's average rate of change to a derivative at an interior point, provided its hypotheses hold.
- Check interior critical points and included endpoints for absolute extrema.
- The mean value theorem requires continuity on [a,b] and differentiability on (a,b).
- A stationary point can be a maximum, minimum, or neither.
Worked example: For f(x)=x² on [0,2], find the mean-value-theorem point c.
- The average slope is (4−0)/(2−0)=2.
- The derivative is f′(x)=2x.
- Solve 2c=2 to get c=1.
Answer: c=1.
Watch out: Do not apply the mean value theorem before checking continuity and differentiability.
Integration
A definite integral accumulates signed contributions over an interval, while an indefinite integral describes a family of antiderivatives. The fundamental theorem of calculus connects accumulation with differentiation.
- Include an arbitrary constant for an indefinite integral.
- A definite integral can be negative when the integrand is negative.
- Substitution and integration by parts simplify different kinds of integrals.
Worked example: Evaluate the integral of 2x from 0 to 3.
- An antiderivative is x².
- Evaluate at the upper and lower limits.
- Compute 3²−0²=9.
Answer: 9.
Watch out: Geometric area and signed integral differ when a function crosses below the axis.
Random variables
A random variable maps outcomes to numbers, allowing probabilities and expectations to be studied numerically. Discrete variables use probability masses; continuous variables use densities whose integrals give probabilities.
- All probability masses sum to 1; a density integrates to 1.
- For a continuous variable, the probability at an individual point is 0.
- Var(X)=E[X²]−(E[X])².
Worked example: A fair die gives X in {1,…,6}. Find E[X].
- Each face has probability 1/6.
- Add the weighted values: (1+2+3+4+5+6)/6.
- Compute 21/6=3.5.
Answer: 3.5.
Watch out: An expected value need not itself be an attainable outcome.
Uniform distribution
A continuous uniform distribution assigns equal density across a finite interval. Probability is proportional to interval length; a discrete uniform distribution instead assigns equal mass to each listed value.
- For continuous U(a,b), density is 1/(b−a) inside the interval.
- Its mean is (a+b)/2.
- Its variance is (b−a)²/12.
Worked example: If X is continuous uniform on [2,8], find P(3≤X≤5).
- The favorable interval has length 5−3=2.
- The full interval has length 8−2=6.
- Probability is 2/6=1/3.
Answer: 1/3.
Watch out: Distinguish a continuous interval from a finite set of equally likely integers.
Normal distribution
A normal distribution is a continuous bell-shaped distribution determined by its mean and variance. Standardization converts it to a standard normal variable for probability calculations.
- For X with mean μ and standard deviation σ>0, Z=(X−μ)/σ.
- The distribution is symmetric about μ.
- Mean, median, and mode coincide.
Worked example: If X is normal with mean 10 and variance 4, what is P(X≤10)?
- The distribution is symmetric around 10.
- Exactly half of its probability lies on either side of its mean.
- A single point has zero probability.
Answer: 0.5.
Watch out: Variance is σ²; use its square root when standardizing.
Exponential distribution
An exponential variable models a nonnegative waiting time with a constant rate parameter λ. It is memoryless: the conditional distribution of additional waiting time does not depend on time already waited.
- For x≥0, P(X>x)=e^(−λx).
- The mean is 1/λ and variance is 1/λ².
- For s,t≥0, P(X>s+t | X>s)=P(X>t).
Worked example: With rate λ=2 per minute, find the mean waiting time.
- The mean of an exponential waiting time is 1/λ.
- Substitute λ=2 per minute.
- Obtain 1/2 minute.
Answer: 0.5 minutes.
Watch out: Rate and mean are reciprocals, not interchangeable parameters.
Poisson distribution
A Poisson variable counts events in a fixed interval under a suitable constant-rate independent-arrival model. Its parameter λ is the expected count in that interval.
- P(X=k)=e^(−λ)λᵏ/k! for k=0,1,2,… .
- Both mean and variance equal λ.
- Scale λ with the interval length when the event rate is constant.
Worked example: For Poisson mean 2, find P(X=0).
- Use k=0 in the probability mass function.
- Since 2⁰=1 and 0!=1, only e⁻² remains.
- Its approximate decimal value is 0.1353.
Answer: e⁻², approximately 0.1353.
Watch out: The event count is discrete even when the time interval is continuous.
Binomial distribution
A binomial variable counts successes in a fixed number of independent trials with the same success probability. Its combinatorial factor counts all placements of a given number of successes.
- P(X=k)=C(n,k)pᵏ(1−p)ⁿ⁻ᵏ.
- Mean = np; variance = np(1−p).
- The number of trials n is fixed in the model.
Worked example: For 3 fair coin tosses, find the probability of exactly 2 heads.
- Choose the 2 head positions in C(3,2)=3 ways.
- Each complete sequence has probability (1/2)³=1/8.
- Multiply to obtain 3/8.
Answer: 3/8.
Watch out: Dependent trials or changing success probabilities generally do not follow the ordinary binomial model.
Mean, median, mode and deviation
Descriptive statistics summarize central tendency and spread. The mean uses every value, the median uses order, the mode uses frequency, and standard deviation measures spread around the mean.
- Sort observations before identifying a median.
- Population variance divides squared deviations by N; the usual unbiased sample variance divides by N−1.
- Standard deviation is the square root of variance and uses the original units.
Worked example: Find the population mean and standard deviation of {2,2,4,4}.
- Mean=(2+2+4+4)/4=3.
- Squared deviations are 1,1,1,1, whose average is 1.
- Take the square root of 1.
Answer: Mean = 3; population standard deviation = 1.
Watch out: State whether the requested variance is a population quantity or a sample estimator.
Conditional probability
Conditioning restricts the relevant outcome space to an event known to have occurred. Independence means that conditioning on one event does not change the other's probability, when the conditional probability is defined.
- P(A|B)=P(A∩B)/P(B), provided P(B)>0.
- Independence gives P(A∩B)=P(A)P(B).
- Mutually exclusive positive-probability events are not independent.
Worked example: A fair die is known to show an even number. What is the probability it is greater than 3?
- The conditional sample space is {2,4,6}.
- The favorable outcomes are {4,6}.
- Divide 2 by 3.
Answer: 2/3.
Watch out: P(A|B) and P(B|A) generally differ.
Bayes' theorem
Bayes' theorem reverses a conditional probability by combining prior probabilities with evidence likelihoods. The denominator accounts for all mutually exclusive ways the evidence could have occurred.
- P(A|B)=P(B|A)P(A)/P(B), when P(B)>0.
- Use total probability to compute P(B) across a partition.
- Posterior probabilities across exhaustive alternatives must sum to 1.
Worked example: Choose one of two boxes equally: A has 3 red of 4 balls, B has 1 red of 4. A red ball is drawn. What is P(A|red)?
- P(red|A)P(A)=(3/4)(1/2)=3/8.
- P(red)=(3/8)+(1/4)(1/2)=1/2.
- Divide (3/8) by (1/2) to obtain 3/4.
Answer: 3/4.
Watch out: Ignoring the prior probabilities can reverse the intended conclusion.
DL · Digital Logic 8 topics
Build reliable digital circuits from Boolean expressions, state, and binary arithmetic. Official syllabus ↗
Boolean algebra
Boolean algebra describes operations on values 0 and 1. Algebraic identities let us prove equivalence between expressions and reduce the hardware needed to implement them.
- AND distributes over OR and OR distributes over AND.
- De Morgan's laws complement both the operands and the operator.
- Absorption gives A+AB=A, where + denotes OR.
Worked example: Simplify A+AB.
- Factor A to write A(1+B).
- In Boolean algebra, 1+B=1.
- Therefore A(1+B)=A.
Answer: A.
Watch out: Boolean addition is OR, so 1+1=1 rather than the arithmetic value 2.
Algebraic minimization
Algebraic minimization rewrites a Boolean function with fewer literals or operations using valid identities. The desired implementation and allowed gates determine which equivalent form is most useful.
- A literal is a variable or its complement.
- SOP is an OR of product terms; POS is an AND of sum terms.
- A simplified expression must preserve every required truth-table output.
Worked example: Simplify AB+A¬B.
- Factor the common A.
- Use B+¬B=1.
- The result is A×1=A.
Answer: A.
Watch out: Fewer written symbols do not always mean a faster circuit under a specific gate library.
Karnaugh maps
A Karnaugh map arranges truth-table cells in Gray-code order so adjacent cells differ in one variable. Combining power-of-two groups eliminates variables that change within each group.
- Valid group sizes are 1,2,4,8,… .
- Opposite map edges are adjacent; diagonal cells are not.
- Don't-care cells may be used when helpful but need not be covered.
Worked example: For variables A,B, minimize F=Σm(1,3).
- Minterm 1 is A=0,B=1; minterm 3 is A=1,B=1.
- The two adjacent cells differ only in A.
- Eliminate A and retain B.
Answer: F=B.
Watch out: Use Gray-code ordering, not ordinary binary ordering, when placing columns.
Tabular minimization
The tabular method systematically combines implicants that differ in one specified bit. A prime-implicant chart then determines a cover for all required minterms.
- Group minterms by their number of 1 bits.
- Combine terms only when their dash positions agree and one remaining bit differs.
- An essential prime implicant uniquely covers at least one required minterm.
Worked example: Combine binary minterms 010 and 011.
- The two minterms differ only in the final bit.
- Replace that bit with a dash.
- The fixed bits A=0 and B=1 remain.
Answer: 01−, representing ¬A B.
Watch out: Finding all prime implicants does not finish the problem; the required minterms still need a suitable cover.
Combinational circuit design
A combinational circuit's outputs depend on its current inputs rather than stored state. Design proceeds from a specification to a truth table, simplified functions, and an implementation using gates or standard building blocks.
- Multiplexers select an input; decoders activate outputs corresponding to input codes.
- A full adder includes a carry input; a half adder does not.
- Propagation delay still exists even though the circuit has no intended memory.
Worked example: For a full adder with A=B=1 and carry-in=0, find sum and carry-out.
- The arithmetic total is 1+1+0=2.
- Binary 2 is 10.
- The low bit is sum 0 and the high bit is carry 1.
Answer: Sum=0; carry-out=1.
Watch out: Do not confuse a combinational circuit's propagation delay with stored state.
Sequential circuit design
Sequential circuits retain state, so outputs can depend on past inputs as well as current inputs. State diagrams, next-state equations, and flip-flop behavior connect the logical specification to clocked hardware.
- A latch is level-sensitive; a flip-flop is commonly edge-triggered.
- Moore outputs depend on state; Mealy outputs depend on state and current input.
- Setup and hold requirements constrain input changes near a sampling edge.
Worked example: A T flip-flop starts at Q=0 and has T=1 at three active clock edges. What is Q?
- With T=1, each active edge toggles the state.
- The state sequence is 0→1→0→1.
- Thus Q=1 after the third edge.
Answer: 1.
Watch out: A clock signal's inactive edge does not trigger an edge-triggered flip-flop specified for the opposite edge.
Fixed-point representation and arithmetic
Fixed-point formats assign a fixed position to the binary point. Signed two's-complement arithmetic uses the same bitwise addition machinery as unsigned arithmetic, but interprets the most significant bit differently.
- An n-bit signed two's-complement integer ranges from −2ⁿ⁻¹ to 2ⁿ⁻¹−1.
- With f fractional bits, the integer bit pattern is scaled by 2⁻ᶠ.
- Signed overflow and an unsigned carry-out are different conditions.
Worked example: Interpret 1110 as a 4-bit two's-complement integer.
- The leading 1 gives a weight of −8.
- The other set bits contribute 4+2.
- The total is −8+4+2=−2.
Answer: −2.
Watch out: The same bit pattern has different values under unsigned and signed interpretations.
Floating-point representation and arithmetic
Floating-point formats represent a sign, a significand, and an exponent, trading uniform precision for a wide range of magnitudes. Arithmetic typically aligns exponents, operates on significands, normalizes, and rounds.
- A binary normalized value has the form ±1.f × 2ᵉ.
- Spacing between representable values grows with magnitude for a fixed significand width.
- IEEE-style formats also define subnormal values, infinities, and NaNs.
Worked example: Normalize binary 110.1.
- Move the binary point left by two places.
- Compensate by multiplying by 2².
- Check: 4+2+0.5=6.5.
Answer: 1.101 × 2², equal to decimal 6.5.
Watch out: Floating-point arithmetic need not be associative because intermediate results are rounded.
COA · Computer Organization and Architecture 10 topics
Follow instructions through a processor, its memory hierarchy, and its input/output interfaces. Official syllabus ↗
Instruction sets
An instruction set specifies the operations and programmer-visible resources a processor supports. Instruction fields encode the operation and how its operands are obtained.
- The ISA is distinct from a particular internal implementation.
- Instruction formats allocate bits among opcodes, registers, and other fields.
- Instruction length and operand count affect encoding choices.
Worked example: A fixed instruction format reserves 6 bits for the opcode. What is the maximum number of distinct opcode patterns?
- Each opcode bit has two values.
- Six bits have 2⁶ distinct patterns.
- Some patterns may be unused in a real ISA.
Answer: 64.
Watch out: The number of possible opcode patterns does not prove that every pattern is implemented.
Addressing modes
An addressing mode explains how an instruction identifies an operand or computes its effective address. Immediate, register, indirect, base-relative, and indexed modes have different memory-access requirements.
- Immediate operands are encoded in the instruction.
- Register indirect addressing treats a register value as a memory address.
- PC-relative addresses use a specified PC value plus an offset.
Worked example: Base register R contains 1000 and displacement is 24. What is the effective address in base-plus-displacement mode?
- Read the register value 1000.
- Add displacement 24 using the stated addressing rule.
- The effective address is 1024.
Answer: 1024.
Watch out: The effective address is not the value stored at that address.
ALU design
An arithmetic and logic unit selects among arithmetic and bitwise operations. Adders, logic gates, multiplexers, and status flags form a basic datapath for these operations.
- Subtraction A−B can be implemented as A+¬B+1 in two's complement.
- Carry propagation influences adder delay.
- Zero, carry, sign, and overflow flags describe different properties of a result.
Worked example: Compute 5−3 using 4-bit two's-complement addition.
- Write 5 as 0101 and 3 as 0011.
- Form −3 as 1101.
- 0101+1101=1 0010; retain the low four bits.
Answer: 0010, representing 2.
Watch out: Discarding carry-out in fixed-width arithmetic does not by itself determine signed overflow.
Hardwired and microprogrammed control
A control unit sequences datapath operations and generates the required control signals. Hardwired control uses logic and state, while microprogrammed control reads a sequence of microinstructions from control memory.
- Control signals select registers, ALU operations, memory actions, and next states.
- Microinstructions describe implementation-level steps rather than necessarily matching ISA instructions one to one.
- The microsequencer chooses the next control-memory address.
Worked example: A microprogram uses 256 control words of 32 bits each. What is its control-store capacity?
- Multiply word count by word width: 256×32=8192.
- Divide by 8 bits per byte.
- The capacity is 1024 bytes.
Answer: 8192 bits, or 1024 bytes.
Watch out: A microprogrammed control store is not the same thing as the program's instruction memory.
Memory interfacing
Memory interfacing connects address, data, and control signals so the intended memory device responds to each access. Address decoding selects a chip or bank, while lower address bits select a location within it.
- Separate address-space size from the width of each stored word.
- Chip count must satisfy both required depth and required width.
- Unselected devices must not drive conflicting values onto a shared data bus.
Worked example: How many 1K×8 chips are needed for a 4K×16 memory?
- Two chips in parallel provide the required 16-bit width.
- Four such banks provide the required 4K depth.
- Multiply 2×4=8.
Answer: 8 chips.
Watch out: Multiplying capacities alone can hide the bank arrangement needed for correct addressing.
Memory hierarchy and performance
A memory hierarchy combines small fast storage with larger slower storage. Locality makes it possible to serve many accesses near the processor, while misses pay the cost of accessing a lower level.
- Temporal locality reuses recent data; spatial locality accesses nearby data.
- For a simple single-cache model, AMAT=hit time+miss rate×miss penalty.
- Clarify whether a quoted miss penalty includes or excludes the initial cache lookup.
Worked example: A cache hit takes 1 ns, miss rate is 5%, and extra miss penalty is 40 ns. Find AMAT.
- Use AMAT=1+0.05×40.
- The miss contribution is 2 ns.
- Add the 1 ns lookup to obtain 3 ns.
Answer: 3 ns.
Watch out: Do not multiply hit time only by the hit rate when using the stated additional-penalty formula.
Cache mapping
Cache mapping determines which cache locations may hold a memory block. Direct mapping gives one possible line, set associativity gives a set of alternatives, and full associativity permits any line.
- For byte addressing, block offset bits equal log₂(block bytes).
- Set index bits equal log₂(number of sets) for power-of-two organizations.
- A tag distinguishes different blocks assigned to the same set.
Worked example: A 32-bit byte-addressed system has a 4 KiB direct-mapped cache with 16-byte blocks. Split the address.
- There are 4096/16=256 cache lines.
- Offset needs log₂16=4 bits and index needs log₂256=8.
- The remaining 32−4−8=20 bits form the tag.
Answer: Offset=4 bits; index=8 bits; tag=20 bits.
Watch out: Use the number of sets, not the total number of lines, for a set-associative index.
Interrupts and DMA
Interrupts notify the processor that an event requires attention, transferring execution to a handler according to the architecture's rules. DMA transfers blocks between a device and memory with a controller managing data movement, reducing per-word CPU intervention.
- An interrupt handler must preserve the state required to resume interrupted work.
- DMA may contend with the CPU for memory or bus access.
- DMA completion can itself be reported by an interrupt.
Worked example: A device transfers a 4096-byte block using DMA. Must the CPU execute a separate copy instruction for every byte?
- The CPU supplies parameters such as source, destination, and count.
- The DMA controller performs the transfers.
- The CPU is notified or checks status when the operation finishes.
Answer: No; it normally configures the transfer and handles completion.
Watch out: DMA reduces CPU copying work; it does not imply zero CPU setup or zero bus cost.
Instruction pipelining
Pipelining overlaps stages of different instructions to improve throughput. An ideal balanced pipeline completes approximately one instruction per cycle after filling, but does not make one instruction traverse fewer stages.
- For k stages and n instructions without stalls, ideal execution takes k+n−1 cycles.
- Clock period must accommodate the slowest stage plus register overhead.
- Pipeline fill and drain matter for short instruction sequences.
Worked example: How many cycles do 6 independent instructions need in an ideal 5-stage pipeline?
- The first instruction requires 5 cycles.
- The remaining 5 complete one per cycle.
- Total=5+6−1=10.
Answer: 10 cycles.
Watch out: Higher throughput is different from lower latency for an individual instruction.
Pipeline hazards
Hazards prevent an instruction from proceeding in its intended pipeline cycle. Structural hazards arise from resource conflicts, data hazards from dependencies, and control hazards from uncertain instruction flow.
- Forwarding can remove some data stalls but not every dependency delay.
- A read-after-write dependency needs the producer's result before the consumer uses it.
- Branch handling and pipeline organization determine control-hazard penalties.
Worked example: In a classic five-stage pipeline, a load is immediately followed by an instruction needing its loaded value in EX. With ordinary forwarding, how many load-use stall cycles are typically needed?
- The load obtains its value at the end of MEM.
- The following instruction would need it in EX one cycle too early.
- Insert one bubble so forwarding can supply the value.
Answer: One cycle under this stated pipeline model.
Watch out: Stall counts depend on the precise stage timing and forwarding paths; one cycle is not universal.
DSA · Programming and Data Structures 10 topics
Trace C programs and understand how data organization determines access, updates, and storage. Official syllabus ↗
Programming in C
C programs operate through typed expressions, control flow, functions, and explicitly managed objects. Reliable tracing requires attention to scope, storage duration, pointer validity, integer conversions, and whether an expression has defined behavior.
- C passes function arguments by value; pointer values can provide access to caller-owned objects.
- Pointer arithmetic is scaled by the size of the pointed-to type and constrained to the relevant array object.
- Undefined behavior has no portable output that can be deduced by ordinary tracing.
Worked example: What does int a[3]={2,4,6}; int *p=a; p++; yield for *p?
- Initially p points to a[0].
- Incrementing an int pointer advances by one int element.
- It now points to a[1], whose value is 4.
Answer: 4.
Watch out: Do not infer a fixed output from unsequenced conflicting modifications or invalid memory access.
Recursion
A recursive function solves a problem through calls on smaller or simpler instances. Each active call normally has its own activation record, and a base case must stop the descent.
- Trace both the call phase and the return phase.
- Maximum active call depth determines stack usage in the ordinary model.
- A correct recurrence for running time must include the number and sizes of recursive calls.
Worked example: For fact(n)=1 when n=0, otherwise n×fact(n−1), find fact(4).
- Expand to 4×3×2×1×fact(0).
- The base case gives fact(0)=1.
- Multiply to get 24.
Answer: 24.
Watch out: A terminating recursion may still repeat substantial work; termination does not imply efficiency.
Arrays
An array stores same-type elements in indexed positions with contiguous storage in the ordinary C array model. This supports constant-time indexed access, while insertion inside an ordered sequence may require shifting elements.
- C array indexing starts at zero.
- For a one-dimensional array, address(a[i])=base+i×element size.
- C multidimensional arrays store the last subscript contiguously.
Worked example: An array starts at byte address 1000 and each element is 4 bytes. Find a[3]'s address.
- Index 3 lies three elements after the first element.
- The byte offset is 3×4=12.
- Add 12 to 1000.
Answer: 1012.
Watch out: The index counts elements, while addresses and element sizes may be stated in bytes.
Stacks
A stack restricts insertion and removal to one end, called the top. Its last-in-first-out behavior supports nested function calls, expression processing, and balanced-delimiter checks.
- Push adds a top element; pop removes it.
- A bounded stack must detect overflow and underflow.
- A sequence of nested operations is naturally reversed when popped.
Worked example: Push 3, push 7, pop, then push 9. What is the stack from bottom to top?
- After two pushes, the stack is [3,7].
- Pop removes 7.
- Push 9 to obtain [3,9].
Answer: [3,9].
Watch out: The oldest element is at the bottom, not the next element to pop.
Queues
A queue inserts at the rear and removes from the front, giving first-in-first-out behavior. Circular arrays reuse freed slots by wrapping indices; linked implementations can also support constant-time endpoint operations.
- Enqueue and dequeue operate at opposite ends.
- Circular indices advance modulo the buffer capacity.
- Full and empty states require a chosen convention, such as a count or an unused slot.
Worked example: Enqueue 2,4,6 into an empty queue, then dequeue once. What remains from front to rear?
- The queue initially becomes [2,4,6].
- Dequeue removes the front element 2.
- The remaining order is 4 then 6.
Answer: [4,6].
Watch out: In a circular queue, equal front and rear indices are ambiguous unless the implementation defines an extra rule.
Linked lists
A linked list connects separately stored nodes through references. It supports local insertion or deletion efficiently when the necessary node references are known, but accessing the ith element requires traversal.
- A singly linked node stores a next link; a doubly linked node also stores a previous link.
- Inserting after a known node takes O(1) pointer changes.
- Finding a value in an unsorted list takes O(n) in the worst case.
Worked example: Insert X between A and B in a singly linked chain A→B.
- Preserve access to B before overwriting A's link.
- Point X to B.
- Redirect A to X.
Answer: Set X.next=B, then A.next=X.
Watch out: Insertion is not O(1) if locating the insertion position itself requires a linear search.
Trees and traversals
A rooted tree represents parent-child relationships without cycles. Tree traversals visit nodes in a defined order; a binary tree limits each node to at most two children.
- Preorder visits root before subtrees; postorder visits root afterward.
- Inorder for a binary tree visits left subtree, root, then right subtree.
- State whether height counts edges or nodes before calculating it.
Worked example: A binary tree has root A, left child B, and right child C. Give its inorder traversal.
- Visit A's left subtree, containing B.
- Visit root A.
- Visit A's right subtree, containing C.
Answer: B, A, C.
Watch out: A binary tree is not necessarily a binary search tree.
Binary search trees
A binary search tree maintains an ordering relation between each node and the values in its subtrees. Searching follows one branch at each comparison, with cost proportional to the tree's height.
- For distinct keys, every left-subtree key is smaller and every right-subtree key larger.
- Inorder traversal produces sorted keys.
- An unbalanced BST can have height n−1 and linear-time search.
Worked example: Insert 5,3,7,4 into an empty BST. Where is 4 placed?
- 4 is smaller than root 5, so go left to 3.
- 4 is larger than 3, so go right.
- Insert at that empty position.
Answer: As the right child of 3.
Watch out: The BST invariant applies to entire subtrees, not just immediate children.
Binary heaps
A binary heap combines a complete binary-tree shape with a heap-order condition. A min-heap makes each parent no larger than its children, putting the minimum at the root without fully sorting all nodes.
- In a zero-based array, children of i are 2i+1 and 2i+2.
- Insert and extract-min are O(log n) in a binary min-heap.
- Bottom-up heap construction runs in O(n), not O(n log n).
Worked example: Is [2,5,3,8,7] a valid min-heap array?
- Root 2 is no larger than children 5 and 3.
- Node 5 is no larger than children 8 and 7.
- Every parent-child relation satisfies min-heap order.
Answer: Yes.
Watch out: Heap order does not require siblings to be sorted.
Graph representations
Graphs model connections between vertices, with directed or undirected edges and optional weights. Adjacency lists and adjacency matrices trade space against different query and traversal costs.
- An adjacency matrix requires Θ(V²) storage.
- Adjacency lists require Θ(V+E) storage in the standard representation.
- An undirected edge appears in both endpoints' lists.
Worked example: For an undirected graph with 5 vertices and 4 edges, how many neighbor entries are stored across all adjacency lists?
- Each edge has two endpoints.
- Store one neighbor entry at each endpoint.
- Therefore there are 2×4=8 entries.
Answer: 8.
Watch out: The graph's number of edges is E, even though undirected adjacency lists usually contain 2E neighbor entries.
ALG · Algorithms 10 topics
Choose strategies, prove correctness, and analyze the resources required to solve computational problems. Official syllabus ↗
Searching
Searching finds a target or establishes that it is absent. Linear search works without order, while binary search repeatedly halves a sorted search interval.
- Linear search has worst-case Θ(n) comparisons.
- Binary search has worst-case Θ(log n) comparisons in a random-access sorted sequence.
- Maintain a precise invariant for which indices may still contain the target.
Worked example: Using midpoint floor((low+high)/2), search for 9 in [1,3,5,7,9] with inclusive indices.
- Start with indices 0…4; midpoint 2 stores 5.
- Retain indices 3…4; midpoint 3 stores 7.
- Retain index 4, which stores 9.
Answer: Compare 5, then 7, then 9: 3 comparisons.
Watch out: Binary search requires an ordering compatible with the comparison and careful boundary updates.
Sorting
Sorting arranges records by a key, and algorithms differ in worst-case cost, extra memory, and stability. A stable algorithm preserves the original relative order of equal-key records.
- Comparison sorting needs Ω(n log n) comparisons in the worst case for arbitrary distinct keys.
- Merge sort has Θ(n log n) worst-case time; typical array implementations need extra storage.
- Quicksort has Θ(n²) worst-case time, although suitable randomized pivoting gives expected Θ(n log n).
Worked example: After the first complete left-to-right bubble-sort pass on [4,1,3,2], what is the array?
- Compare 4 and 1, swapping to [1,4,3,2].
- Compare 4 and 3, giving [1,3,4,2].
- Compare 4 and 2, giving [1,3,2,4].
Answer: [1,3,2,4].
Watch out: Do not report an expected or average cost as a worst-case guarantee.
Hashing
Hashing maps keys to table locations to support fast lookup and updates. Collisions are unavoidable when a larger key space maps into fewer locations, so a collision-resolution method is part of the design.
- Chaining keeps a collection of keys per bucket.
- Open addressing searches alternative table positions according to a probe sequence.
- Expected constant-time operations require assumptions about hashing and load; worst-case lookup can be linear.
Worked example: Insert 10 and 17 into a size-7 table with h(k)=k mod 7 and linear probing.
- Both keys hash to remainder 3.
- Store 10 in empty slot 3.
- For 17, probe the next slot 4.
Answer: 10 goes to slot 3; 17 goes to slot 4.
Watch out: Deleting an open-addressed entry often needs a tombstone so later searches do not stop prematurely.
Worst-case time and space complexity
Asymptotic analysis describes how resource use grows with input size, ignoring constant factors and lower-order terms. Worst-case analysis maximizes the cost over all valid inputs of a fixed size.
- O gives an asymptotic upper bound; Ω gives a lower bound; Θ gives a tight bound.
- Nested loops multiply only when their iteration counts have the corresponding dependence.
- Auxiliary space usually excludes the input storage; state the convention.
Worked example: A loop runs i=1…n and an inner loop runs j=1…i. What is the total iteration count and asymptotic time?
- The inner counts are 1,2,…,n.
- Their sum is n(n+1)/2.
- The quadratic term dominates growth.
Answer: n(n+1)/2 iterations, Θ(n²) time.
Watch out: O(n²) can be true without being tight; use Θ(n²) when both upper and lower bounds are established.
Greedy algorithms
A greedy algorithm repeatedly makes a locally preferred choice without revisiting earlier decisions. Correctness needs a proof that these choices can extend to an optimal solution for the specific problem.
- Exchange arguments often justify a greedy choice.
- Optimal substructure alone does not establish that a greedy rule works.
- An algorithm can be correct for fractional knapsack yet fail for 0/1 knapsack.
Worked example: For compatible activity selection with intervals [1,2),[2,4),[1,5), choose by earliest finishing time.
- The earliest finish is 2, so choose [1,2).
- Among activities starting at or after 2, choose [2,4).
- The interval [1,5) overlaps the chosen activities.
Answer: Select [1,2) and [2,4), giving 2 activities.
Watch out: Use the problem's endpoint convention when deciding whether adjacent activities overlap.
Dynamic programming
Dynamic programming stores solutions to overlapping subproblems and combines them through a recurrence. A useful formulation states exactly what each table entry means and the order in which dependencies are evaluated.
- Memoization computes needed states on demand; tabulation uses an explicit order.
- Separate state definition, transition, base cases, and final answer.
- Time is often the number of states multiplied by the work per transition.
Worked example: For coin values {1,3,4}, what is the minimum number of coins totaling 6 with unlimited coins?
- Define dp[x]=1+min(dp[x−c]) over usable coins, with dp[0]=0.
- Compute dp[3]=1 and dp[6]≤1+dp[3]=2.
- One coin cannot make 6, so 2 is optimal.
Answer: 2 coins: 3+3.
Watch out: A greedy largest-coin choice gives 4+1+1 here and is not optimal.
Divide and conquer
Divide and conquer splits a problem into smaller instances, solves them recursively, and combines the results. The recurrence must include division and combination costs as well as recursive calls.
- Merge sort splits the input and merges sorted halves.
- The Master theorem applies only to recurrences meeting its stated form and conditions.
- Recursive stack space depends on call depth and whether work is stored across calls.
Worked example: Solve T(n)=2T(n/2)+n with T(1)=Θ(1), for powers of 2.
- Each non-leaf recursion level performs Θ(n) combined work.
- There are log₂n such levels.
- Leaf work totals Θ(n), giving Θ(n log n) overall.
Answer: Θ(n log n).
Watch out: Do not apply a recurrence theorem to a different recurrence form without checking its hypotheses.
Graph traversals
Breadth-first search explores vertices in layers using a queue, while depth-first search follows a branch before backtracking. Their visit order depends on the start vertex and the order in which neighbors are considered.
- BFS gives shortest path lengths in an unweighted graph.
- DFS supports cycle analysis and traversal-based structural reasoning.
- Using adjacency lists, both run in O(V+E) over the visited graph.
Worked example: Starting at A, with sorted neighbors, traverse undirected edges A–B, A–C, B–D using BFS.
- Visit A and enqueue B then C.
- Visit B and enqueue its unvisited neighbor D.
- Visit C, then D.
Answer: A, B, C, D.
Watch out: BFS minimizes the number of edges, not total weight in an arbitrarily weighted graph.
Minimum spanning trees
A minimum spanning tree connects every vertex of a connected undirected weighted graph using the smallest total edge weight. Kruskal's and Prim's algorithms exploit safe-edge properties to construct such a tree.
- An MST on V vertices has V−1 edges.
- Distinct edge weights ensure a unique MST, but uniqueness can also occur with ties.
- Disconnected graphs have a minimum spanning forest rather than one spanning tree.
Worked example: A triangle has edge weights AB=1, BC=2, AC=4. Find the MST weight.
- Choose the smallest edge AB of weight 1.
- Choose BC of weight 2 without forming a cycle.
- All vertices are connected with total weight 1+2=3.
Answer: 3, using AB and BC.
Watch out: An MST minimizes total connection cost, not every source-to-vertex path distance.
Shortest paths
Shortest-path algorithms minimize the sum of edge weights along a path. The allowable edge weights and whether one or all sources are queried determine an appropriate algorithm.
- Dijkstra's algorithm requires nonnegative edge weights for its standard correctness guarantee.
- Bellman–Ford handles negative edges and detects reachable negative cycles.
- Floyd–Warshall computes all-pairs distances in O(V³) time.
Worked example: Directed edges are A→B=2, B→C=3, A→C=8. What is the shortest A-to-C distance?
- The direct route costs 8.
- The route A→B→C costs 2+3=5.
- Choose the smaller total, 5.
Answer: 5 via B.
Watch out: A reachable negative cycle can make a finite shortest-path value undefined for affected destinations.
TOC · Theory of Computation 8 topics
Understand which languages machines can recognize, how grammars generate strings, and where computation has fundamental limits. Official syllabus ↗
Regular expressions
A regular expression describes a language using union, concatenation, and repetition. Its symbols denote whole sets of strings, so two expressions are equivalent when they describe exactly the same set.
- Union chooses between languages; concatenation joins one string from each.
- The Kleene star includes zero repetitions, so it always contains the empty string.
- Automata and regular expressions describe the same class of languages.
Worked example: Over {0,1}, what language does (0|1)*01 describe?
- The starred prefix can be any binary string, including empty.
- The final two symbols must be 0 followed by 1.
- 01 and 1101 belong; 010 does not.
Answer: All binary strings ending in 01.
Watch out: Do not confuse the empty language with the language containing only the empty string.
Finite automata
A finite automaton processes input while remembering only one of finitely many states. A DFA has one next state per state-symbol pair; an NFA can have several choices, but neither model recognizes more than the regular languages.
- DFA acceptance depends on the state after all input has been consumed.
- Subset construction converts an NFA with n states to a DFA with at most 2^n states.
- Equivalent DFA states can be merged when no suffix distinguishes their acceptance.
Worked example: A DFA tracks parity of the number of 1s. Starting in even, where does 1011 finish?
- Read 1: even becomes odd.
- Read 0: parity is unchanged.
- Read 1 then 1: odd becomes even, then odd.
Answer: The odd state; it contains three 1s.
Watch out: An accepting state reached midway does not imply acceptance of the entire input.
Regular languages and closure
A language is regular when some finite automaton recognizes it. Closure properties let you construct new regular languages from known ones and can also help prove that a proposed language is not regular.
- Regular languages are closed under union, intersection, complement, concatenation, and star.
- Complementing a DFA requires a complete transition function before swapping accepting states.
- Finite languages are regular, but infinite languages can also be regular.
Worked example: If L is the binary strings with an even number of 1s, is its complement regular?
- Use the complete two-state parity DFA.
- Swap which parity state is accepting.
- The resulting DFA recognizes exactly the complement over {0,1}*.
Answer: Yes: binary strings with an odd number of 1s.
Watch out: State the alphabet when taking a complement; the surrounding universe matters.
Context-free grammars
A context-free grammar replaces one nonterminal at a time using production rules. Parse trees record the hierarchical structure of a derivation; ambiguity means that at least one string has two distinct parse trees.
- A production has one nonterminal on its left-hand side.
- Leftmost and rightmost derivations can describe the same parse tree.
- One ambiguous grammar does not prove that its language is inherently ambiguous.
Worked example: What does S → aSb | ε generate, and how is aabb derived?
- Each recursive production adds one a before S and one b after it.
- The ε production ends the recursion.
- Two recursive steps produce two a symbols followed by two b symbols.
Answer: The language {a^n b^n : n ≥ 0}; S ⇒ aSb ⇒ aaSbb ⇒ aabb.
Watch out: Equal counts alone are insufficient: this grammar also requires every a to precede every b.
Pushdown automata
A pushdown automaton adds an unbounded stack to finite control. Nondeterministic pushdown automata recognize exactly the context-free languages; deterministic pushdown automata recognize a proper subset.
- The stack supports last-in, first-out storage.
- A PDA can push while reading one part of a string and pop while checking another.
- For nondeterministic PDAs, empty-stack and final-state acceptance give equivalent language classes with suitable constructions.
Worked example: How can a PDA recognize aabb in {a^n b^n : n ≥ 0}?
- Begin with a bottom-of-stack marker.
- Read aa and push one marker twice.
- Read bb and pop twice; accept at the end with no unmatched a markers.
Answer: Push two markers for the a symbols, then pop one marker for each b.
Watch out: Specify the switch from the a phase to the b phase; otherwise strings with mixed order may slip through.
Pumping lemmas
Pumping lemmas give necessary properties of regular and context-free languages. To disprove regularity or context-freeness, choose a sufficiently long witness and show that every legal decomposition has some repetition count that leaves the language.
- The regular lemma uses xyz with |xy| ≤ p and |y| > 0.
- The context-free lemma uses uvxyz with |vxy| ≤ p and |vy| > 0, pumping v and y together.
- A language satisfying a pumping condition is not thereby proved regular or context-free.
Worked example: Use the regular pumping lemma to show {a^n b^n : n ≥ 0} is not regular.
- Assume pumping length p and choose a^p b^p.
- Every legal y lies in the first p symbols, so y is one or more a symbols.
- Set the repetition count to 0; the resulting string has fewer a symbols than b symbols.
Answer: Pumping down removes a symbols but no b symbols, breaking equal counts.
Watch out: You choose the witness, but the decomposition is arbitrary: one bad decomposition is not enough.
Turing machines
A Turing machine uses finite control and a read-write tape to model general computation. A decider halts on every input, while a recognizer may run forever on inputs outside its language.
- Each transition may write a symbol, move the head, and change state.
- A decidable language is also recognizable.
- Different standard tape configurations change efficiency but not computability.
Worked example: If a machine accepts members of L and loops on some nonmembers, is it a decider?
- Check behavior on both members and nonmembers.
- Acceptance of all members establishes the positive behavior.
- A single nonhalting input rules out decider status.
Answer: No; it may be a recognizer, but a decider must halt on every input.
Watch out: Do not equate rejection with nonacceptance; looping is a third possible behavior.
Undecidability and reductions
An undecidable decision problem has no algorithm that always halts with the correct yes/no answer on every input. Reductions transfer impossibility: if a known undecidable problem can be solved using a solver for a new problem, the new solver cannot exist.
- The halting problem is undecidable.
- To prove B undecidable, reduce a known undecidable A to B.
- Undecidable does not mean every individual instance is impossible to settle.
Worked example: Suppose a computable transformation converts halting instances to B instances, preserving yes/no answers. Could B have a decider?
- Assume B has a decider.
- Transform any halting instance into the corresponding B instance.
- Run the supposed decider to obtain a forbidden general halting algorithm.
Answer: No; composing the transformation with that decider would decide halting.
Watch out: Reversing the reduction direction does not establish the desired undecidability claim.
CD · Compiler Design 9 topics
Trace source code through tokens, syntax trees, intermediate forms, runtime storage, and program analyses. Official syllabus ↗
Lexical analysis
Lexical analysis groups source characters into tokens such as identifiers, literals, and operators. Token rules are commonly described using regular expressions and implemented with finite automata.
- A token kind differs from its concrete lexeme.
- Whitespace and comments are often discarded outside contexts where they matter.
- Longest-match rules and explicit priorities resolve overlapping token patterns.
Worked example: How is total = count + 12; tokenized?
- Recognize total and count as identifier lexemes.
- Recognize =, +, and ; as separate punctuation/operator tokens.
- Recognize 12 as one integer literal rather than two single-character tokens.
Answer: identifier, assignment, identifier, plus, integer literal, semicolon.
Watch out: A lexer does not generally decide whether the token sequence is a valid expression.
Parsing
Parsing checks whether tokens fit a grammar and constructs their syntactic structure. Top-down parsing predicts productions; bottom-up parsing reduces recognized right-hand sides to nonterminals.
- FIRST and FOLLOW sets help construct predictive parsing tables.
- Immediate left recursion obstructs standard predictive recursive-descent parsing.
- A shift-reduce or reduce-reduce conflict concerns parsing-table choices.
Worked example: With multiplication having higher precedence, how is a + b * c grouped?
- Construct a multiplication subtree for b and c.
- Use that subtree as the right operand of addition.
- The root operator is +, with a as the left operand.
Answer: a + (b * c).
Watch out: Precedence and associativity must come from the grammar or explicit rules, not visual intuition.
Syntax-directed translation
Syntax-directed translation associates semantic rules or actions with grammar productions. Attributes carry information such as types, values, or generated code through the parse structure.
- Synthesized attributes are computed from children.
- Inherited attributes obtain information from parents or siblings under defined rules.
- Attribute dependency graphs determine valid evaluation orders.
Worked example: For E → E1 + T with E.val = E1.val + T.val, what is E.val if the children have values 3 and 4?
- Read the synthesized values 3 and 4 from the children.
- Apply the production's addition rule.
- Attach value 7 to the parent E node.
Answer: 7.
Watch out: An attribute grammar must avoid circular dependencies for the chosen evaluation scheme.
Runtime environments
A runtime environment organizes the storage and control information needed while a program executes. Activation records represent function calls and may contain parameters, local variables, return information, and links to other frames.
- Stack allocation naturally follows properly nested function calls.
- Objects that outlive a call may require storage beyond that call's stack frame.
- Static links and dynamic links serve different purposes.
Worked example: When f calls g and g returns, which call frame is normally removed first?
- Calling g places its activation above the active f frame.
- g uses its frame for its call-specific data.
- Returning from g restores f's execution context.
Answer: g's frame, leaving f's frame active.
Watch out: A recursive function has separate activation records for its simultaneous calls.
Intermediate code generation
Intermediate representations make program operations explicit independently of a particular target machine. Three-address code breaks complex expressions into small assignments and branch operations.
- Temporaries hold intermediate results.
- Control flow can be represented using labels and conditional jumps.
- Expression evaluation order must respect the language's semantics.
Worked example: Write three-address code for x = a + b * c.
- Evaluate the higher-precedence multiplication into t1.
- Add a to that temporary.
- Assign the result to x.
Answer: t1 = b * c; x = a + t1.
Watch out: Algebraic rearrangement can change floating-point behavior or observable side effects.
Local optimization
Local optimization improves code within a basic block, a straight-line region with one entry and one exit. It can simplify expressions or remove unnecessary work when program behavior is preserved.
- Constant folding evaluates compile-time constant expressions.
- A DAG can expose repeated computations within a block.
- Dead assignments can be removed only when their results are unused and their evaluation has no required side effects.
Worked example: Simplify t = 3 * 4; y = t + 2 when integer overflow is irrelevant.
- Fold the multiplication to 12.
- Propagate t's constant into the next expression.
- Fold the addition and then check whether t remains live.
Answer: t = 12; y = 14; t may be removed if it is not used later.
Watch out: A rewrite must preserve exceptions, side effects, and the numeric semantics that apply.
Constant propagation
Constant propagation tracks values known to be the same constant along all relevant paths. At a control-flow join, disagreeing incoming constants usually force an unknown value.
- A forward analysis propagates information from predecessors.
- A fixed point is needed when control flow contains cycles.
- A value is constant at a join only when all feasible incoming paths support it.
Worked example: Two branches assign x = 5 and x = 7 before y = x + 1. Can ordinary constant propagation replace y by one constant?
- Compute x on each incoming branch.
- The values disagree at the join.
- Treat x as nonconstant and retain the computation of y.
Answer: No; y may be 6 or 8.
Watch out: One branch's value cannot be assumed after paths merge.
Liveness analysis
A variable is live at a point when its current value may be read on some future path before being overwritten. Liveness is a backward data-flow analysis that supports register allocation and dead-code elimination.
- OUT of a block is the union of successor IN sets.
- IN = USE ∪ (OUT − DEF).
- A value can be live even if some execution paths never read it.
Worked example: Immediately before x = a + b; print(x); which of a, b, x are live, assuming no later uses?
- The assignment reads a and b, so their current values are needed.
- The assignment overwrites x before print reads it.
- The later print needs the newly assigned x, not its previous value.
Answer: a and b are live; the old value of x is not.
Watch out: Liveness tracks current values, not merely whether a variable name appears later.
Common subexpression elimination
Common subexpression elimination reuses an earlier computed value when the same expression is evaluated again and its operands have not changed. Across blocks, availability information is needed on every incoming path.
- An assignment to an operand can invalidate a saved expression.
- Memory writes and aliasing can invalidate expressions involving loads.
- Reusing an expression must preserve required evaluation effects.
Worked example: Can t2 = a + b reuse t1 in t1 = a + b; a = 8; t2 = a + b?
- Record the operands used by the first expression.
- The assignment a = 8 changes one of those operands.
- The second expression therefore needs a fresh evaluation unless further facts prove equivalence.
Answer: Not in general, because a changes between the computations.
Watch out: Textually identical expressions need not compute the same value at different program points.
OS · Operating System 10 topics
Study how the operating system manages execution, shared resources, memory, storage, and coordination. Official syllabus ↗
System calls
System calls provide controlled entry from user code into operating-system services. A library function may invoke a system call, implement its work entirely in user space, or combine both approaches.
- Privileged operations require a protected transition.
- File access, process creation, and communication are common service families.
- Crossing into kernel mode is not necessarily a switch to another process.
Worked example: Does a system call always imply a context switch to a different process?
- A trap changes the execution privilege and entry point.
- The kernel handles the requested operation.
- The scheduler may keep the same process running if no rescheduling is necessary.
Answer: No; the same process may resume after the kernel completes its request.
Watch out: Mode switch and process context switch are related but different events.
Processes and threads
A process provides an execution environment including an address space and resources. Threads within a process share many resources while each maintains execution state such as a program counter, registers, and stack.
- Separate processes normally have separate virtual address spaces.
- Threads in one process can share global data and heap objects.
- Each thread needs its own call stack for independent execution.
Worked example: Two threads in one process update a shared global counter. Is the counter automatically private to each thread?
- Locate the counter in the process's global storage.
- Both threads access that shared address space.
- Protect the compound update if concurrent access can race.
Answer: No; it is shared, so concurrent updates may require synchronization.
Watch out: Sharing a process does not mean sharing a single stack.
Inter-process communication
Inter-process communication transfers information or coordinates work across process boundaries. Shared memory exposes a common region, while message-based mechanisms transfer data through defined communication operations.
- Shared memory still requires synchronization for conflicting accesses.
- Communication can be blocking or nonblocking.
- Pipes and message queues impose their own ordering and capacity rules.
Worked example: Why is shared memory alone insufficient for two processes that both increment one shared integer?
- Both processes can read the same old value, such as 4.
- Each computes 5 independently.
- Both write 5, although two increments should produce 6.
Answer: Each increment may involve a read-modify-write sequence that can overlap and lose an update.
Watch out: Fast access to shared data does not make compound operations atomic.
Concurrency and synchronization
Concurrent execution allows operations from multiple tasks to interleave. Synchronization constrains those interleavings to protect invariants such as mutual exclusion or ordering between a producer and a consumer.
- A critical section accesses shared state that must be protected.
- Mutexes provide mutual exclusion; semaphores can also count available resources.
- Deadlock freedom, starvation freedom, and mutual exclusion are separate properties.
Worked example: A counting semaphore starts at 3. After two successful wait operations and no signals, what is its value?
- Start with three available units.
- The first successful wait consumes one unit.
- The second consumes another, leaving one.
Answer: 1, under the nonnegative resource-count convention.
Watch out: Semaphore conventions differ when waiters are encoded as negative values; state the convention used.
Deadlock
Deadlock occurs when a set of tasks cannot proceed because each waits for resources or actions held by others in the set. Prevention, avoidance, detection, and recovery address the problem in different ways.
- The classic necessary conditions are mutual exclusion, hold-and-wait, no preemption, and circular wait.
- A cycle proves deadlock for single-instance resource types; with multiple instances it is not sufficient.
- A safe state has some completion order; an unsafe state is not necessarily already deadlocked.
Worked example: P1 holds R1 and waits for R2; P2 holds R2 and waits for R1. Each resource has one instance. What happens?
- P1 cannot obtain R2 because P2 holds it.
- P2 cannot obtain R1 because P1 holds it.
- Neither can reach the action that releases its held resource.
Answer: The two processes are deadlocked if neither resource can be preempted or voluntarily released.
Watch out: Unsafe and deadlocked are not synonyms.
CPU scheduling
CPU scheduling selects which ready task executes next. Scheduling metrics measure different goals, including completion delay, queueing delay, responsiveness, and processor utilization.
- Turnaround time equals completion time minus arrival time.
- For a single CPU burst without I/O, waiting time equals turnaround minus burst length.
- Preemptive policies can interrupt a running task, while nonpreemptive policies wait for it to release the CPU.
Worked example: Under FCFS, P1 and P2 arrive at time 0 with CPU bursts 3 and 2; P1 goes first. What is average waiting time?
- P1 starts immediately, so it waits 0.
- P2 starts at time 3, so it waits 3.
- Average waiting time = (0 + 3) / 2 = 1.5.
Answer: 1.5 time units.
Watch out: Arrival times and tie-breaking rules must be stated before comparing schedules.
I/O scheduling
I/O scheduling orders pending device requests to improve performance or fairness. For a moving-head disk, algorithms such as FCFS and shortest-seek-time-first use different tradeoffs between movement and starvation.
- Seek calculations depend on the initial head position.
- SCAN-style policies also require an initial direction and boundary convention.
- A policy that reduces movement can still delay far-away requests.
Worked example: A disk head starts at cylinder 50 and serves 60 then 20 using FCFS. What is total head movement?
- Move from 50 to 60: |60 − 50| = 10.
- Move from 60 to 20: |20 − 60| = 40.
- Add 10 + 40 = 50.
Answer: 50 cylinders.
Watch out: Do not apply rotating-disk head movement assumptions to every storage technology.
Memory management
Memory management maps process addresses to physical storage and tracks which storage is available. Paging uses fixed-size units, while segmentation represents variable-size logical regions.
- A page offset is unchanged by ordinary page-table translation.
- Paging can introduce internal fragmentation in partially used pages.
- Contiguous allocation and segmentation can suffer external fragmentation.
Worked example: With 1 KiB pages, split virtual address 2500 into page number and offset.
- One page contains 1024 bytes.
- Compute floor(2500 / 1024) = 2.
- Compute 2500 − 2 × 1024 = 452.
Answer: Page 2, offset 452.
Watch out: Distinguish byte-addressed memory from word-addressed memory when calculating offsets.
Virtual memory and page replacement
Virtual memory lets a process address more locations than are resident in physical memory at once. A page fault occurs when a needed page is not resident; replacement policies choose a victim when all frames are occupied.
- A TLB caches translations, not the actual data pages.
- FIFO replacement can exhibit Belady's anomaly.
- LRU and optimal replacement are stack algorithms and do not exhibit that anomaly under the standard model.
Worked example: Using FIFO with three initially empty frames, how many faults occur for 1, 2, 3, 1, 4?
- The first three distinct pages each fault and fill the frames.
- The second reference to 1 is a hit and does not refresh FIFO age.
- Reference 4 faults and evicts the oldest loaded page, 1.
Answer: 4 page faults.
Watch out: A TLB miss need not be a page fault; the page may already be resident.
File systems
A file system organizes persistent data, names, directories, and metadata. Allocation choices such as contiguous extents, linked blocks, and indexed blocks affect access cost, growth, and space overhead.
- A directory associates names with file metadata or identifiers.
- Indexed allocation supports locating blocks without traversing every earlier data block.
- File size limits depend on pointer sizes, block size, and indexing structure.
Worked example: An index block is 1024 bytes and each block pointer is 4 bytes. How many data blocks can one single-level index block address?
- Divide index-block capacity by pointer size.
- 1024 / 4 = 256 pointer entries.
- Each pointer identifies one data block under the stated model.
Answer: 256 data blocks.
Watch out: Account for metadata overhead when a problem says some index-block bytes are reserved.
DB · Databases 8 topics
Model data, express queries, organize indexes, and reason about correct concurrent transactions. Official syllabus ↗
Entity–relationship modeling
An entity–relationship model describes entities, their attributes, and the associations among them. Cardinality and participation constraints express how many associations are allowed and whether participation is mandatory.
- Entity keys distinguish individual entity instances.
- A many-to-many relationship usually becomes a separate relation in relational mapping.
- Weak entities rely on an owner relationship and a partial key for identification.
Worked example: How would a many-to-many Student–Course enrollment relationship normally be mapped?
- Keep each entity's attributes in its own relation.
- Create Enrollment(student_id, course_id, ...).
- Use the identifier pair as a candidate key if repeated enrollment records are not allowed.
Answer: Use Student, Course, and an Enrollment relation containing both identifiers.
Watch out: Cardinality and participation are different: many does not imply mandatory.
Relational model and algebra
The relational model represents data as relations with named attributes and tuples. Relational algebra composes operations such as selection, projection, join, and set difference to describe a query's result.
- Selection filters tuples; projection chooses attributes.
- Classical relational algebra uses set semantics.
- A natural join matches equally named attributes and keeps one copy of each shared attribute.
Worked example: For R(A,B) = {(1,x),(2,y),(3,x)}, what is πA(σB=x(R))?
- Select tuples whose B value is x.
- The remaining tuples are (1,x) and (3,x).
- Project them onto attribute A.
Answer: {(1),(3)}.
Watch out: SQL normally retains duplicates unless DISTINCT or another operation removes them.
Tuple relational calculus
Tuple relational calculus specifies which tuples satisfy a logical condition rather than listing an evaluation procedure. Safe, domain-independent expressions describe finite answers determined by the database contents.
- Tuple variables range over tuples and predicates constrain them.
- Quantifiers express existence and universal conditions.
- Safety avoids results that depend on an unrestricted outside domain.
Worked example: What does {t | Student(t) ∧ t.score > 80} return?
- Restrict t to tuples in Student.
- Evaluate the score predicate for each candidate tuple.
- Keep exactly the tuples satisfying both conditions.
Answer: The Student tuples with score greater than 80.
Watch out: An unrestricted negation such as 'all tuples not in R' can be unsafe.
SQL
SQL expresses retrieval and modification of relational data. Query reasoning requires attention to grouping, duplicate handling, joins, and NULL's three-valued logic.
- WHERE filters rows before grouping; HAVING filters groups.
- COUNT(*) counts rows, while COUNT(column) excludes NULL values in that column.
- Use IS NULL rather than equality to test for NULL.
Worked example: A column contains 5, NULL, and 8. What are COUNT(*) and COUNT(column)?
- There are three rows in total.
- Two rows have non-NULL values in the named column.
- Apply each aggregate's counting rule.
Answer: COUNT(*) is 3; COUNT(column) is 2.
Watch out: NULL comparisons normally produce UNKNOWN, which WHERE does not retain.
Integrity constraints
Integrity constraints restrict database states to those satisfying declared rules. Keys, foreign keys, domain constraints, and checks each enforce a different part of the data model.
- A candidate key uniquely identifies tuples and is minimal.
- A primary key is one selected candidate key.
- Foreign keys constrain references to permitted target rows, subject to the database's NULL and action rules.
Worked example: Enrollment.course_id references Course.id. Can an enrollment normally reference a non-NULL course_id absent from Course?
- Find the referenced Course key.
- Search for the matching identifier.
- If no matching row exists and no deferred repair applies, the constraint is violated.
Answer: No; it violates the foreign-key constraint.
Watch out: A foreign key need not be unique in the referencing relation.
Functional dependencies and normal forms
Normalization uses dependencies to identify redundancy and update anomalies. Decomposition should preserve information through a lossless join, and dependency preservation determines whether constraints can be checked locally.
- BCNF requires the determinant of every nontrivial functional dependency to be a superkey.
- 3NF also allows a non-superkey determinant when the dependent attribute is prime.
- Lossless join and dependency preservation are separate properties.
Worked example: R(A,B,C) has FDs A → B and B → C, and A is the only candidate key. Does R satisfy 3NF?
- A determines B and then C, so A is a key.
- B determines only B and C, not A.
- The dependency B → C violates the stated 3NF conditions.
Answer: No; B → C violates 3NF because B is not a superkey and C is not prime.
Watch out: Check all implied dependencies where required; considering only a convenient subset can hide a violation.
File organization and B/B+ tree indexes
File organization determines how records are physically arranged, while indexes provide additional access paths. Balanced search trees keep search depth bounded; B+ trees store data entries at leaves and commonly link leaves for range scans.
- Heap, sorted, and hashed file organizations suit different access patterns.
- A sparse index relies on an ordering relationship with the underlying data.
- B and B+ tree order conventions vary, so read the definition in each problem.
Worked example: A B+ tree has three levels including the root and leaves. With no cached nodes, how many index-node reads does one root-to-leaf lookup take?
- Read the root node.
- Read one node at the intermediate level.
- Read the target leaf; a separate record fetch may add another read.
Answer: 3 index-node reads, before any separate data-page access.
Watch out: Do not silently treat leaf access as a data-record access when the index stores record pointers.
Transactions and concurrency control
A transaction groups operations into a logical unit with atomicity, consistency, isolation, and durability goals. Concurrency control prevents harmful interleavings while allowing useful overlap.
- Conflicts occur between different transactions on the same item when at least one operation writes.
- A schedule is conflict serializable exactly when its precedence graph is acyclic.
- Recoverability, cascadelessness, and strictness concern additional ordering properties.
Worked example: Schedule: r1(X), w1(X), r2(X), w2(X). What serialization order does its conflict graph imply?
- Compare cross-transaction operations on X.
- Every conflicting pair places T1's operation before T2's.
- The acyclic graph therefore matches the serial order T1 then T2.
Answer: T1 before T2; the graph has edge T1 → T2 and no reverse edge.
Watch out: Serializable does not automatically mean recoverable if commit and read-from ordering are unsuitable.
CN · Computer Networks 13 topics
Follow information through layered protocols, link access, IPv4 routing, TCP, and application exchanges. Official syllabus ↗
Principles of layering
Layering divides communication responsibilities into interfaces and protocols. A layer uses the service below it and offers a service above it; encapsulation adds the control information needed at each stage.
- A protocol describes communication between peer entities.
- A service interface describes what a layer offers its user.
- Headers add overhead, so payload size and total transmitted size differ.
Worked example: A 1000-byte payload receives a 20-byte network header and a 20-byte transport header. Ignoring other layers, what is the resulting size?
- Begin with 1000 bytes of application payload.
- Add 20 bytes at the transport layer.
- Add 20 more bytes at the network layer.
Answer: 1040 bytes.
Watch out: Do not count a header twice when the problem already gives the total packet length.
Circuit, packet, and virtual-circuit switching
Circuit switching reserves communication resources along a path. Packet switching forwards discrete packets; a virtual-circuit system establishes forwarding state so packets follow an identified logical connection.
- Circuit setup and resource reservation differ from per-packet forwarding.
- Datagram packet switching can route packets independently.
- A virtual circuit is not necessarily a dedicated physical wire or reserved bandwidth.
Worked example: Which method establishes a logical path identifier before forwarding packets along that connection?
- Identify the setup step creating per-connection state.
- Packets then carry a short virtual-circuit identifier.
- Switches use that identifier and the incoming interface to choose forwarding actions.
Answer: Virtual-circuit switching.
Watch out: Connection-oriented packet forwarding does not automatically guarantee circuit-like bandwidth.
Network performance metrics
Network delay combines transmission, propagation, processing, and queueing components. Throughput measures the delivered rate, while latency measures how long an individual transfer takes.
- Transmission delay equals packet bits divided by link bit rate.
- Propagation delay equals link distance divided by signal speed.
- Bandwidth-delay product measures how many bits can be in flight under the specified delay.
Worked example: How long does transmitting 1500 bytes take at 10 Mbit/s, ignoring all other delays?
- Convert 1500 bytes to 12000 bits.
- Divide by 10,000,000 bits per second.
- 0.0012 seconds equals 1.2 ms.
Answer: 1.2 milliseconds.
Watch out: Mbps and MB/s differ by a factor of eight.
Error detection
Error-detecting codes add redundancy so a receiver can recognize certain changes to transmitted bits. Parity and cyclic redundancy checks detect different sets of error patterns; detection alone does not correct the data.
- Even parity makes the total count of 1 bits even.
- A CRC uses polynomial division over GF(2), where subtraction is XOR.
- An undetected CRC error pattern is divisible by the generator polynomial.
Worked example: What even-parity bit must be added to data 1011001?
- Count the 1 bits: positions 1, 3, 4, and 7.
- Four is even.
- Append 0 to preserve even parity.
Answer: 0, because the data already contains four 1 bits.
Watch out: A single parity bit detects every odd number of flipped bits, but not every even number.
Medium access control and Ethernet
Medium access control determines how devices share a communication medium. Classic shared half-duplex Ethernet uses collision detection, whereas switched full-duplex Ethernet links do not use CSMA/CD collision handling.
- MAC addresses identify link-layer interfaces within the relevant network context.
- Shared-medium contention and switched full-duplex operation have different assumptions.
- For classic collision detection, minimum transmission duration must cover the round-trip propagation time.
Worked example: For classic CSMA/CD, if one-way propagation is 5 μs, what is the minimum transmission duration required by the collision-detection argument?
- A far-end collision may take one propagation delay to be encountered.
- Its effect takes another propagation delay to return.
- The sender must still be transmitting after 2 × 5 μs.
Answer: At least 10 μs, ignoring other delays.
Watch out: Do not apply collision detection to modern full-duplex Ethernet as if it were a shared hub.
Distance-vector and link-state routing
Distance-vector routing exchanges estimated distances with neighbors and applies a Bellman–Ford-style update. Link-state routing distributes topology information so each router can compute paths from a broader network view.
- Distance-vector updates compare neighbor cost plus the neighbor's advertised distance.
- Link-state shortest paths commonly use Dijkstra's algorithm for nonnegative link costs.
- Transient loops and count-to-infinity are important distance-vector failure behaviors.
Worked example: A reaches B at cost 2 and C at cost 5. B advertises distance 4 to D; C advertises 2. Which next hop is cheaper?
- Via B: 2 + 4 = 6.
- Via C: 5 + 2 = 7.
- Choose B because 6 is smaller.
Answer: B, with total cost 6 instead of 7 through C.
Watch out: A neighbor's advertised distance excludes your own link cost to that neighbor.
IPv4 fragmentation
IPv4 fragmentation splits a datagram when it exceeds a link's MTU and fragmentation is allowed. Fragments carry offsets into the original payload; the offset field uses units of eight bytes.
- Each fragment receives its own IP header.
- Except the last fragment, fragment payload sizes must be multiples of eight bytes.
- The more-fragments flag is 1 except on the final fragment of the original datagram.
Worked example: A 4000-byte IPv4 datagram with a 20-byte header crosses an MTU of 1500 bytes. With no options, what payload sizes and offsets result?
- Original payload is 4000 − 20 = 3980 bytes.
- Each full fragment can carry 1500 − 20 = 1480 bytes, divisible by 8.
- Remaining payload is 1020; offsets are 0, 1480/8, and 2960/8.
Answer: Payloads 1480, 1480, 1020 bytes; offsets 0, 185, 370.
Watch out: Fragment offsets measure original payload position, not total bytes including prior fragment headers.
CIDR and address ranges
CIDR represents an IPv4 prefix using an address and a prefix length. Routers choose the matching route with the longest prefix, while subnet calculations divide the address bits into prefix and host portions.
- An IPv4 /p block contains 2^(32−p) addresses.
- Network boundaries align to the block size.
- Traditional host-count exclusions have special cases such as /31 and /32.
Worked example: What is the range of 192.0.2.64/26?
- A /26 prefix leaves 6 host bits.
- 2^6 = 64 addresses form the block.
- Starting at .64, the final address is .64 + 63 = .127.
Answer: 192.0.2.64 through 192.0.2.127, containing 64 addresses.
Watch out: A routing prefix is not automatically a count of usable end-host addresses.
Network address translation
NAT rewrites address information at a network boundary and maintains mappings where needed. Port translation can distinguish multiple internal connections that share one external IPv4 address.
- Translation can modify addresses, ports, and affected checksums.
- Return traffic must match an appropriate translation mapping.
- Sharing an address does not make the underlying internal connections identical.
Worked example: Two internal clients use source port 5000 to contact the same server. How can a port-translating NAT keep them distinct?
- The internal client addresses distinguish the original flows.
- Choose distinct public endpoint tuples, such as ports 40001 and 40002.
- Use each external tuple to map replies back to the correct client.
Answer: Assign different external source ports and retain separate mappings.
Watch out: NAT is an address-translation mechanism, not a complete security policy.
TCP flow and congestion control
TCP flow control limits sending according to the receiver's advertised capacity, while congestion control adapts to inferred network conditions. The usable sending window is constrained by both the receiver window and the congestion window.
- The receiver window protects receiver buffering.
- The congestion window limits load placed on the network.
- Acknowledgments, loss signals, and timing drive the chosen congestion-control algorithm.
Worked example: If rwnd is 12 KiB and cwnd is 8 KiB, with 3 KiB already unacknowledged, how much more can be sent under this simplified window model?
- Take min(12,8) = 8 KiB as the effective outstanding-data limit.
- Subtract 3 KiB already in flight.
- 8 − 3 = 5 KiB remains.
Answer: 5 KiB.
Watch out: Do not confuse flow control with congestion control or ignore data already in flight.
Socket API
A socket API gives programs operations for establishing and using communication endpoints. A typical TCP server creates a listening socket and obtains a separate connected socket for each accepted connection.
- A common server sequence is socket, bind, listen, accept.
- A common client sequence is socket then connect.
- TCP exposes a byte stream, so application message boundaries require framing.
Worked example: Does one send call guarantee that the peer receives all those bytes in one recv call?
- TCP preserves ordered bytes rather than send-call boundaries.
- The receiver chooses buffer sizes and calls recv as data becomes available.
- Applications must loop and use a length or delimiter protocol when framing messages.
Answer: No; the byte stream may be read in smaller or combined chunks.
Watch out: A successful read returning fewer bytes than requested is not automatically an error.
Domain Name System
DNS resolves domain names through a distributed hierarchy of naming information. Caching reduces repeated work, and record types specify what kind of information is being requested or returned.
- A records associate names with IPv4 addresses.
- Authoritative servers supply data for their zones.
- A cached record's remaining TTL constrains how long it should be reused.
Worked example: A record is cached with TTL 300 seconds. After 120 seconds, how much TTL remains under normal elapsed-time handling?
- Start with 300 seconds.
- Subtract the 120 seconds already elapsed.
- Reuse is limited to the remaining 180 seconds unless refreshed.
Answer: 180 seconds.
Watch out: DNS does not imply a single permanent address for every name.
HTTP
HTTP defines request and response semantics for web resources. Methods, status codes, headers, and bodies communicate the intended operation and its outcome; connection behavior depends on the HTTP version and configuration.
- GET normally requests a representation; POST asks a resource to process submitted content.
- Status-code classes distinguish success, redirection, client errors, and server errors.
- Persistent connections can avoid repeating connection setup for each resource.
Worked example: What does an HTTP 404 response mean at the protocol level?
- The leading 4 places it in the client-error status class.
- The specific code concerns the requested target resource.
- It does not, by itself, prove that the entire server is offline.
Answer: The server did not find a current representation for the target resource, or is unwilling to disclose one.
Watch out: A status code is an application response, distinct from transport connection failure.
GA · General Aptitude 17 topics
Practice precise language, quantitative interpretation, logical reasoning, and spatial transformations. Official syllabus ↗
Tenses and subject–verb agreement
Verb tense places an action in time and can show whether it is completed, ongoing, or connected to another action. Agreement depends on the grammatical subject rather than the nearest noun.
- Identify the head of the subject before choosing the verb.
- Keep time relationships consistent across clauses.
- Singular and plural subjects generally require different present-tense verb forms.
Worked example: Choose the correct verb: 'The list of topics is/are on the desk.'
- The subject head is list, which is singular.
- Of topics modifies list; topics does not control the verb.
- The sentence therefore takes is.
Answer: is.
Watch out: A plural noun inside a prepositional phrase can distract from the actual subject.
Articles and prepositions
Articles signal whether a noun is specific, nonspecific, or used without an article in its context. Prepositions express relationships such as position, time, and association, and many choices depend on established usage.
- Use a/an according to the following sound, not just the written first letter.
- The often identifies a specific or already known referent.
- Preposition choice must fit both meaning and the governing expression.
Worked example: Choose: 'She is a/an honest engineer.'
- Honest begins with a vowel sound because the h is silent.
- The engineer is introduced as a nonspecific person of that description.
- Use an before the vowel sound.
Answer: an honest engineer.
Watch out: An initial written consonant does not always mean an initial consonant sound.
Adjectives, conjunctions, and parts of speech
A word's grammatical role depends on how it functions in a sentence. Adjectives describe nouns, adverbs often modify verbs or adjectives, and conjunctions connect units while expressing relationships such as contrast or cause.
- Distinguish a word's function from its spelling.
- Parallel constructions should connect compatible grammatical forms.
- Choose conjunctions that express the intended logical relationship.
Worked example: Complete: 'The task was difficult, ___ she completed it.' Choose but or because.
- The first clause creates an expectation that completion may be difficult.
- The second clause contrasts with that expectation.
- But expresses the contrast.
Answer: but.
Watch out: A grammatically possible connector can still express the wrong relationship.
Vocabulary, idioms, and phrases
Vocabulary questions often require interpreting a word or phrase within its surrounding sentence. Idioms may have meanings that cannot be obtained by translating their words one by one.
- Use nearby contrasts, explanations, and tone as clues.
- Check whether a candidate word fits both meaning and grammar.
- Recognize figurative expressions without assuming every use is figurative.
Worked example: What does 'break the ice' mean in 'A short introduction helped break the ice'?
- The context is an introduction, not frozen water.
- The phrase describes reducing initial social awkwardness.
- Select the meaning consistent with the whole sentence.
Answer: Make people feel more comfortable at the start of an interaction.
Watch out: A familiar word's first dictionary meaning may be wrong in context.
Reading comprehension
Reading comprehension requires separating what a passage states from what can reasonably be inferred. A sound answer follows the passage's scope and evidence without importing unrelated outside assumptions.
- Identify the main claim and the support offered for it.
- Distinguish a necessary inference from a merely possible explanation.
- Check qualifiers such as some, only, may, and all.
Worked example: A passage says, 'Some students use public transport.' Does it follow that all students use public transport?
- Some asserts at least one student in the ordinary logical reading.
- It does not specify the remaining students.
- All would make a stronger claim unsupported by the sentence.
Answer: No.
Watch out: Do not strengthen a qualified statement while paraphrasing it.
Narrative sequencing
Narrative sequencing places sentences in an order that preserves time, reference, and logical development. Pronouns, connecting words, and cause-effect dependencies provide clues to where a sentence belongs.
- Introduce an entity before a pronoun refers to it when context requires that order.
- Place causes before their stated consequences unless a deliberate flashback is signaled.
- Use opening and concluding sentences to constrain the middle sequence.
Worked example: Arrange: A 'It then produced a report.' B 'The program loaded the data.' C 'Next, it analyzed the records.'
- B introduces the program and starts the operation.
- C follows with analysis of the loaded records.
- A concludes with the generated report.
Answer: B → C → A.
Watch out: Words like then help, but they do not replace checking the meaning of the sequence.
Charts, plots, maps, and tables
Data interpretation translates visual or tabular encodings into quantities and comparisons. Axes, units, scales, legends, and denominators must be identified before performing calculations, particularly in perspective drawings and geographic maps.
- A pie-sector fraction equals its angle divided by 360°.
- Check whether an axis is truncated, logarithmic, or differently scaled.
- For 2D/3D plots and maps, distinguish coordinate values, projected appearance, distance scale, and legend categories.
Worked example: A pie chart represents 240 students. A 90° sector corresponds to how many students?
- Compute the sector's share: 90/360 = 1/4.
- Multiply the total by that share.
- 240 × 1/4 = 60.
Answer: 60 students.
Watch out: Do not infer a 3D bar's value from its apparent volume when its labeled height encodes the data.
Ratios, percentages, and estimation
Ratios compare quantities multiplicatively, and percentages express a quantity relative to a base of 100. Successive percentage changes multiply factors, so equal percentage increases and decreases do not generally cancel.
- A percentage is meaningless without its reference base.
- Convert ratios to common units before using them.
- Estimate magnitude first to catch decimal and order-of-size errors.
Worked example: A price rises by 20% and then falls by 20%. What is its net change?
- Let the starting price be 100.
- After the increase it is 120.
- After the decrease it is 120 × 0.8 = 96.
Answer: A 4% decrease.
Watch out: The second percentage applies to the changed value, not the original value.
Powers, exponents, and logarithms
Exponentiation describes repeated multiplication and its extensions, while logarithms invert exponentiation for a valid base. Manipulating these expressions requires attention to domains and the difference between sums and products.
- For positive x and y, log_b(xy) = log_b x + log_b y.
- A real logarithm requires a positive argument and base b > 0 with b ≠ 1.
- Taking logarithms can turn multiplicative relationships into additive ones.
Worked example: Solve 2^x = 32.
- Write 32 as 2 × 2 × 2 × 2 × 2.
- Thus 32 = 2^5.
- Equal powers of the same valid base have equal exponents.
Answer: x = 5.
Watch out: log(x + y) is not generally log x + log y.
Permutations and combinations
Counting methods depend on whether order matters and whether repetition is allowed. Permutations count ordered selections; combinations count selections in which rearranging the chosen items produces no new outcome.
- For r distinct choices from n, nPr = n!/(n−r)!.
- For unordered selection, nCr = n!/[r!(n−r)!].
- Repeated or indistinguishable objects need additional adjustment.
Worked example: How many committees of 3 can be formed from 5 distinct people?
- Committee membership is unordered.
- Use 5C3 = 5!/(3!2!).
- Evaluate 120/(6 × 2) = 10.
Answer: 10.
Watch out: Assigning different roles changes an unordered committee problem into an ordered selection problem.
Series and numerical sequences
Sequences list terms according to a rule; a series adds those terms. Arithmetic and geometric patterns have different formulas, and finite examples alone may not uniquely determine a rule.
- An arithmetic progression has constant first difference.
- A geometric progression has constant ratio when the ratios are defined.
- State the assumed rule before extending an unfamiliar finite pattern.
Worked example: Find 3 + 6 + 9 + ... + 30.
- There are 10 terms because 30/3 = 10.
- The arithmetic-series average term is (3 + 30)/2 = 16.5.
- Multiply 10 × 16.5 = 165.
Answer: 165.
Watch out: A sequence's nth term and the sum of its first n terms are different quantities.
Mensuration and geometry
Geometry reasons about shapes, angles, distances, and similarity; mensuration computes quantities such as area and volume. Scaling relationships help compare figures without recalculating every dimension.
- Uniform length scaling by k changes areas by k² and volumes by k³.
- Use consistent units before substituting into formulas.
- Distinguish surface area from cross-sectional area and volume.
Worked example: If every edge of a cube doubles, how does its volume change?
- Cube volume is side³.
- The new side is 2 times the old side.
- The new volume factor is 2³ = 8.
Answer: It becomes 8 times the original volume.
Watch out: Doubling length does not merely double area or volume.
Elementary statistics and probability
Statistics summarizes observed values, while probability describes uncertainty under a specified model. Averages and probabilities depend on how outcomes are weighted and whether events interact.
- An arithmetic mean is sum divided by count.
- Probability lies between 0 and 1 for any event.
- Multiply probabilities directly for joint events only when independence or the proper conditional structure is established.
Worked example: For a fair six-sided die, what is the probability of an even number?
- The equally likely outcomes are 1 through 6.
- The favorable outcomes are 2, 4, and 6.
- Probability = 3/6 = 1/2.
Answer: 1/2.
Watch out: Equally likely outcomes are an assumption, not a default for every real-world process.
Deduction and induction
Deductive reasoning derives conclusions that must follow from accepted premises. Inductive reasoning generalizes from observations and can support a conclusion without making it logically certain.
- A valid deduction preserves truth when its premises are true.
- An inductive pattern can be overturned by a counterexample.
- Distinguish a statement from its converse and inverse.
Worked example: All routers in a lab are powered on. Device R is a router in that lab. Must R be powered on?
- The universal statement applies to every router in the lab.
- R is explicitly a member of that set.
- Therefore the stated property applies to R.
Answer: Yes, given those premises.
Watch out: If all A are B, it does not follow that all B are A.
Analogy and numerical reasoning
An analogy asks for a relationship that is preserved across two pairs or structures. Numerical reasoning requires identifying a rule consistent with the stated constraints and checking it against all provided information.
- Name the relation before trying answer choices.
- Check direction: A relates to B may differ from B relating to A.
- A short number list can support multiple patterns unless constraints disambiguate it.
Worked example: Complete the square analogy 4 : 16 :: 7 : ? using the relation 'second number is the square of the first'.
- The specified relation maps x to x².
- Verify it gives 4² = 16.
- Apply it to 7: 7² = 49.
Answer: 49.
Watch out: Do not claim a guessed pattern is uniquely determined without enough information.
Translation, rotation, scaling, and mirroring
Spatial transformations change a figure's location, orientation, size, or handedness according to a rule. Tracking a few labeled points helps distinguish a rotation from a reflection and prevents confusion caused by perspective.
- Translation preserves both shape and orientation.
- Rotation preserves distances and handedness; reflection reverses orientation in the plane.
- Uniform scaling preserves shape but changes lengths by its scale factor.
Worked example: Rotate point (2,1) by 90° counterclockwise about the origin in the usual Cartesian plane.
- For a 90° counterclockwise rotation, map (x,y) to (−y,x).
- Substitute x = 2 and y = 1.
- The rotated point is (−1,2).
Answer: (−1,2).
Watch out: Specify the center, direction, and viewing convention before performing a rotation.
Assembly, grouping, folding, cutting, and patterns
Spatial assembly combines parts while respecting shared faces, edges, and orientation. Folding and cutting problems can be solved by reversing folds and reflecting each cut across the corresponding crease, while pattern questions track repeated structural changes.
- A cut through stacked layers appears in every layer it crosses.
- Unfold in the reverse order of folding.
- For cube nets and 3D assembly, track adjacency and opposite faces rather than relying only on a flat outline.
Worked example: A sheet is folded once along its vertical centerline. One hole is punched through both layers away from the crease. How many holes appear after unfolding?
- The punch passes through two stacked layers.
- Unfolding separates those layers back into the sheet.
- Each layer contributes one hole, at reflected positions across the crease.
Answer: 2 mirror-related holes.
Watch out: A hole on the crease or overlapping repeated cuts changes the usual counting argument.