Programming Languages & Computer Graphics

Why this unit matters

Unit 3 is the widest unit in the NET CS syllabus, it spans language theory, two full programming languages (C and C++), web technologies, and an entire subfield of graphics mathematics. NET questions from this unit test both definitional knowledge (what is a virtual function?) and numerical ability (apply a 2D rotation matrix). Candidates with a programming background have a head start on C/C++ questions, but the graphics and language theory portions require dedicated preparation. Together, this unit typically contributes 10-15 questions per paper.

Syllabus map

Every named topic in the official UGC NET CS Code 87 syllabus for Unit 3:

• Language Design: programming paradigms (imperative, functional, logic, OOP), programming environments, virtual computers and binding times, syntax (BNF, EBNF), stages of translation (lexical analysis, parsing, semantic analysis, code generation, optimisation), formal transition models (finite automata, regular expressions, context-free grammars), Elementary Data Types: properties of types (name, structure, size, operations), scalar types (integer, float, char, bool, pointer, enum), composite types (array, record/struct, union, string, set), Programming in C: tokens (keywords, identifiers, constants, operators, special symbols), data types, sequence control, subprogram control (functions, recursion), arrays (single and multidimensional), structures, unions, strings (standard library functions), pointers (pointer arithmetic, pointers to arrays and functions), file handling (fopen, fclose, fread, fwrite, fprintf, fscanf), command-line arguments (argc, argv), preprocessor directives (#include, #define, conditional compilation), OOP Concepts: class, object, instantiation, inheritance (single, multiple, multilevel), encapsulation, data hiding, abstract class, pure virtual functions, polymorphism (compile-time / runtime), Programming in C++: tokens and variables, operators (including scope resolution ::, new/delete), control statements, functions (inline, default arguments, function overloading), virtual functions, classes and objects, constructors (default, parameterised, copy), destructors, operator overloading, inheritance in C++, templates (function templates, class templates), exception handling (try-catch-throw), streams and file handling (cin, cout, fstream), Web Programming: HTML (structure, tags, forms, tables), DHTML (DOM, CSS, JavaScript for dynamic content), XML (structure, DTD, schema, XPath, XSLT), scripting languages (JavaScript, VBScript), Java basics, Java servlets (lifecycle, HTTP methods), Java applets (lifecycle, security sandbox), Computer Graphics: display devices, raster scan vs random scan displays, points and lines on raster displays, DDA line drawing algorithm, Bresenham's line algorithm, midpoint circle algorithm, midpoint ellipse algorithm, polygon fill algorithms (scan-line, boundary fill, flood fill), 2D Geometric Transformations and Viewing: translation, scaling, rotation, reflection, shear, matrix representation, homogeneous coordinates, composite transformations, 2D viewing pipeline, window-to-viewport mapping (normalization), clipping algorithms (Cohen-Sutherland for lines, Sutherland-Hodgman for polygons), 3D Representation and Transformations: polygon and quadric surfaces, spline representation, Bezier curves and surfaces, B-spline curves and surfaces, 3D transformations (translation, scaling, rotation), 3D viewing, parallel and perspective projection, hidden surface removal (painter's algorithm, Z-buffer)

Language Design

Programming Paradigms

A programming paradigm is a style or way of thinking about programs.

• Imperative: programs are sequences of statements that change program state. C, Pascal., Object-oriented: programs are collections of interacting objects. Java, C++, Python., Functional: computation is the evaluation of mathematical functions; avoids mutable state. Haskell, Lisp., Logic: computation is deduction from facts and rules. Prolog.

Binding Times

Binding is the association of a name with a value, type, or location. It can happen at:

• Language definition time (semantic rules), Compile time (type binding for statically typed languages), Link time (binding function calls to addresses), Load time (allocation of global variables), Runtime (binding of variables in dynamically typed languages, dynamic dispatch in OOP)

Early binding (compile time) is faster. Late binding (runtime) is more flexible.

Stages of Translation

A compiler translates source code to machine code in these stages:

1. Lexical analysis (scanning): source text -> tokens. Handled by a finite automaton.
2. Syntax analysis (parsing): tokens -> parse tree / AST. Uses context-free grammar (CFG). LL, LR parsers.
3. Semantic analysis: type checking, scope resolution, symbol table management.
4. Intermediate code generation: produce three-address code or IR.
5. Code optimisation: eliminate redundancies, constant folding, loop optimisation.
6. Code generation: produce target machine code.

Elementary Data Types

Scalar types hold a single value: int, float, char, bool, enum, pointer. Composite types aggregate multiple values: array (homogeneous, fixed-size, random access by index), struct/record (heterogeneous, named fields), union (overlapping storage, only one field valid at a time), string (sequence of characters).

Type coercion: implicit conversion between types by the compiler (e.g., int to float). Type casting: explicit conversion by the programmer.

Programming in C

Pointers

A pointer holds the memory address of another variable.

int x = 10;
int *p = &x;   // p points to x
*p = 20;       // dereference: changes x to 20
p++;           // pointer arithmetic: moves to next int (4 bytes ahead)

Pointer to a function:

int add(int a, int b) { return a + b; }
int (*fp)(int, int) = add;
int result = fp(3, 4);   // result = 7

Structures and Unions

struct Point {
    int x;
    int y;
};

union Data {
    int i;
    float f;
    char c;
};
// sizeof(union Data) = max of all member sizes
// Only one member is valid at a time

File Handling

FILE *fp = fopen("data.txt", "r");
if (fp == NULL) { /* error */ }
int n;
fscanf(fp, "%d", &n);
fprintf(fp, "Value: %d\n", n);
fclose(fp);

Binary file: use fread and fwrite with element size and count arguments.

Command-Line Arguments

int main(int argc, char *argv[]) {
    // argc: number of arguments (including program name)
    // argv[0]: program name, argv[1]: first argument, etc.
    for (int i = 0; i < argc; i++) {
        printf("arg %d: %s\n", i, argv[i]);
    }
    return 0;
}

Preprocessor Directives

#include <stdio.h>          // include standard header
#define PI 3.14159          // macro constant
#define SQUARE(x) ((x)*(x)) // function-like macro

#ifdef DEBUG
    printf("Debug mode\n");
#endif

Macros are expanded by the preprocessor before compilation. Parenthesise arguments carefully to avoid operator precedence bugs.

OOP Concepts

Core Pillars

Encapsulation: bundling data and methods that operate on that data into a single unit (class), and restricting access to internal state.

Inheritance: a derived class inherits attributes and methods of a base class. Types: single (one parent), multiple (two or more parents), multilevel (chain of inheritance), hierarchical (one parent, many children), hybrid.

Polymorphism: same interface, different behaviour., Compile-time (static): function overloading, operator overloading. Resolved at compile time., Runtime (dynamic): virtual functions, method overriding. Resolved at runtime via vtable.

Abstract class: a class that cannot be instantiated. Contains at least one pure virtual function. Defines an interface for derived classes.

Programming in C++

Classes, Constructors, and Destructors

class Rectangle {
private:
    int width, height;
public:
    Rectangle() : width(0), height(0) {}           // default constructor
    Rectangle(int w, int h) : width(w), height(h) {} // parameterised
    Rectangle(const Rectangle &r) : width(r.width), height(r.height) {} // copy
    ~Rectangle() { /* destructor: cleanup */ }
    int area() const { return width * height; }
};

Operator Overloading

class Complex {
public:
    double real, imag;
    Complex operator+(const Complex &other) const {
        return {real + other.real, imag + other.imag};
    }
    friend std::ostream& operator<<(std::ostream &os, const Complex &c) {
        os << c.real << "+" << c.imag << "i";
        return os;
    }
};

Virtual Functions and Runtime Polymorphism

class Shape {
public:
    virtual double area() = 0;  // pure virtual: makes Shape abstract
    virtual ~Shape() {}
};

class Circle : public Shape {
    double r;
public:
    Circle(double radius) : r(radius) {}
    double area() override { return 3.14159 * r * r; }
};

Shape *s = new Circle(5.0);
s->area();  // calls Circle::area() at runtime via vtable

Templates

template<typename T>
T maximum(T a, T b) {
    return (a > b) ? a : b;
}

template<typename T>
class Stack {
    T data[100];
    int top;
public:
    Stack() : top(-1) {}
    void push(T val) { data[++top] = val; }
    T pop() { return data[top--]; }
};

Exception Handling

try {
    int x = -1;
    if (x < 0) throw std::invalid_argument("Negative value");
    // ...
} catch (const std::invalid_argument &e) {
    std::cerr << "Error: " << e.what() << std::endl;
} catch (...) {
    std::cerr << "Unknown exception" << std::endl;
}

Web Programming

HTML provides structure. CSS provides style. JavaScript provides behaviour, the three-layer model of the web.

DHTML (Dynamic HTML): combination of HTML, CSS, JavaScript, and the DOM (Document Object Model). JavaScript can read and modify the DOM to change page content without reloading.

XML: a markup language for storing and transporting structured data. DTD and XML Schema define the valid structure. XPath is used to navigate XML documents. XSLT transforms XML into other formats (HTML, plain text).

Java Servlet lifecycle: init() called once at startup, service() called for each request (dispatches to doGet, doPost, etc.), destroy() called at shutdown.

Java Applet lifecycle (largely deprecated): init(), start(), paint(), stop(), destroy(). Runs inside a browser sandbox.

Computer Graphics

Raster vs Random Scan

Raster scan: the electron beam (or LCD update) sweeps across the screen row by row, left to right, top to bottom. Each position corresponds to a pixel. Frame buffer holds pixel values. Most modern displays.

Random scan (vector): the beam draws only the lines of the picture in any order. Resolution-independent. Used in oscilloscopes and early vector displays.

Line Drawing Algorithms

DDA (Digital Differential Analyser): compute x and y increments as dx/steps and dy/steps. Add increments iteratively. Uses floating-point arithmetic, which is slower.

Bresenham's line algorithm: uses only integer arithmetic (addition and subtraction). Decides at each step whether to increment y by tracking an error term.

// Bresenham for line from (x1,y1) to (x2,y2), slope 0 to 1
void bresenham_line(int x1, int y1, int x2, int y2) {
    int dx = x2 - x1, dy = y2 - y1;
    int d = 2*dy - dx;         // initial decision parameter
    int y = y1;
    for (int x = x1; x <= x2; x++) {
        plot(x, y);
        if (d > 0) { y++; d += 2*(dy - dx); }
        else        {      d += 2*dy;        }
    }
}

Midpoint Circle Algorithm

Uses the decision parameter to choose between two candidate pixels at each step. Exploits eight-fold symmetry, compute one octant, reflect for the rest.

Decision parameter: d = 1, r (initial). If d < 0: next point is (x+1, y), d += 2x + 3. If d >= 0: next point is (x+1, y-1), d += 2(x, y) + 5.

Polygon Fill

Scan-line fill: for each horizontal scan line, find intersections with polygon edges, sort them, and fill between pairs.

Boundary fill: start from an interior point, recursively fill neighbours that are not the boundary colour.

Flood fill: start from an interior point, fill all connected pixels with the same colour as the start until a boundary colour is reached.

2D Geometric Transformations

All 2D transforms are represented as 3x3 matrices using homogeneous coordinates (x, y, w) where the Euclidean point is (x/w, y/w). Using w=1 for standard points:

Translation by (tx, ty):

| 1  0  tx |   | x |   | x + tx |
| 0  1  ty | * | y | = | y + ty |
| 0  0   1 |   | 1 |   |   1    |

Scaling by (sx, sy) about origin:

| sx  0  0 |
|  0 sy  0 |
|  0  0  1 |

Rotation by angle theta (counterclockwise) about origin:

| cos(theta)  -sin(theta)  0 |
| sin(theta)   cos(theta)  0 |
|     0            0       1 |

Reflection about x-axis: scale y by -1. About y-axis: scale x by -1. About y = x: swap x and y.

Shear in x direction by sh_x: point (x, y) maps to (x + sh_x * y, y).

Composite transformations: multiply the matrices in sequence (right to left for column vectors). Order matters, rotation then translation is different from translation then rotation.

Window to Viewport Mapping

Window: a rectangular region in world coordinates. Viewport: a rectangular region on screen (device) coordinates.

Mapping formulas: x_vp = (x_w, x_wmin) / (x_wmax, x_wmin) * (x_vpmax, x_vpmin) + x_vpmin y_vp = (y_w, y_wmin) / (y_wmax, y_wmin) * (y_vpmax, y_vpmin) + y_vpmin

Clipping

Cohen-Sutherland line clipping: assigns each endpoint a 4-bit outcode (Left, Right, Bottom, Top). Lines are trivially accepted (both outcodes 0000) or trivially rejected (AND of outcodes nonzero). Otherwise, compute intersection with a boundary and repeat.

Sutherland-Hodgman polygon clipping: clips a polygon against each edge of a rectangular window successively. For each edge, pass all vertices through the clip test and compute intersections.

3D Representation and Transforms

Bezier curve: defined by n+1 control points P0...Pn. The curve is the weighted sum of Bernstein basis polynomials. For cubic Bezier (n=3), the curve passes through P0 and P3, with P1 and P2 as tangent guides.

B-spline: more local control than Bezier, moving one control point affects only a portion of the curve. NURBS (Non-Uniform Rational B-Splines) generalises B-splines, used in CAD.

3D rotation is more complex because it depends on the axis. Rotation about the z-axis is the same as 2D rotation. Rotation about x and y axes involve similar trigonometric matrices but permuted.

Perspective projection: objects closer to the viewer appear larger. The perspective divide divides x and y by z (or a function of z). Creates depth cues.

Parallel projection: no foreshortening. Orthographic projection: project straight along the view direction. Used in engineering drawings.

Hidden surface removal:

• Painter's algorithm: sort polygons by depth, draw farthest first. Fails for cyclic depth overlap., Z-buffer: per-pixel depth buffer. For each fragment, compare z value with the z-buffer; draw only if closer. Simple and effective; standard in hardware.

Worked Examples

Example 1: Bresenham's Line, Trace

Draw a line from (0,0) to (5,2). dx=5, dy=2. d = 22, 5 = -1. x=0,y=0,plot(0,0). d=-1<=0: d += 22=4 -> d=3. x=1,y=0,plot(1,0). d=3>0: y=1, d += 2*(2-5)=-6 -> d=-3. x=2,y=1,plot(2,1). d=-3<=0: d += 4 -> d=1. x=3,y=1,plot(3,1). d=1>0: y=2, d += -6 -> d=-5. x=4,y=2,plot(4,2). d=-5<=0: d += 4 -> d=-1. x=5,y=2,plot(5,2). Done. Pixels: (0,0),(1,0),(2,1),(3,1),(4,2),(5,2).

Example 2: 2D Rotation

Rotate point P(3, 0) by 90 degrees counterclockwise about the origin. cos(90) = 0, sin(90) = 1. x' = 30, 01 = 0. y' = 31 + 00 = 3. Result: P'(0, 3). Correct, rotating a point on the x-axis 90 degrees puts it on the y-axis.

Example 3: Composite Transform

Rotate a point about an arbitrary pivot (px, py) by angle theta. Step 1: Translate so that pivot moves to origin: T(-px, -py). Step 2: Rotate by theta: R(theta). Step 3: Translate back: T(px, py). Combined matrix: T(px, py) * R(theta) * T(-px, -py).

Example 4: C Pointer Arithmetic

int arr[] = {10, 20, 30, 40, 50};
int *p = arr;
printf("%d\n", *(p+2));   // prints 30
printf("%d\n", p[3]);     // prints 40 (equivalent to *(p+3))
p += 1;
printf("%d\n", *p);       // prints 20

Example 5: Virtual Function and VTable

class Base {
public:
    virtual void display() { printf("Base\n"); }
};
class Derived : public Base {
public:
    void display() override { printf("Derived\n"); }
};

Base *b = new Derived();
b->display();   // prints "Derived", runtime polymorphism via vtable

The vtable is a per-class table of function pointers. Each object has a hidden vptr pointing to its class's vtable. At runtime, the call goes through the vtable, this is dynamic dispatch.

Quick-Revision Summary

• Binding times: compile-time (static), runtime (dynamic). Late binding enables polymorphism., Stages of translation: lexical -> syntax -> semantic -> IR -> optimise -> code generate., Union: all members share the same memory location., Pointer arithmetic: p+n moves n * sizeof(*p) bytes., Virtual functions in C++ use vtable for runtime dispatch. Pure virtual makes class abstract., Templates: generic programming; instantiated at compile time., Bresenham's line algorithm: integer arithmetic only, efficient., Homogeneous coordinates: represent translation as matrix multiplication., Composite transform order matters: R then T is different from T then R., Cohen-Sutherland: 4-bit outcode for each line endpoint against viewport edges., Z-buffer: per-pixel depth comparison for hidden surface removal.

How to Study This Unit

1. C and C++ questions are mostly about output prediction or error identification. Practice reading small code snippets and tracing execution mentally.
2. Pointer questions are a favourite. Be clear on the difference between a pointer, what it points to, and pointer arithmetic.
3. For graphics, derive the transformation matrices yourself, do not just memorise them. Understand why homogeneous coordinates are needed for translation.
4. Practice applying the window-to-viewport formula with numerical examples.
5. Bresenham's algorithm questions on NET usually ask you to trace a few steps. Practice the decision parameter update rules.
6. OOP/C++ questions often test virtual functions, constructor/destructor order in inheritance, and multiple inheritance ambiguity. Run small programs mentally.
7. For web programming, focus on the servlet lifecycle, the role of DTD/schema in XML, and the DOM model for DHTML.