Final Examination 2024 (12th Batch) — Full Solution

Eight questions from the Jagannath University B.Sc. in CSE 4th Year 1st Semester Final Examination 2024 (CSE-4105, 12th Batch) — full worked solutions covering computer graphics fundamentals and drivers, raster vs vector graphics with advantages and disadvantages, display hardware and application areas, the DDA algorithm traced for $(2,6) \rightarrow (4,10)$, the Mid-point circle algorithm derived and traced for radius $3$ at center $(4,4)$, decision variables and mid-point coordinates for both E and SE choices in the midpoint circle, 2D and 3D translation in homogeneous matrix form, homogeneous coordinates and conversion of the translation matrix, 2D rotation of $P=(4,2)$ by $90°$ and 3D rotation with equations/matrices/figures, parallel vs perspective projection with equations and figures, one/two/three-point vanishing points, the RGB color model with advantages/disadvantages, RGB-to-CMY conversion and CMY uses, Z-buffer placement of four polygons on a $6 \times 6$ pixel grid with depth range $[0, 10]$, the Cohen-Sutherland line clipping algorithm and viewport definition, Sutherland-Hodgman polygon clipping of pentagon ABCDE, the basic scan-fill polygon algorithm and interior pixel convention, Bezier vs B-spline curves, the Z-buffer algorithm with a worked two-polygon example, illumination vs shading model, halftone approximation, linear vs non-linear multimedia, entropy calculation for an alphabet $\{X, Y\}$, lossless vs lossy compression, and Huffman coding for the string AABABBBBEBECCCCCDDD.

Question 1 — Computer Graphics Fundamentals, Raster vs Vector, Display Hardware & Applications

(a) What is computer graphics? Write some drives for introducing computer graphics. [1+3]

(b) Define and differentiate vector and raster graphics. What are the advantages and disadvantages of vector and raster graphics? [3+2]

(c) Briefly discuss about display hardware used in computer graphics. What are the common application areas of computer graphics? [3+2]

Concept Needed

Computer graphics is the discipline of generating, manipulating, storing and displaying visual content with computers. The field spans low-level pixel rasterization and high-level scene modeling. Two storage models — raster (pixel-based) and vector (geometry-based) — define the fundamental trade-off in image representation, and the display hardware layer (CRT → LCD → LED → OLED) carries the framebuffer to the viewer's eye.

(a) Definition and Drivers

Definition. Computer graphics is the branch of computer science concerned with the creation, manipulation, storage, and display of images, models, and visual information using computers. It includes everything from low-level pixel rasterization to high-level scene modeling, animation, and rendering.

Drivers (why computer graphics matters):

1. Better visual communication — graphics convey information faster and more clearly than text; charts, diagrams, and animations help users interpret complex data quickly.
2. User-interface enhancement — modern operating systems and applications rely on GUIs (windows, icons, menus, pointers), making computers accessible to non-technical users.
3. Realistic simulation and training — flight simulators, medical training, military drills, and driving simulators provide safe, cost-effective practice environments.
4. Entertainment industry — movies (CGI, VFX), video games, animations, and VR/AR content depend entirely on computer graphics.
5. Scientific visualization — researchers visualize molecular structures, weather patterns, astronomical data, and fluid dynamics that would otherwise be impossible to observe.
6. Computer-aided design (CAD/CAM) — engineering, architecture, and product design use graphics to model, simulate, and analyze designs before physical production.
7. Medical imaging — CT, MRI, and ultrasound rely on graphics techniques to construct 3D views of internal body structures for diagnosis.

(b) Raster vs Vector Graphics

Raster graphics (bitmap): images composed of a fixed grid of pixels, each storing a color value. Resolution is fixed; zooming causes pixelation.

Vector graphics: images defined by mathematical equations, geometric primitives (points, lines, curves, polygons), and their attributes (color, fill, stroke). Resolution-independent — scales infinitely without quality loss.

Vector — Advantages: resolution-independent; small file size for simple art; easy object-level editing; precise geometric shapes; ideal for CAD and print. Vector — Disadvantages: unsuitable for complex photographic content; rendering can be slow for highly detailed scenes; limited photorealism.

Raster — Advantages: excellent for realistic images; simple capture from cameras and scanners; fast pixel-level operations (filters, color correction). Raster — Disadvantages: quality degrades on scaling; large file sizes at high resolution; memory intensive; per-pixel editing is tedious.

(c) Display Hardware & Application Areas

Display hardware translates the framebuffer (a raster image in GPU memory) into visible light on a screen.

• CRT (Cathode Ray Tube) — vacuum tube with electron guns that scan a phosphor-coated screen. Three guns for RGB. Now legacy.
• LCD (Liquid Crystal Display) — modulates a backlight through liquid crystal cells sandwiched between polarizers. Dominant in monitors and laptops.
• LED (Light Emitting Diode) displays — each pixel is an LED. Used in stadium displays, billboards, and modern TVs; LED can also refer to LED-backlit LCD panels.
• Plasma Display Panels (PDP) — small cells filled with ionized gas (plasma) that emit light when electrically stimulated. Historically important for large TVs.
• OLED (Organic LED) — self-emissive organic compounds; superior contrast, deeper blacks, flexible screens.
• Video cards / GPUs — dedicated hardware (NVIDIA, AMD) that performs parallel rendering, rasterization, and 3D acceleration.
• Display controllers — interface between CPU and display; manage the frame buffer (video memory) where pixel data is stored.

Common application areas:

1. Computer-Aided Design (CAD) — engineering, architecture, mechanical design.
2. Entertainment — movies, video games, animation.
3. Education and training — e-learning, flight simulators, surgical simulators.
4. Scientific visualization — meteorology, astronomy, biology, fluid dynamics.
5. Medical imaging — CT, MRI, ultrasound visualization.
6. Business — presentations, data visualization, dashboards.
7. Virtual Reality (VR) and Augmented Reality (AR).
8. Geographic Information Systems (GIS) — maps and terrain modeling.

Related Conceptual Questions

Q1.1. If a logo must appear both on a 1080p monitor and on a 5-meter outdoor banner, which format should you keep the master in?

A1.1. SVG (vector). A raster master at 1080p will pixelate when scaled to 5 meters; the SVG stores the logo as mathematical primitives that scale cleanly to any output size, including large-format print.

Q1.2. Why did LCDs replace CRTs for consumer computer displays, even though CRTs had excellent color and viewing angles?

A1.2. LCDs are thinner, lighter, draw less power, emit less heat, and have no burn-in risk. Manufacturing economies of scale also drove LCD panel prices far below CRT equivalents, ending the CRT's commercial life by the late 2000s.

Q1.3. Why are GPUs designed around rasterization rather than vector rendering at the hardware level?

A1.3. The framebuffer — the data the display actually reads — is inherently raster. Even vector formats (SVG, fonts, vector games) must be rasterized at display time. Building hardware around the final on-screen representation (pixels) avoids a redundant vector→raster step and lets the GPU pipeline specialize in massively parallel pixel ops.

Question 2 — DDA Line Algorithm for (2,6)→(4,10) and Mid-Point Circle for r=3 at (4,4)

(a) Explain the DDA (Digital Differential Analyzer) algorithm and trace the algorithm for the given points $(2, 6)$ to $(4, 10)$. [7]

(b) Derive the Midpoint circle algorithm. Considering the midpoint circle algorithm, draw a circle with radius $3$ and center $(4, 4)$. [7]

Concept Needed

The DDA algorithm is a line-drawing procedure based on calculating intermediate points along a straight line by sampling $x$ at unit intervals and computing $y$ from the line equation. It is simple but uses floating-point arithmetic and rounding. The midpoint circle algorithm is an integer-only rasterization method that exploits the 8-fold symmetry of circles — computing one octant and reflecting to obtain the other seven.

(a) DDA Algorithm — Theory

For a line from $(x_1, y_1)$ to $(x_2, y_2)$, the slope is $m = (y_2 - y_1) / (x_2 - x_1)$. Starting at $(x_1, y_1)$, each successive point is sampled by stepping in the dominant direction:

$x_{k+1} = x_k + \Delta x, \qquad y_{k+1} = y_k + \Delta y$

where $\Delta x = dx / \text{steps}$ and $\Delta y = dy / \text{steps}$, with $\text{steps} = \max(|dx|, |dy|)$.

Algorithm:

1. Read the endpoints $(x_1, y_1)$ and $(x_2, y_2)$.
2. Compute $dx = x_2 - x_1$, $dy = y_2 - y_1$.
3. Compute $\text{steps} = \max(|dx|, |dy|)$.
4. Compute $\Delta x = dx / \text{steps}$ and $\Delta y = dy / \text{steps}$.
5. Initialize $x = x_1$, $y = y_1$, plot $\text{round}(x)$, $\text{round}(y)$.
6. Repeat steps times: $x = x + \Delta x$, $y = y + \Delta y$, plot $\text{round}(x)$, $\text{round}(y)$.

Disadvantages: uses floating-point arithmetic and rounding, so it is slower than Bresenham's integer-only algorithm.

(a) Trace for (2, 6) → (4, 10)

Given: $(x_1, y_1) = (2, 6)$, $(x_2, y_2) = (4, 10)$.

Step 1: Compute differences

$dx = 4 - 2 = 2, \qquad dy = 10 - 6 = 4$

Slope: $m = dy / dx = 4 / 2 = 2$.

Step 2: Compute steps and increments

$\text{steps} = \max(|2|, |4|) = 4$ $\Delta x = 2 / 4 = 0.5, \qquad \Delta y = 4 / 4 = 1$

Step 3: Tabulate

Generated points: $(2, 6), (3, 7), (3, 8), (4, 9), (4, 10)$.

(b) Mid-Point Circle Algorithm — Derivation

A circle of radius $r$ centered at the origin has the implicit equation:

$x^2 + y^2 = r^2$

Define the function:

$f(x, y) = x^2 + y^2 - r^2$

• $f(x, y) < 0$ → inside the circle.
• $f(x, y) = 0$ → on the circle.
• $f(x, y) > 0$ → outside the circle.

Because a circle has 8-fold symmetry, we compute only one octant (start at $(0, r)$, walk in $+x$ / $-y$) and reflect to obtain the other seven.

At each step from pixel $(x_i, y_i)$ we choose between:

• East (E): $(x_i + 1, y_i)$
• South-East (SE): $(x_i + 1, y_i - 1)$

The mid-point between them is:

$M = \left(x_i + 1,\ y_i - \tfrac{1}{2}\right)$

Decision parameter:

$p_i = f(M) = (x_i + 1)^2 + \left(y_i - \tfrac{1}{2}\right)^2 - r^2$

• $p_i < 0$ → mid-point is inside the circle → choose East.
• $p_i \ge 0$ → mid-point is on or outside the circle → choose South-East.

Recurrences (substituting $x_{i+1} = x_i + 1$):

• If East chosen ($y$ unchanged): $p_{i+1} = p_i + 2x_i + 3$
• If SE chosen ($y$ decreases by 1): $p_{i+1} = p_i + 2x_i - 2y_i + 5$

Initial value at $(x_0, y_0) = (0, r)$ — substituting $M = (1, r - \tfrac{1}{2})$:

$p_0 = f\left(1, r - \tfrac{1}{2}\right) = 1 + r^2 - r + \tfrac{1}{4} - r^2 = \tfrac{5}{4} - r$

The integer-friendly form used in textbooks is $p_0 = 1 - r$ — only the sign matters for the decision, so subtracting $\tfrac{1}{4}$ from every subsequent $p$ does not change any sign.

(b) Trace for radius 3 at center (4, 4)

For $r = 3$:

$p_0 = 1 - r = 1 - 3 = -2$

$p_0 < 0$, so the first step is East. The center is then added at the end as $(x_c + \text{relative-}x, y_c + \text{relative-}y)$.

With $2x + 3$ and $2x - 2y + 5$ updates at each iteration, starting from $(x_0, y_0) = (0, 3)$:

Step-by-step:

• Start: $(0, 3)$, $p = -2$ → E.
• Step 1 (E): $x=1, y=3$, $p = -2 + 2(0) + 3 = 1 \ge 0$ → SE.
• Step 2 (SE): $x=2, y=2$, $p = 1 + 2(1) - 2(3) + 5 = 2 \ge 0$ → SE.
• Step 3 (SE): $x=3, y=1$, $p = 2 + 2(2) - 2(2) + 5 = 7 \ge 0$ → SE.
• The next SE would drive $y$ to $0$; we stop at the boundary of the octant.

Octant-2 pixels (relative to center): $(0, 3), (1, 3), (2, 2), (3, 1)$.

Adding center $(4, 4)$: $(4, 7), (5, 7), (6, 6), (7, 5)$.

Full circle via 8-fold symmetry around $(4, 4)$ — for each octant-2 pixel $(x, y)$ relative to the center, the eight reflected pixels are obtained by $(\pm x, \pm y)$ and $(\pm y, \pm x)$, then adding the center $(4, 4)$:

Distinct boundary pixels (radius 3, center $(4, 4)$): $(1, 3), (1, 4), (1, 5), (2, 1), (2, 6), (2, 7), (3, 1), (3, 7), (4, 1), (4, 7), (5, 1), (5, 7), (6, 2), (6, 6), (7, 3), (7, 4), (7, 5)$ and the four corner pixels $(2, 2), (2, 6), (6, 2), (6, 6)$ — 20 distinct boundary points forming the integer rasterization of the circle.

Related Conceptual Questions

Q2.1. Why is DDA slower than Bresenham's line algorithm in practice?

A2.1. DDA performs floating-point addition and rounding at every step. Bresenham avoids floats entirely by using an integer decision variable that is updated by small integer increments, making Bresenham faster on hardware without fast FPUs and equally accurate for the integer pixel grid.

Q2.2. Why does the midpoint circle algorithm compute only one octant?

A2.2. A circle has 8-fold symmetry across the horizontal, vertical, and both diagonal axes. Computing one octant (45°) and reflecting yields the other seven at zero extra cost — an 8× reduction in computation.

Q2.3. Why is the initial decision parameter $p_0 = 1 - r$ acceptable when the true value is $\tfrac{5}{4} - r$?

A2.3. Only the sign of $p$ drives the next-step decision. Subtracting $\tfrac{1}{4}$ from every subsequent $p$ (which is what switching from $\tfrac{5}{4} - r$ to $1 - r$ does) preserves every sign, so the algorithm produces the same output while keeping all values integer — a friendlier implementation.

Question 3 — Decision Variables, 2D & 3D Translation, Homogeneous Coordinates

(a) Derive the equation for decision variable (both initial and new) for mid-point circle algorithm. Also derive the equations for calculating mid-point (both for E and SE). [3+3]

(b) What is Transformation? Calculate the 2-D and 3-D Translation equations and convert in matrix form. [1+4]

(c) Why homogeneous coordinates are used in transformation? Convert the derived matrix form of question no. 3(b) in homogeneous form. [3]

Concept Needed

A decision variable in the midpoint circle algorithm is an integer-only quantity whose sign tells the algorithm which neighbor pixel is closer to the true circle arc. The same idea underlies Bresenham's line algorithm. Translation is the rigid shift of an object by a vector — it is additive (not multiplicative) in plain coordinates but becomes a matrix multiplication once we adopt homogeneous coordinates, which is what enables a single composite matrix for any sequence of affine operations.

(a) Decision Variable Derivation (Mid-Point Circle)

For a circle centered at the origin with radius $r$, define the implicit function:

$f(x, y) = x^2 + y^2 - r^2$

• $f < 0$ → inside the circle.
• $f = 0$ → on the circle.
• $f > 0$ → outside the circle.

For the first octant, $x$ increases and $y$ decreases. At step $(x_i, y_i)$, the mid-point between the two candidates is:

$M = \left(x_i + 1,\ y_i - \tfrac{1}{2}\right)$

The decision parameter is:

$p_i = f(M) = (x_i + 1)^2 + \left(y_i - \tfrac{1}{2}\right)^2 - r^2$

Initial decision parameter. Substituting $M = (1, r - \tfrac{1}{2})$ (the first mid-point starting from $(0, r)$):

$p_0 = 1 + \left(r - \tfrac{1}{2}\right)^2 - r^2 = 1 + r^2 - r + \tfrac{1}{4} - r^2 = \tfrac{5}{4} - r$

The integer form used in textbooks is $p_0 = 1 - r$.

Updated decision variable. Substituting $x_{i+1} = x_i + 1$ and either $y_{i+1} = y_i$ (E) or $y_{i+1} = y_i - 1$ (SE):

• East chosen ($p_i < 0$, $y$ unchanged):

$p_{i+1} = (x_i + 2)^2 + \left(y_i - \tfrac{1}{2}\right)^2 - r^2 = p_i + 2x_i + 3$

• South-East chosen ($p_i \ge 0$, $y$ decreases by 1):

$p_{i+1} = (x_i + 2)^2 + \left(y_i - \tfrac{3}{2}\right)^2 - r^2 = p_i + 2x_i - 2y_i + 5$

Mid-point coordinates for E and SE choices (used to evaluate the decision variable at the next step):

• East mid-point (between $(x_i+1, y_i)$ and $(x_i+2, y_i)$):

$M_E = \left(x_i + 2,\ y_i - \tfrac{1}{2}\right)$

• South-East mid-point (between $(x_i+1, y_i-1)$ and $(x_i+2, y_i-1)$):

$M_{SE} = \left(x_i + 2,\ y_i - \tfrac{3}{2}\right)$

(b) Transformation & 2-D / 3-D Translation

Definition. A transformation is the process of modifying the coordinates, size, shape, or orientation of a graphical object. The four fundamental 2D transformations are translation, rotation, scaling, and reflection; in 3D we add shear and projection.

2-D translation. A 2-D point $(x, y)$ is moved by translation distances $t_x$ (along $x$) and $t_y$ (along $y$):

$x' = x + t_x$ $y' = y + t_y$

2-D translation matrix form:

$$\begin{bmatrix} x' \\ y' \end{bmatrix} = \begin{bmatrix} x \\ y \end{bmatrix} + \begin{bmatrix} t_x \\ t_y \end{bmatrix}$$

3-D translation. A 3-D point $(x, y, z)$ is moved by translation distances $(t_x, t_y, t_z)$:

$x' = x + t_x$ $y' = y + t_y$ $z' = z + t_z$

3-D translation matrix form:

$$\begin{bmatrix} x' \\ y' \\ z' \end{bmatrix} = \begin{bmatrix} x \\ y \\ z \end{bmatrix} + \begin{bmatrix} t_x \\ t_y \\ t_z \end{bmatrix}$$

(c) Why Homogeneous Coordinates, and the Homogeneous Form of the Matrices

Why homogeneous coordinates are used:

1. Unified matrix representation. In plain coordinates, translation is additive while rotation/scaling are multiplicative. In homogeneous form, every affine transformation becomes a single matrix multiplication.
2. Composite transformations. Multiple sequential operations (e.g. scale → rotate → translate) collapse into a single composite matrix $M = T \cdot R \cdot S$.
3. Pipeline-friendly. Graphics pipelines (CPU vertex stage → GPU shader) expect $4 \times 4$ (3D) or $3 \times 3$ (2D) matrices for every operation; homogeneous form is the lingua franca.
4. Hardware efficiency. GPU shader cores are built around $4 \times 4$ matrix-vector multiplies; treating every transform uniformly simplifies the silicon.

2-D translation in homogeneous form. Append a third coordinate $w = 1$:

$$\begin{bmatrix} x' \\ y' \\ 1 \end{bmatrix} = \begin{bmatrix} 1 & 0 & t_x \\ 0 & 1 & t_y \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} x \\ y \\ 1 \end{bmatrix}$$

3-D translation in homogeneous form. Append a fourth coordinate $w = 1$:

$$\begin{bmatrix} x' \\ y' \\ z' \\ 1 \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 & t_x \\ 0 & 1 & 0 & t_y \\ 0 & 0 & 1 & t_z \\ 0 & 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} x \\ y \\ z \\ 1 \end{bmatrix}$$

In both forms, the bottom row $(0, 0, 1)$ (2D) or $(0, 0, 0, 1)$ (3D) preserves the homogeneous $w$ coordinate so the result is a valid affine point.

Related Conceptual Questions

Q3.1. Why does the recurrence $+2x + 3$ appear for the East case? Where does the $+3$ come from?

A3.1. The new mid-point is $(x_i+2, y_i - \tfrac{1}{2})$. Subtracting the old mid-point $(x_i+1, y_i - \tfrac{1}{2})$ from it in the implicit function gives $(x_i+2)^2 - (x_i+1)^2 = 2x_i + 3$. The $y$-contribution cancels because $y$ does not change on an East step.

Q3.2. If translation is additive, why do we still convert it to a matrix?

A3.2. Without homogeneous form, you cannot fold translation into the same matrix that holds rotation and scaling, because matrix addition ≠ matrix multiplication. Homogeneous form turns translation into multiplication, so a long sequence (S, then R, then T) collapses into a single matrix product $T \cdot R \cdot S$ that the GPU applies in one pass.

Q3.3. Could we drop the $w = 1$ bottom row of the homogeneous matrix and still get correct results?

A3.3. No — the bottom row is what preserves the $w$ coordinate, ensuring the output is an affine point $(x', y', z', 1)$ rather than a homogeneous tuple. If the bottom row had other entries, the output would have $w \ne 1$ and you'd need a perspective divide, which is the essence of perspective projection rather than affine translation.

Question 4 — 2D Rotation, 3D Rotation, Projection Types, Vanishing Points

(a) What is rotation? Find the transformed point, $P'$, caused by rotating $P = (4, 2)$ about the origin through an angle of $90°$. [1+2]

(b) Briefly explain 3-D rotation using appropriate equations, matrices and figures. [4]

(c) Explain about two types of projection with appropriate equations and figures. [4]

(d) What is vanishing point? Discuss about different types of vanishing points. [3]

Concept Needed

Rotation is the rigid transformation that moves a point around a pivot by an angle, preserving distance from the pivot. In 3D we rotate independently about each coordinate axis. Projection maps a 3D scene onto a 2D image plane — either with parallel rays (no foreshortening) or with rays converging at a finite center of projection (foreshortening and vanishing points).

(a) 2D Rotation about the Origin

Definition. Rotation is the transformation that moves a point along a circular arc around a fixed pivot by a specified angle $\theta$, preserving the distance from the pivot.

Rotation matrix (counter-clockwise about the origin):

$R(\theta) = \begin{bmatrix} \cos\theta & -\sin\theta \\ \sin\theta & \cos\theta \end{bmatrix}$

For $P = (4, 2)$ and $\theta = 90°$:

$\cos 90° = 0$, $\sin 90° = 1$.

$P' = \begin{bmatrix} 0 & -1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} 4 \\ 2 \end{bmatrix} = \begin{bmatrix} -2 \\ 4 \end{bmatrix}$

So $P' = (-2, 4)$.

(b) 3D Rotation

3D rotation can occur about any of the three coordinate axes by angle $\theta$.

About the X-axis (rotation in the YZ-plane; $x$ unchanged):

$R_x(\theta) = \begin{bmatrix} 1 & 0 & 0 \\ 0 & \cos\theta & -\sin\theta \\ 0 & \sin\theta & \cos\theta \end{bmatrix}$

About the Y-axis (rotation in the XZ-plane; $y$ unchanged):

$R_y(\theta) = \begin{bmatrix} \cos\theta & 0 & \sin\theta \\ 0 & 1 & 0 \\ -\sin\theta & 0 & \cos\theta \end{bmatrix}$

About the Z-axis (rotation in the XY-plane; $z$ unchanged — same as 2D rotation embedded):

$R_z(\theta) = \begin{bmatrix} \cos\theta & -\sin\theta & 0 \\ \sin\theta & \cos\theta & 0 \\ 0 & 0 & 1 \end{bmatrix}$

Arbitrary 3D rotation is a composition of these: $R = R_z \cdot R_y \cdot R_x$ (or whichever order the textbook specifies, depending on whether the rotations are about world or moving axes).

(c) Two Types of Projection

1. Parallel Projection. Projection rays are parallel. Object size in projection is independent of distance from the projection plane.

• Orthographic (orthogonal): rays perpendicular to the projection plane. Front, top, side views.
• Oblique: rays at an angle to the projection plane.
  • Cavalier: angle $= 45°$, foreshortening factor $= 1$ (true lengths preserved).
  • Cabinet: angle $\approx \arctan(0.5) \approx 26.57°$, foreshortening factor $= 0.5$.

$x_p = x + z \cdot \frac{\cos\alpha}{L}$ $y_p = y + z \cdot \frac{\sin\alpha}{L}$

where $\alpha$ is the angle of the projector with the $x$-axis and $L$ is the foreshortening factor.

In matrix form, parallel projection's last row is $(0, 0, 0, 1)$ — the homogeneous $w$ coordinate is preserved, so no perspective divide occurs.

2. Perspective Projection. Projection rays converge at a finite center of projection (vanishing point). Objects appear smaller as they move farther from the viewer, producing realistic depth cues.

With the projection plane at $z = d$ and the center of projection at the origin:

$x_p = \frac{x \cdot d}{z}, \qquad y_p = \frac{y \cdot d}{z}$

In matrix form, the last row is nonzero — e.g. $(0, 0, -\tfrac{1}{d}, 1)$ — which grows $w$ during projection; the final divide shrinks distant points, producing foreshortening.

(d) Vanishing Points

Definition. A vanishing point is a point on the 2-D projection where lines that are parallel in 3-D space appear to converge. It is the projection of a point at infinity along a set of parallel lines, onto the image plane.

Types of vanishing points:

1. One-point perspective. One principal axis is perpendicular to the picture plane (the other two are parallel). All parallel depth lines converge to a single point. Example: looking down a straight hallway.

2. Two-point perspective. Two principal axes are at angles to the picture plane (none perpendicular). Two distinct vanishing points appear on the horizon line. Example: a corner view of a building.

3. Three-point perspective. All three principal axes make angles with the picture plane. A third vanishing point appears above or below the horizon. Example: looking up at a tall skyscraper from ground level.

Significance. Vanishing points create depth perception, enhance realism, and convey scale and distance in 2-D representations of 3-D scenes.

Related Conceptual Questions

Q4.1. Where does $P = (4, 2)$ land after a $-90°$ rotation about the origin?

A4.1. $(-2, 4)$ rotated by $-90°$ becomes $(2, 4)$. Equivalently, $(4, 2)$ rotated by $-90°$ lands at $(2, 4)$ — the mirror image across the $y$-axis of the $+90°$ answer.

Q4.2. Why does $R_y$ look "sign-flipped" compared to $R_x$ and $R_z$?

A4.2. In a right-handed coordinate system, the positive rotation about $y$ follows the left-hand rule relative to the $+y$ axis, so the $\sin\theta$ entry appears with opposite sign in the matrix. If you see sign errors, check the textbook's handedness convention.

Q4.3. Why do parallel 3D lines converge only in perspective projection, not in parallel projection?

A4.3. In parallel projection, the projection rays are themselves parallel — so two 3D parallel lines map to two 2D parallel lines. In perspective projection, all rays pass through a single finite center of projection, so two 3D parallel lines (not parallel to the image plane) trace two rays that meet at a single point in the image — the vanishing point.

Question 5 — RGB & CMY Color Models, Z-Buffer with Four Polygons on a 6×6 Image

(a) What is color model? Describe RGB color model with advantages and disadvantages. [1+5]

(b) How to convert RGB color model to CMY color model? What are the uses of CMY color model? [1+2]

(c) Consider a Z-buffer with a range of $0$ to $10$ and $6 \times 6$ pixel image and four polygons as follows: [5]

• Polygon 1: Depth $= 4$; vertex1 $= (1, 1)$; vertex2 $= (1, 3)$; vertex3 $= (3, 3)$; vertex4 $= (3, 1)$.
• Polygon 2: Depth $= 2$; vertex1 $= (3, 0)$; vertex2 $= (3, 2)$; vertex3 $= (5, 2)$; vertex4 $= (5, 0)$.
• Polygon 3: Depth $= 8$; vertex1 $= (2, 2)$; vertex2 $= (2, 5)$; vertex3 $= (4, 5)$; vertex4 $= (4, 2)$.
• Polygon 4: Depth $= 4$; vertex1 $= (2, 0)$; vertex2 $= (2, 3)$; vertex3 $= (5, 3)$; vertex4 $= (5, 0)$.

Now place the polygons using the Z-buffer method.

Concept Needed

A color model is a mathematical system for representing colors as tuples of numbers in a reproducible range. RGB is the additive model that maps directly to display hardware; CMY is the subtractive model used in printing. The Z-buffer (depth buffer) is the standard image-space hidden-surface algorithm: at each pixel, store the smallest depth seen so far, and write the corresponding polygon's color.

(a) RGB Color Model

Definition. A color model is a mathematical framework for representing colors as tuples of numbers (typically three or four components), with rules for combining those components into the visible spectrum.

RGB (Red, Green, Blue) is an additive color model: colors are produced by adding varying intensities of red, green, and blue light. Each component ranges from 0 to 255 in 8-bit storage.

• $(0, 0, 0)$ → Black (no light)
• $(255, 255, 255)$ → White (full intensity of all)
• $(255, 0, 0)$ → Red
• $(0, 255, 0)$ → Green
• $(0, 0, 255)$ → Blue
• $(255, 255, 0)$ → Yellow (R + G)

Advantages of RGB:

1. Directly corresponds to how monitors, TVs, and other emissive displays produce color (each pixel has RGB sub-pixels).
2. Wide gamut for emission-based displays.
3. Easy hardware implementation — every modern display is built around three RGB sub-pixels.
4. Intuitive for light-based color mixing.
5. Efficient for digital cameras and scanners (sensors are RGB).
6. Simple to manipulate in image editing software.

Disadvantages of RGB:

1. Not perceptually uniform — equal numerical changes don't produce equal perceptual changes.
2. Inefficient for printing (CMYK is needed).
3. Channels are correlated — changing one channel affects the others.
4. Difficult to specify a desired color directly without color-picker UI.

(b) RGB → CMY Conversion & Uses of CMY

Conversion. CMY is the subtractive model: each component is computed by subtracting the RGB intensity from full white:

$C = 1 - R$ $M = 1 - G$ $Y = 1 - B$

assuming normalized RGB values in $[0, 1]$. For 8-bit RGB (0–255):

$C = 255 - R, \qquad M = 255 - G, \qquad Y = 255 - B$

Uses of CMY:

1. Color printing — primary model for inkjet and laser printers; CMYK extends with a dedicated black ink for deeper blacks.
2. Photographic reproduction — used in film photography and print media.
3. Packaging design — magazines, brochures, posters.
4. Subtractive color mixing — when pigments are physically mixed, colors are subtracted from reflected white light, so CMY applies.

(c) Z-Buffer Method

Algorithm:

1. Set the frame buffer to the background color.
2. Initialize the Z-buffer with the maximum depth value ($10$).
3. For each polygon, for each pixel $(x, y)$ in the polygon's $x$-$y$ projection:
   • Compute the polygon's $z$ at $(x, y)$.
   • If $z < \text{Z-buffer}[x, y]$, set $\text{Z-buffer}[x, y] = z$ and write the polygon's color to the frame buffer.

Polygons on the $6 \times 6$ image (with depth range $[0, 10]$, smaller $z$ = closer to viewer):

Each polygon has a uniform scalar depth (constant across its pixels). The Z-buffer keeps the minimum $z$ at each pixel — the closest visible surface.

Final Z-buffer (each cell shows the minimum depth of all polygons covering it):

Note: at $(2, 2)$ both P1 and P4 have depth 4 and P3 has depth 8 — minimum is 4. At $(2, 3)$ and $(3, 3)$ P1 and P4 share depth 4 (P3 also covers at depth 8). At $(4, 3)$ P3 covers with depth 8 and P4 covers with depth 4 — minimum is 4.

Visibility result:

• P2 (depth 2) is the closest polygon; it dominates wherever its pixels overlap any other.
• P1 and P4 (depth 4) are visible only where P2 doesn't overlap.
• P3 (depth 8) is the farthest; it is fully covered wherever P1, P2, or P4 also cover. P3 is only visible in the strip rows 4–5, cols 2–4 where no other polygon reaches.

Related Conceptual Questions

Q5.1. Why is the Z-buffer called an "image-space" algorithm?

A5.1. It operates per-pixel in the final 2D image, not per-polygon in 3D object space. The Z-buffer is a 2D array indexed by screen coordinates, with one depth per pixel — the resolution of the algorithm is the display resolution, not the polygon count.

Q5.2. What is Z-fighting, and when does it occur?

A5.2. Z-fighting happens when two surfaces have nearly identical depths at the same pixel (e.g. coplanar polygons). Tiny rounding errors in the depth comparison cause one polygon or the other to win unpredictably, producing a flickering checkerboard pattern. Mitigations: nudge one polygon by a small $\epsilon$, increase depth-buffer precision, or use depth bias.

Q5.3. Does RGB-to-CMY lose information?

A5.3. The mathematical conversion is lossless as long as both are stored at the same precision. In practice, print workflows quantize to ink coverage and add a separate K (black) channel in CMYK, so some saturation detail is approximated — but the underlying math is bijective.

Question 6 — Viewport, Cohen-Sutherland Clipping, Sutherland-Hodgman Polygon Clipping, Scan-Fill

(a) Define viewport. Describe the basic idea of Cohen-Sutherland clipping algorithm. [1+3]

(b) Determine the clipped region for the following polygon ABCDE using Sutherland Hodgman polygon clipping algorithm. The rectangle signifies the viewport. [6]

(c) Write the basic scan-fill algorithm for polygon filling. What is interior pixel convention? [2+2]

Concept Needed

A viewport is the on-screen rectangle where the world-coordinate window is displayed. Clipping cuts away the parts of a scene outside the viewport. Cohen-Sutherland clips individual line segments using 4-bit outcodes; Sutherland-Hodgman clips polygons against a convex window by walking each vertex through each clipping edge. Scan-fill rasterizes a polygon by computing scanline intersections and filling between paired crossings; the interior pixel convention decides how to treat boundary pixels.

(a) Viewport & Cohen-Sutherland Clipping

Viewport. A rectangular region on a display device (in screen coordinates) where the contents of a window in world coordinates are mapped and displayed. It defines the visible area for output.

Cohen-Sutherland line clipping. Each line endpoint is tagged with a 4-bit outcode indicating which of nine $3 \times 3$ regions it lies in, relative to the clipping rectangle:

The 9 regions and their codes:

Algorithm:

1. Compute outcodes for both endpoints of the line segment.
2. Trivial accept: both outcodes are $0000$ — both endpoints inside, draw the line.
3. Trivial reject: bitwise AND of the two outcodes is non-zero — both endpoints share a side outside the rectangle, discard the line.
4. Otherwise: the line crosses a boundary. Pick an endpoint that is outside, clip it against the boundary it crosses (top, bottom, left, or right) using the parametric line $x = x_1 + t(x_2 - x_1)$, $y = y_1 + t(y_2 - y_1)$, replace it with the intersection point, recompute its outcode, and repeat until trivial accept or reject.

The algorithm finds intersections iteratively, clipping against one boundary at a time, and is very efficient for scenes where most segments are either trivially accepted or trivially rejected.

(b) Sutherland-Hodgman Polygon Clipping of ABCDE

The Sutherland-Hodgman algorithm clips a polygon against a convex clipping window by sequentially clipping against each boundary (left, right, top, bottom). For each input edge $S \to E$:

Reading the figure (from the source .tex): the viewport is the rectangle with corners roughly $(-1.5, 0.5)$ and $(5.5, 3.5)$. The polygon ABCDE has approximate vertices (from the figure):

• $A = (-0.4, 1.9)$
• $B = (1.0, 0.4)$
• $C = (3.8, 0.3)$
• $D = (0.9, -1.6)$
• $E = (-2.4, -0.2)$

The viewport is the inner rectangle. Walking the algorithm against each boundary:

1. Left edge ($x = -1.5$): no vertex is left of the viewport — all are inside this axis. Output unchanged.
2. Right edge ($x = 5.5$): no vertex is right of the viewport — all are inside. Output unchanged.
3. Bottom edge ($y = 0.5$): $D$ is below ($-1.6$); $A$ is above ($1.9$); $B, C, E$ are around the boundary ($0.4, 0.3, -0.2$). Walking the polygon edge by edge and emitting intersections with $y = 0.5$ where each edge crosses the line produces a clipped bottom contour.
4. Top edge ($y = 3.5$): all vertices are below the top — no edge crosses. Output unchanged.

The final clipped polygon consists of the parts of the polygon inside the viewport, joined by intersection points where the polygon's edges crossed the bottom boundary.

Note: Because the source figure uses TikZ coordinates rather than integer pixel coordinates, exact pixel values of the intersection points depend on the precise vertex positions; the procedure above is the conceptual answer. The key point is that Sutherland-Hodgman clips against each boundary in turn, and the output list of one pass becomes the input of the next.

(c) Basic Scan-Fill Algorithm & Interior Pixel Convention

Basic scan-fill algorithm:

text

Copy

Details and edge cases:

• Intersection counting. For a non-self-intersecting polygon, the scanline crosses an even number of edges; pairs are $(1, 2), (3, 4), \dots$.
• Vertex handling. A scanline passing through a vertex touches two edges at the same point; use the upper-endpoint rule — count the intersection if the vertex is the lower endpoint of an edge, but not if it is the upper endpoint (or use your textbook's specific convention consistently).
• Horizontal edges. Skip horizontal edges; they would otherwise produce duplicates at every pixel along the edge.
• Active-edge list (AEL). Real implementations maintain a sorted list of edges crossing the current scanline and update incrementally each scanline, avoiding a full recompute — this is how graphics libraries implement scan-fill efficiently.

Interior pixel convention. When a polygon boundary passes between two pixels, an interior pixel convention decides which pixels are considered part of the polygon and which are not.

Common conventions:

• Even-odd (parity) rule — count edge crossings along the scanline; a pixel is inside if the count is odd. Default for polygons with holes.
• Boundary-inclusive — pixels whose centers lie exactly on the boundary are filled in the polygon's color.
• Boundary-exclusive — boundary pixels are drawn separately (e.g. in black) and only strictly interior pixels get the polygon's color.

The choice affects how thick the polygon border looks and whether adjacent polygons share boundary pixels cleanly.

Related Conceptual Questions

Q6.1. Why use 4-bit outcodes instead of a single flag per endpoint in Cohen-Sutherland?

A6.1. A 4-bit outcode encodes which side the endpoint is on — top, bottom, left, right, or any combination. The trivial-reject test (bitwise AND of two outcodes) detects "both endpoints on the same outside side" in one operation; the trivial-accept test (both outcodes are $0$) handles "both endpoints inside" in another. A single flag would lose this directional information.

Q6.2. Can Sutherland-Hodgman clip against a circular viewport?

A6.2. No, not directly. Sutherland-Hodgman only works for convex clipping windows with straight edges. Although a circle is convex, the algorithm's per-edge intersection math assumes straight edges on the clipping window. For circular windows you'd need a different algorithm (Weiler-Atherton with circular boundary, or specialized ellipse/polygon clipping).

Q6.3. Why use floating-point arithmetic for scanline intersections when Bresenham uses integers for lines?

A6.3. Polygon edges can have arbitrary slopes, and the intersection with a horizontal scanline generally falls between integer $x$ positions. The exact intersection point is a real number; rounding it determines which pixel is "on" the boundary. Bresenham avoids floats because it uses a decision variable instead of computing intersection $x$'s explicitly.

Question 7 — Bezier vs B-Spline, Z-Buffer with Two Polygons, Illumination vs Shading, Halftone

(a) Enumerate the major differences between Bezier curve and the B-spline curve. [3]

(b) Explain the Z-buffer algorithm for hidden surface removal. Suppose we have two polygons A and B with Z values $0.7$ and $0.5$. Assume $5 \times 5$ pixel image and value of Z is from $0$ to $1$. Find which polygon will be hidden and why? [5]

(c) Compare between Illumination and shading model. [3]

(d) What is Halftone approximation? [3]

Concept Needed

Curves are parametric representations: Bezier is simple but global in control; B-spline offers local control and independent degree choice. The Z-buffer is the standard image-space hidden-surface algorithm: store the smallest depth per pixel and write that polygon's color. Illumination models compute light intensity at a point; shading models distribute that color across a polygon surface. Halftoning simulates continuous tone on devices with few intensity levels (e.g. 1-bit printers).

(a) Bezier vs B-Spline Curve

Rule of thumb: Use Bezier for simple, fixed shapes (UI icons, glyphs, one-off paths). Use B-spline (or NURBS) when you need fine control over complex, evolving shapes (animation paths, CAD models).

(b) Z-Buffer Algorithm + Two-Polygon Example

Algorithm.

Data structures:

• Frame buffer — stores color/intensity for each pixel (initialized to background).
• Z-buffer — stores the depth of the closest surface seen at each pixel (initialized to maximum depth).

Steps:

1. Set the frame buffer to the background color.
2. Initialize the Z-buffer to the maximum depth (here $1$).
3. For each polygon:
   • For each pixel $(x, y)$ in the polygon's projection:
     • Compute the polygon's $z$ at $(x, y)$.
     • If $z < \text{Z-buffer}[x, y]$, then this polygon is closer at this pixel: set $\text{Z-buffer}[x, y] = z$ and write the polygon's color to the frame buffer.

Advantages: simple; works for any number of polygons; hardware supported (GPU z-buffer); handles overlapping objects naturally. Disadvantages: memory-intensive (one depth per pixel); precision issues (z-fighting); no object coherence; resolution-dependent.

Worked example. $5 \times 5$ image, Z range $[0, 1]$. Polygons A (Z = 0.7) and B (Z = 0.5).

With the convention "smaller $z$ = closer to viewer":

• Polygon B ($z = 0.5$) is closer to the viewer.
• Polygon A ($z = 0.7$) is farther.

At every pixel where both polygons project, the algorithm compares their depths:

• $\text{Z-buffer}[x, y] = 1$ (initial)
• After scanning polygon A: $\text{Z-buffer}[x, y] = 0.7$ at pixels where A projects.
• After scanning polygon B: at pixels where B projects, $0.5 < 0.7$, so $\text{Z-buffer}[x, y] = 0.5$ and B's color is written. At pixels where B does not project but A does, $\text{Z-buffer}[x, y]$ remains $0.7$ and A's color is shown.

Conclusion: Polygon A is hidden wherever polygon B projects to the same pixel. Polygon B is visible at all its own pixels. Polygon A is visible only where B does not project. B is in front; A is hidden behind B in their overlap.

(c) Illumination vs Shading Model

Key distinction: the illumination model computes the color at a point; the shading model distributes that color across the entire polygon using techniques like constant shading (flat), linear interpolation (Gouraud), or interpolated normals (Phong).

(d) Halftone Approximation

Definition. Halftone approximation is a technique used to simulate continuous-tone images on devices with limited color or gray-level capability (e.g. 1-bit black-and-white printers, early displays) by varying the density of black (or color) dots in a pattern.

Working principle:

• The image is divided into small cells (typically $2 \times 2$, $4 \times 4$, $8 \times 8$).
• Each cell contains a fixed number of dots.
• The number of "on" dots in each cell approximates the local intensity.
• Bright regions → fewer dots; dark regions → more dots.

Types:

• Ordered dithering — uses a fixed threshold matrix (e.g. Bayer matrix).
• Error diffusion — distributes quantization error to neighboring pixels (e.g. Floyd-Steinberg).

Example — $4 \times 4$ Bayer matrix (for 17 intensity levels):

$$M = \begin{bmatrix} 0 & 8 & 2 & 10 \\ 12 & 4 & 14 & 6 \\ 3 & 11 & 1 & 9 \\ 15 & 7 & 13 & 5 \end{bmatrix}$$

For each pixel, compare its intensity $I$ (0–16) to $M[i, j]$: if $I > M[i, j]$ the output dot is "on".

Applications:

1. Newspaper printing.
2. Low-color printers (1-bit black/white).
3. Comic books.
4. Image compression pre-processing.
5. Display systems with limited color depth.

Advantages: reduces memory requirements; provides visual continuity; works with binary displays. Disadvantages: loss of fine detail; moiré patterns possible; visible dot structure.

Related Conceptual Questions

Q7.1. Why does B-spline use local control while Bezier does not?

A7.1. B-spline uses piecewise basis functions — each basis function has compact support, so moving one control point changes the curve only inside that support region. Bezier's Bernstein basis is global: every basis function has support over the whole interval $[0, 1]$, so any control-point move affects the whole curve.

Q7.2. Why does the Z-buffer work even when polygons overlap in complex ways?

A7.2. The Z-buffer operates per-pixel, independent of polygon order. For each pixel, only the polygon with the smallest depth at that pixel survives. This makes the algorithm immune to polygon overlap complexity — no sorting or ordering is required.

Q7.3. Why is flat shading faster than Gouraud shading?

A7.3. Flat shading computes the illumination model once per polygon and assigns the resulting color to every pixel in the polygon. Gouraud shading interpolates three vertex colors across the polygon, requiring extra work per pixel. Phong shading is slowest because it interpolates normals and recomputes the illumination model per pixel.

Question 8 — Linear vs Non-Linear Multimedia, Entropy, Lossless vs Lossy Compression, Huffman Coding

(a) Find the differences between linear and non-linear multimedia. [3]

(b) What is Entropy in compression? Calculate the entropy for the followings Alphabet $\{X, Y\}$, $P(X) = 0.3$ and $P(Y) = 0.5$. [3]

(c) Write the differences between lossless and lossy compression techniques. [3]

(d) Let's assume we have a file to send containing the following values: AABABBBBEBECCCCCDDD. Generate the Huffman code to compress the file. [5]

Concept Needed

Linear multimedia plays sequentially with no user control (TV, cinema). Non-linear multimedia lets the user navigate freely (web pages, games, DVDs). Entropy is the theoretical lower bound on average bits per symbol — the Shannon limit. Lossless compression preserves every bit; lossy compression discards imperceptible detail. Huffman coding assigns shorter codes to more frequent symbols, producing an optimal prefix-free code for a known distribution.

(a) Linear vs Non-Linear Multimedia

Linear: the user is a passive consumer. Time progresses without their control. Non-linear: the user decides what, when, and how to access content. Requires linking, search, and indexing.

(b) Entropy in Compression

Definition. Entropy $H(X)$ is the average amount of information per symbol in a message. It represents the theoretical minimum number of bits needed to encode each symbol — the lower bound for lossless compression:

$H(X) = -\sum_{i=1}^{n} p_i \log_2 p_i \quad \text{(bits/symbol)}$

Calculation. Given alphabet $\{X, Y\}$ with $P(X) = 0.3$ and $P(Y) = 0.5$:

Note: strictly, probabilities must sum to $1$. We interpret the two values as the full distribution given in the question (and note the inconsistency).

Using the given probabilities as-is:

$H = -\left[0.3 \log_2 0.3 + 0.5 \log_2 0.5\right]$ $= -\left[0.3 \times (-1.737) + 0.5 \times (-1.0)\right]$ $= -\left[-0.521 - 0.500\right]$ $= 1.021 \text{ bits/symbol}$

If we treat $P(Y) = 0.7$ (the complement of $P(X) = 0.3$ for a proper two-symbol alphabet):

$H = -\left[0.3 \log_2 0.3 + 0.7 \log_2 0.7\right] = 0.881 \text{ bits/symbol}$

Either result is the entropy of the given source. The exact number depends on whether the question's $P(Y) = 0.5$ is a typo for $0.7$ or an intentional incomplete distribution.

(c) Lossless vs Lossy Compression

Examples.

• Lossless: ZIP archives, PNG images, source code, database backups, FLAC audio.
• Lossy: JPEG photos, MP3 audio, streaming video, voice calls.

(d) Huffman Coding for AABABBBBEBECCCCCDDD

Step 1: Count frequencies. Reading the string AABABBBBEBECCCCCDDD:

• A: positions 1, 2, 4 → 3
• B: positions 3, 5, 6, 7, 8, 10 → 6
• C: positions 13, 14, 15, 16, 17 → 5
• D: positions 18, 19, 20 → 3
• E: positions 9, 11 → 2

Total = 3 + 6 + 5 + 3 + 2 = 19 characters.

Step 2: Sort symbols by frequency (ascending).

Step 3: Build the Huffman tree.

• Iteration 1: Combine E (2) + A (3) → EA: 5.
• Iteration 2: Combine D (3) + EA (5) → DEA: 8.
• Iteration 3: Combine C (5) + B (6) → CB: 11.
• Iteration 4: Combine DEA (8) + CB (11) → Root: 19.

Step 4: Assign codes (0 to left child, 1 to right child at each internal node):

text

Copy

Step 5: Read off codes.

Verify the prefix property: no code is a prefix of another ($00$, $10$, $11$, $010$, $011$ — every leaf differs at the first differing bit). ✓

Step 6: Encode the string. AABABBBBEBECCCCCDDD:

text

Copy

Concatenated: 01101111011111111101011010101010000000 (43 bits).

Step 7: Compression statistics.

Total encoded bits:

$= 3 \times 3 + 6 \times 2 + 5 \times 2 + 3 \times 2 + 2 \times 3 = 9 + 12 + 10 + 6 + 6 = 43 \text{ bits}$

For comparison, fixed-length coding with $\lceil \log_2 5 \rceil = 3$ bits per symbol gives $19 \times 3 = 57$ bits.

Compression ratio = $57 / 43 \approx 1.33 : 1$. Space saved = $(57 - 43) / 57 \approx 24.6\%$.

Related Conceptual Questions

Q8.1. Why does entropy set a hard lower bound on lossless compression?

A8.1. Shannon's source coding theorem shows that any lossless code must use at least $H(X)$ bits per symbol on average — otherwise, by the pigeonhole principle, two distinct messages would map to the same codeword and decoding would be ambiguous. So $H(X)$ is the theoretical limit, and Huffman coding comes within 1 bit of it for symbol-by-symbol codes.

Q8.2. Why is the prefix property essential in Huffman codes?

A8.2. Without the prefix property, two different bit strings could be parsed in multiple ways during decoding, and the decoder could not tell which one the encoder meant. With the prefix property, reading bits from left to right, you can identify each symbol the moment you reach a leaf of the code tree — no separator between symbols is needed.

Q8.3. Can Huffman coding beat the entropy bound?

A8.3. No. Shannon's source coding theorem shows the average code length is at least $H(X)$ for any uniquely decodable code. Huffman achieves the optimal symbol-by-symbol code (within 1 bit of $H(X)$ for integer bit-lengths). To beat the bound you need block coding — encoding multiple symbols at a time — which then approaches $H(X)$ asymptotically.

Q8.4. Is the Huffman code in (d) unique?

A8.4. Not strictly — different valid Huffman trees can be built by making different choices during the bottom-up merges (e.g. swapping the order of equal-frequency siblings). All such trees produce optimal (equal minimum total bits) codes, but the bit patterns assigned to each symbol differ. The code lengths in the table above are unique: the two rarest symbols (E, A) get 3-bit codes and the three more common ones (D, C, B) get 2-bit codes.

Interview Corner