Computer Fundamentals and Organization

Digital Signal Processing in Signal Transmission and Reception

DSP means processing signals after converting them into digital form (sampling → quantization → coding) using processors and algorithms. A DSP-based transceiver is shown below.

 TRANSMITTER SIDE
 +--------+   +-------+   +---------------------------+   +-----------+   +-----------+
 | Analog |-->|  ADC  |-->|        DSP BLOCK          |-->| DAC /     |-->|  Channel  |
 | Source |   |(anti- |   | Source coding, filtering, |   | Modulator |   |  (noisy   |
 |        |   | alias)|   | equalization, error ctrl, |   |           |   |  medium)  |
 +--------+   +-------+   | encryption, modulation    |   +-----------+   +-----+-----+
                          +---------------------------+                         |
                                                                                v
 RECEIVER SIDE
 +--------+   +-------+   +---------------------------+   +-----------+         |
 | Analog |<--|  DAC  |<--|        DSP BLOCK          |<--| ADC /     |<--------+
 | Sink   |   |       |   | Demodulation, matched     |   | Down-     |
 +--------+   +-------+   | filtering, equalization,  |   | converter |
                          | error correction, AGC     |   +-----------+
                          +---------------------------+

How DSP improves transmission

1. Noise immunity: Signals are represented by discrete levels, so small noise does not change the bit value; regeneration at each stage prevents noise accumulation.
2. Error control coding: Hamming, Reed–Solomon and convolutional codes add redundancy so the receiver can detect and correct errors, lowering BER.
3. Bandwidth efficiency: Source coding/compression (PCM, ADPCM) and spectrally efficient modulation (QPSK, QAM, OFDM) send more bits per Hz.
4. Adaptive equalization and filtering: LMS/RLS digital filters cancel ISI, echo and multipath distortion; smart antennas do beamforming.
5. Flexibility and security: Algorithms are software-programmable (SDR), easy to upgrade, and support encryption/scrambling.

How DSP improves reception

1. Matched filtering maximizes SNR at the sampling instant.
2. Digital demodulation and synchronization recover the carrier and clock accurately.
3. Channel equalization removes distortion and inter-symbol interference.
4. Error detection/correction repairs corrupted bits, giving clear voice/data.
5. AGC and digital filtering reject out-of-band noise and interference, improving quality and reliability.

Conclusion: DSP makes communication more noise-resistant, bandwidth-efficient, secure and flexible, giving better signal quality at both the transmitting and receiving ends.

Knowledge Representation

Knowledge representation (KR) is the branch of Artificial Intelligence concerned with how to store knowledge about the world inside a computer so that an intelligent system can reason with it and use it to solve problems. It is the study of how an agent's beliefs, facts, rules and relationships are encoded in a form that a machine can manipulate. A good knowledge representation scheme should be:

• Representational adequacy — it must be able to represent all the knowledge needed for the domain.
• Inferential adequacy — it must allow new knowledge to be inferred from the existing knowledge.
• Inferential efficiency — inference must be done in an efficient manner.
• Acquisitional efficiency — new knowledge must be easy to acquire and add to the system.

Knowledge Representation Techniques

1. Logical representation

Knowledge is expressed in formal logic. In propositional logic, facts are represented as Boolean propositions (P, Q, P ∧ Q → R) and inference is done by truth-table or resolution. In first-order predicate logic (FOPL), objects, properties and relations are represented using predicates, variables and quantifiers, e.g. ∀x (Man(x) → Mortal(x)). Logic is declarative, unambiguous and has a sound and complete inference mechanism, but it is rigid, monotonic and computationally expensive for large domains.

2. Semantic network representation

Knowledge is represented as a directed graph in which nodes denote objects, concepts or events and labelled arcs denote the relations between them. The most common relations are "is-a" (subclass/superclass) and "has-a" (attribute/part). For example, "Sparrow is-a Bird" and "Bird has-a Wing" are drawn as nodes joined by arrows. Inheritance is natural in this scheme, so properties of a superclass are automatically available to subclasses. It is simple and easy to visualise, but it lacks formal semantics, cannot easily express negation or quantifiers, and inference may become ambiguous.

3. Frame representation

A frame is a record-like structure representing a stereotyped object or situation. It consists of a frame name and a collection of slots (attributes) with slot values and default values. Frames support inheritance through an "ako" (a-kind-of) link to a parent frame. For example, a "Car" frame may have slots: ako = Vehicle, wheels = 4, engine = yes. Frames are modular, easy to extend and close to object-oriented programming, but they are not well suited to representing procedural knowledge and can become unwieldy when exceptions to defaults are many.

4. Production rules

Knowledge is represented as a set of condition–action rules of the form: IF <condition> THEN <action>. A working memory holds the current facts and an inference engine matches rules against it, using forward chaining (data-driven) or backward chaining (goal-driven). This is the basis of expert systems such as MYCIN. Production rules are natural, modular and easy to modify, but they suffer from inefficiency when the rule base is large and cannot represent structured objects well.

5. Semantic and conceptual graphs / description logic

Conceptual graphs represent knowledge as a bipartite graph of concepts and relations and are used for natural-language understanding. Description logic is a decidable fragment of FOPL used in ontologies (e.g. OWL) for the Semantic Web. These give formal semantics with tractable reasoning but are restricted in expressive power.

6. Scripts and frames for events

A script is a structured representation of a stereotyped sequence of events, such as "visiting a restaurant" (entering, ordering, eating, paying, leaving). Scripts help in understanding stories and predicting missing events, but they are domain-specific and brittle.

7. Rule-based vs. structured vs. procedural hybrids

Modern systems often combine techniques — e.g. semantic networks with production rules, or frames with logic — to gain both expressiveness and efficient inference. Ontologies, knowledge graphs (Google Knowledge Graph) and semantic web technologies are practical large-scale applications of these ideas.

Conclusion

Knowledge representation is the core of any intelligent system, since reasoning is only as good as the knowledge stored. Each technique — logic, semantic networks, frames, production rules, conceptual graphs and scripts — has its own strengths and weaknesses. In practice, a hybrid representation is chosen according to the domain, the type of knowledge (declarative or procedural) and the required inference efficiency.

1. Direct Memory Access (DMA) — 1 mark

Direct Memory Access (DMA) is a data-transfer technique in which an I/O device transfers data directly to or from main memory without continuous CPU involvement. The CPU first programs the DMA controller with the starting memory address, the number of bytes/words to transfer, and the direction of transfer. After that, the DMA controller takes control of the system bus and moves the data. The CPU is interrupted only once, when the entire block transfer is complete.

---

2. Internal Components and Registers of a Standard DMA Controller — 3 marks

A standard DMA controller, such as the Intel 8237, contains the following main internal components:

The important registers inside a standard DMA controller are:

1. Base Address Register (BAR) — stores the initial memory address.
2. Base Word Count Register (BWCR) — stores the initial word/byte count.
3. Current Address Register (CAR) — holds the current memory address during transfer.
4. Current Word Count Register (CWCR) — holds the remaining count during transfer.
5. Command Register — enables/disables channels and sets priority, etc.
6. Mode Register — selects transfer mode, direction, auto-initialization, and increment/decrement.
7. Status Register — indicates terminal count, request pending, and error conditions.
8. Request Register — allows software to generate a DMA request.
9. Mask Register — masks or unmasks individual DMA channels.
10. Temporary Register — used during memory-to-memory transfer.

---

3. Burst Mode vs Cycle Stealing Mode — 3 marks

---

4. How DMA Improves System Efficiency Compared to Interrupt-Driven I/O — 3 marks

In interrupt-driven I/O, the CPU must execute an interrupt service routine for every byte or word transferred. This involves saving the CPU context, checking device status, moving data, updating pointers/counters, and restoring the context. Therefore, a large amount of CPU time is wasted in I/O overhead.

In DMA, the CPU initializes the DMA controller only once. After that, the DMA controller transfers the entire block directly between the I/O device and memory. The CPU is interrupted only at the end of the block transfer.

Thus, DMA improves system efficiency because:

1. Reduces CPU overhead — the CPU does not execute instructions for each byte/word.
2. Fewer interrupts — only one interrupt is generated per block instead of one per byte/word.
3. Higher data-transfer rate — data moves directly between device and memory without CPU intervention.
4. Better CPU utilization — in cycle stealing mode, the CPU can continue executing programs while DMA transfers data.
5. Suitable for high-speed devices — useful for disk drives, network cards, sound cards, and other block-transfer devices.

Hence, DMA significantly improves throughput and overall system performance compared with ordinary interrupt-driven I/O.

Systolic Arrays in High-Performance Parallel Processing

1. Contribution to High-Performance Parallel Processing

A systolic array is a regular, homogeneous network of simple processing elements (PEs) in which data is pumped rhythmically (like a heartbeat, hence "systolic") from the memory through the array. Each PE performs a simple operation, stores a partial result, and passes data to its neighbours on every clock cycle. This gives three key contributions:

• Massive parallelism with regular data flow: Hundreds to thousands of PEs operate concurrently on different data elements. For matrix multiplication of order (n), a 2-D array of (n \times n) PEs computes the product in (O(n)) time instead of (O(n^3)) on a sequential processor.
• High throughput via pipelining: Once the pipeline is filled, one result emerges per clock cycle. Data reuse is very high — each input element is used by many PEs, so memory bandwidth demand is reduced relative to the amount of computation.
• Local communication only: PEs communicate only with nearest neighbours (mesh/systolic interconnect), so there are no long global wires. This keeps clock skew, wire delay and routing complexity low, allowing very high clock frequencies and scalability.

2. Architectural Advantages

1. Regularity and modularity: Identical PEs and regular interconnect make VLSI layout easy, area-efficient and highly scalable — just add more PE rows/columns.
2. High throughput and deterministic timing: Fixed, synchronous data movement makes performance predictable and easy to analyse.
3. Excellent computation-to-I/O ratio: Data is reused inside the array, so the memory bandwidth bottleneck is relieved (crucial for compute-bound tasks like matrix multiplication, convolution, FIR filtering, FFT).
4. Low control overhead: No complex instruction fetch/decode per PE; control is distributed and simple.
5. Fault tolerance potential: Regular structure allows spare PEs and reconfiguration.
6. Energy efficiency: Short local wires and simple PEs reduce power compared to general-purpose cores doing the same work.

3. Limitations

1. Problem-specific design: A systolic array is efficient only for regular, data-parallel algorithms (matrix/vector operations, convolution). Irregular or control-intensive workloads map poorly.
2. Low flexibility / no generality: It cannot run arbitrary programs; it is a specialised accelerator, not a CPU.
3. I/O and memory bandwidth bound: If data cannot be fed fast enough, PEs idle — the array's speed is limited by host memory bandwidth.
4. Pipeline fill/drain overhead: For small problem sizes, the latency to fill and drain the pipeline dominates, reducing effective utilisation.
5. Synchronisation and clock distribution: Global synchronous clocking at very high frequency becomes difficult; skew and power become issues.
6. Programming difficulty: Mapping algorithms onto the array and handling boundary/edge PEs requires careful design.
7. Underutilisation for sparse/irregular data: Sparse matrices and irregular graphs leave many PEs idle.

4. Analysis in the Modern Context

In modern parallel processing, the systolic array has seen a strong revival — most notably in Google's TPU, where a (256 \times 256) systolic array performs matrix multiplication for deep-learning inference at very high throughput per watt. This shows the classic trade-off clearly:

• Where it wins: Regular, dense, compute-intensive workloads (DNN matrix multiplies, signal processing) — where its regularity, data reuse and energy efficiency beat general-purpose SIMD/GPU cores.
• Where it loses: General-purpose, irregular, branch-heavy computation — where CPUs/GPUs with flexible control and caching are superior.

Thus the systolic array is best understood as a domain-specific accelerator rather than a replacement for general processors. Its architectural advantages (regularity, locality, high throughput, energy efficiency) make it ideal for dense linear algebra and neural-network acceleration, while its limitations (inflexibility, I/O sensitivity, fill/drain overhead, programming complexity) restrict it to well-structured problems. Modern designs therefore combine systolic arrays as co-processors alongside general-purpose cores, using each where it is strongest.

1. Role of Programmable Logic Devices (PLDs) in Embedded Systems and Modern Digital System Design

Programmable Logic Devices (PLDs) are integrated circuits whose digital logic function can be configured (programmed) by the designer after manufacturing. Common types include SPLDs (PAL, PLA), CPLDs, and FPGAs.

Role in embedded systems:

1. Glue logic integration — PLDs replace dozens of discrete 74-series logic ICs (address decoders, bus buffers, chip-select generators) with a single chip, reducing board size, cost, and power.
2. Custom peripheral interfacing — They bridge mismatched interfaces between a microcontroller/CPU and peripherals (LCD, keypad, sensors, memory) by implementing custom timing and handshake logic.
3. Flexibility and faster time-to-market — Since the logic is defined in software (HDL), design changes require only reprogramming, not PCB redesign. This is vital for embedded products with evolving requirements.
4. Real-time and parallel processing — FPGAs execute many logic operations truly in parallel, giving deterministic, low-latency response that a sequential processor cannot guarantee. This suits motor control, motor drives, and communication protocol handling.
5. Low-volume production economy — For small production runs, PLDs avoid the high NRE cost of ASIC fabrication.
6. In-system reprogrammability — Flash/EEPROM CPLDs and SRAM/Flash FPGAs allow field upgrades and bug fixes after deployment.

Role in modern digital system design:

1. Rapid prototyping — FPGAs allow a complete SoC (processor core + memory + peripherals) to be prototyped and verified before committing to silicon.
2. Hardware/software co-design — Functions can be moved between hardware (FPGA fabric) and software (embedded CPU) to meet performance/power budgets.
3. Platform FPGAs and SoCs — Modern devices integrate hard CPU cores (e.g., ARM), DSP slices, block RAM, and high-speed transceivers, enabling single-chip systems.
4. Reconfigurable computing — The same hardware can be reconfigured at run time for different algorithms, giving hardware speed with software adaptability.
5. Bridging to ASIC — FPGA prototypes validate RTL before ASIC tape-out, reducing risk and cost.
6. Standard interface implementation — PLDs readily implement PCIe, Ethernet MAC, USB, and memory controllers.

Limitations: higher unit cost than ASICs at high volume, greater static power, and lower maximum speed than custom silicon.

---

2. Distance Vector Routing Algorithm

Principle: Each router maintains a distance vector — a table of the least cost to every destination network — and knows only its directly connected neighbours. Periodically (or on change) it sends its whole vector to its neighbours. A router updates its table using the Bellman-Ford equation:

$D_x(y) = \min_{v \in N(x)} \{\, c(x,v) + D_v(y) \,\}$

where $c(x,v)$ is the link cost to neighbour $v$ and $D_v(y)$ is neighbour $v$'s advertised cost to $y$.

Algorithm steps:

1. Initialise: cost to self = 0, cost to directly connected networks = link cost, others = ∞.
2. Exchange distance vectors with all directly connected neighbours.
3. For each destination, compute the minimum over all neighbours using the equation above; record the neighbour giving the minimum as the next hop.
4. If any entry changes, advertise the updated vector to neighbours.
5. Repeat until no entry changes (convergence).

Example. Five routers A, B, C, D, E with link costs:

Initial vectors (cost to reach each router):

After first exchange, A computes (neighbours B and C):

• to B: $\min(2+0,\;5+2) = 2$ via B
• to C: $\min(2+2,\;5+0) = 4$ via B
• to D: $\min(2+3,\;5+2) = 5$ via B
• to E: $\min(2+\infty,\;5+4) = 9$ via C

A's vector becomes $(0, 2, 4, 5, 9)$.

After second exchange, A recomputes to E using B's and C's updated vectors (B's cost to E = 4, C's cost to E = 3):

• to E: $\min(2+4,\;5+3) = 6$ via B

A's final vector: $(0, 2, 4, 5, 6)$.

Converged routing table at A:

Note: A reaches E along the path A → B → D → E with cost $2+3+1 = 6$; the next hop from A is therefore B.

Problems: slow convergence and the count-to-infinity problem after a link failure; mitigated by split horizon, route poisoning, and triggered updates. Distance vector routing is used in RIP.

1. Fundamental Characteristics of a Distributed System vs. Centralized Architecture

A centralized system keeps all processing, storage and control at one node (mainframe or single server). A distributed system is a collection of independent computers that appear to users as one coherent system. The distinguishing characteristics are:

Key design goals of a distributed system are transparency, openness, scalability, fault tolerance and resource sharing — none of which a centralized architecture can provide beyond its single box.

2. IaaS vs. PaaS vs. SaaS

All three are cloud service models; they differ in how much of the stack the provider manages* versus the customer.

The stack runs on-premises → IaaS → PaaS → SaaS, with the provider taking over one more layer at each step. Nepal Telecom, for example, may use IaaS for its own VMs, PaaS to host an internal billing application, and SaaS for corporate email.

3. Public, Private and Hybrid Cloud Deployment Models

Public cloud — Infrastructure is owned and operated by a third-party provider (AWS, Azure, Google Cloud) and shared among many tenants over the internet. Advantages: no capital expenditure, pay-as-you-go, elastic scale. Drawbacks: less control, data-residency and compliance concerns, multi-tenant security risk. Suitable for web portals, test environments and variable workloads.

Private cloud — Infrastructure is dedicated to a single organization, hosted on-premises or by a third party. Advantages: full control, strong security and compliance, predictable performance. Drawbacks: high capital and operational cost, limited elasticity. Suitable for banks, telecom core networks and government data centres holding sensitive subscriber data.

Hybrid cloud — A combination of private and public clouds connected so that data and applications can move between them. The private part holds sensitive, latency-critical or regulated workloads; the public part absorbs peak or non-critical workloads (cloud bursting). Advantages: best of both — security plus scalability and cost efficiency. Drawbacks: integration, network and management complexity. Suitable for Nepal Telecom, which can keep subscriber and billing data in a private cloud while using public cloud capacity for seasonal traffic spikes.

Common Gateway Interface (CGI) and Its Role in Dynamic Web Pages

CGI (Common Gateway Interface) is a standard protocol/interface that defines how a web server communicates with external programs (called CGI scripts) to generate web content dynamically. It is not a programming language itself but a specification that allows the server to pass a client's request (form data, query strings, HTTP headers) to an external program and return that program's output back to the browser as an HTTP response.

Working / Role in dynamic web pages:

1. The browser sends a request (e.g., submitting a form) to the web server.
2. The server identifies the request as a CGI request (usually via a /cgi-bin/ directory or file extension).
3. The server executes the corresponding CGI program, passing request data through environment variables (e.g., QUERY_STRING, REQUEST_METHOD, CONTENT_LENGTH) and standard input (STDIN).
4. The CGI program processes the input (e.g., queries a database, performs a calculation).
5. The program writes the result to standard output (STDOUT) in the form of HTTP headers + HTML content.
6. The server forwards this output to the browser, which displays the dynamically generated page.

Why it enables dynamic pages: Unlike static HTML (fixed content), CGI lets the server generate content at runtime based on user input, database state, or session data — enabling login systems, search, feedback forms, e-commerce, etc. CGI scripts can be written in any language (Perl, C, Python, PHP, etc.).

Limitations: Each request spawns a new process, causing high overhead and poor scalability under heavy load — which led to faster alternatives like FastCGI, mod_perl, and embedded scripting (PHP, servlets).

---

Use of PHP and Java for Internet Programming

PHP (Hypertext Preprocessor):

• A server-side, open-source scripting language embedded directly within HTML (<?php ... ?>).
• Runs on the web server via modules like mod_php or FastCGI; the server executes the script and sends only the resulting HTML to the client.
• Widely used for dynamic websites, form handling, session management, and database connectivity (especially MySQL).
• Advantages: easy to learn, cross-platform (Linux/Windows), huge community, low cost.
• Example use: login validation, content management systems (WordPress), e-commerce carts.

Java for Internet Programming:

• Java is used on the server side mainly through Servlets and JSP (Java Server Pages), running inside a servlet container (e.g., Apache Tomcat).
• Servlets are Java classes that extend HttpServlet, handle HTTP requests/responses, and run in a multithreaded environment — more efficient than CGI's process-per-request model.
• JSP allows embedding Java code in HTML (similar to PHP) and is compiled into servlets.
• Advantages: platform independence (Write Once, Run Anywhere), strong typing, robustness, security, enterprise support (J2EE/Jakarta EE), and excellent scalability.
• Example use: banking applications, enterprise web portals, large-scale transactional systems.

Comparison in brief: PHP is lightweight, quick to develop, and ideal for small-to-medium dynamic sites; Java is heavier but offers superior scalability, security, and enterprise-grade reliability for large systems.

Bipolar Junction Transistor (BJT) — 5 marks

Construction

A BJT is a three-terminal, three-layer semiconductor device formed by sandwiching two layers of one type around a thin layer of the other type. It has two forms:

• NPN transistor — a thin P-type base sandwiched between two N-type regions (emitter and collector).
• PNP transistor — a thin N-type base sandwiched between two P-type regions.

The three regions are:

1. Emitter (E): Heavily doped so that it can supply a large number of majority carriers (electrons in NPN, holes in PNP). It is moderately sized.
2. Base (B): Very thin and lightly doped so that most carriers injected from the emitter can pass through to the collector without recombining. This thinness is the key to transistor action.
3. Collector (C): Moderately doped and physically the largest region, so that it can dissipate the heat produced by the large collector current.

Thus two PN junctions are formed: the emitter–base junction (J_E) and the collector–base junction (J_C). Terminals are taken out from all three regions, giving three terminals — emitter, base and collector — with the base common to both junctions. The arrow on the emitter terminal shows the direction of conventional current flow.

Operation (NPN, active mode)

For normal amplification the transistor is biased in the active region:

• Emitter–base junction → forward biased (battery V_BE, base positive w.r.t. emitter).
• Collector–base junction → reverse biased (battery V_CE, collector positive w.r.t. base).

Working:

1. Because J_E is forward biased, the heavily doped emitter pushes a large number of free electrons into the thin base region.
2. The base is very thin and lightly doped, so only about 1–5 % of these electrons recombine with holes in the base. This small recombination current forms the base current I_B.
3. The remaining 95–99 % of the electrons diffuse across the base and reach the depletion region of J_C. Since J_C is reverse biased, its electric field is strong and it collects these electrons, giving the large collector current I_C.
4. Thus the emitter current is the sum of the two:

$I_E = I_C + I_B$

Since I_C is almost equal to I_E and I_B is very small, the current gain is large:

$\alpha = \frac{I_C}{I_E} \approx 0.95\text{–}0.99, \qquad \beta = \frac{I_C}{I_B} \approx 20\text{–}500$

Because a small base current controls a large collector current, the BJT works as a current-controlled current amplifier and is used in switching and amplification circuits. For a PNP transistor the same action occurs, but the majority carriers are holes and all battery polarities are reversed.

1. Object-Oriented Programming Concepts and Modular Program Design in C/C++

Object-Oriented Programming (OOP) organises a program around objects (data + the functions that operate on that data) rather than around procedures. Its four pillars:

• Encapsulation — bundling data and methods into a class, hiding internal state behind access specifiers (private, protected, public). In C++ this is done with class; only public members form the interface.
• Abstraction — exposing only the essential behaviour (e.g. a Stack class offers push()/pop() without revealing the array or linked list underneath).
• Inheritance — a derived class reuses and extends a base class (class Engineer : public Employee), giving code reuse and an "is-a" relationship. C++ supports single, multiple and multilevel inheritance.
• Polymorphism — the same message behaving differently at run time. C++ implements this through virtual functions (dynamic/late binding) and function overloading / operator overloading (compile-time binding).

class Shape {                 // abstract base class
public:
    virtual double area() const = 0;   // pure virtual -> polymorphism
    virtual ~Shape() {}                // virtual destructor
};
class Circle : public Shape {
    double r;
public:
    Circle(double r) : r(r) {}
    double area() const override { return 3.14159 * r * r; }
};

Modular program design means decomposing a large program into independent, cohesive, loosely-coupled modules that can be compiled and tested separately.

• C approach: each module = a .c file + a header .h file. The header declares the public interface; static makes functions/variables private to the file; extern shares them. Compilation units are linked at the end.
• C++ approach: the same idea with namespaces to avoid name clashes, classes as the unit of encapsulation, and header guards (#ifndef … #define … #endif) or #pragma once to prevent double inclusion.
• Principles: high cohesion (one module, one job), low coupling (modules interact only through declared interfaces), information hiding, and separation of interface from implementation. This gives reusability, easier debugging, parallel team development and maintainability — essential for large telecom software such as billing, OSS/BSS and network management systems.

2. Stacks, Queues and Binary Trees — Implementation and Applications

Stack (LIFO — Last In First Out)

Implemented either as an array with a top index or as a singly linked list with insertion/deletion at the head. Core operations: push(), pop(), peek(), isEmpty() — all O(1).

template <class T> class Stack {
    T arr[100]; int top = -1;
public:
    void push(T x) { if (top < 99) arr[++top] = x; }
    T pop()        { return arr[top--]; }
    T peek() const { return arr[top]; }
    bool isEmpty() const { return top == -1; }
};

Applications: expression conversion (infix → postfix/prefix) and evaluation; matching balanced brackets; function-call management (activation records) and recursion; undo/redo; backtracking (DFS, maze, parsing); browser history.

Queue (FIFO — First In First Out)

Implemented as an array with front and rear (circular queue to avoid false overflow) or as a linked list with insertion at the rear and deletion at the front. Operations: enqueue(), dequeue(), front() — O(1).

class Queue {
    int arr[100], front = 0, rear = -1, count = 0;
public:
    void enqueue(int x) { rear = (rear + 1) % 100; arr[rear] = x; count++; }
    int dequeue()       { int x = arr[front]; front = (front + 1) % 100; count--; return x; }
};

Applications: CPU and printer scheduling; BFS traversal of graphs; buffering in routers, switches and packet queues; call-centre and IVR waiting queues; message queues in telecom middleware; disk and I/O scheduling.

Binary Tree

A hierarchical structure where each node has at most two children (left, right). A binary search tree (BST) keeps left < parent < right. Implemented with nodes containing data, left, right pointers. Traversals: inorder (sorted order for BST), preorder, postorder, level-order (uses a queue). Search/insert/delete are O(log n) when balanced, O(n) when skewed.

struct Node { int data; Node *left = nullptr, *right = nullptr; };
Node* insert(Node* root, int x) {
    if (!root) return new Node{x};
    if (x < root->data) root->left  = insert(root->left,  x);
    else                root->right = insert(root->right, x);
    return root;
}

Applications: file systems and directory trees; expression trees in compilers; routing tables and prefix tries in IP routing; decision trees; database indexing (B-tree/B+ tree); Huffman coding for compression.

3. Relational Database Design and Normalization up to 3NF

A relational database stores data in relations (tables) of tuples (rows) and attributes (columns). Design goals: eliminate redundancy, avoid insertion/deletion/update anomalies, and preserve data integrity through keys and constraints.

Functional dependency: $X \to Y$ means each value of $X$ determines a unique value of $Y$. A candidate key is a minimal set of attributes that uniquely identifies a tuple; one is chosen as the primary key.

Normal forms:

• 1NF — every attribute holds atomic (indivisible) values; no repeating groups or multivalued attributes.
• 2NF — in 1NF and every non-prime attribute is fully functionally dependent on the whole primary key (no partial dependency on part of a composite key).
• 3NF — in 2NF and no non-prime attribute is transitively dependent on the primary key (i.e. for every $X \to Y$, either $X$ is a superkey or $Y$ is prime).

Example. Enrollment(StudentID, CourseID, StudentName, CourseName, Instructor)

• Not 2NF: StudentName depends only on StudentID; CourseName only on CourseID.
• Decompose to 2NF: Student(StudentID, StudentName), Course(CourseID, CourseName, Instructor), Enroll(StudentID, CourseID).
• If CourseID → Instructor and Instructor → Dept, then Dept is transitively dependent on CourseID; decompose to 3NF: Course(CourseID, CourseName, Instructor), Instructor(Instructor, Dept).

Normalization up to 3NF removes most redundancy while preserving dependencies; BCNF is a stricter form used when every determinant must be a candidate key.

4. Relational Algebra, SQL Query Facilities and Concurrency Control

Relational Algebra

A procedural query language with six fundamental operations:

Derived operations include join ($\bowtie$), intersection ($\cap$) and division ($\div$). Example: names of students enrolled in course C1:

$$\pi_{Name}\big(\sigma_{CourseID='C1'}(Enroll) \bowtie Student\big)$$

SQL Query Facilities

SQL is a declarative language with DDL, DML, DCL and TCL sub-languages.

-- DDL
CREATE TABLE Student (
    StudentID  INT PRIMARY KEY,
    Name       VARCHAR(50) NOT NULL,
    Dept       VARCHAR(20)
);

-- DML: join + aggregation + grouping
SELECT s.Dept, COUNT(*) AS total
FROM Student s JOIN Enroll e ON s.StudentID = e.StudentID
WHERE e.CourseID = 'C1'
GROUP BY s.Dept
HAVING COUNT(*) > 5
ORDER BY total DESC;

Other facilities: INSERT, UPDATE, DELETE, nested/subqueries, EXISTS, IN, set operators (UNION, INTERSECT, EXCEPT), views, indexes, and GRANT/REVOKE for access control.

Concurrency Control Mechanisms

When many transactions run at once, the DBMS must preserve ACID properties. Problems: lost update, dirty read, unrepeatable read, phantom read.

• Locking: shared (read) and exclusive (write) locks; two-phase locking (2PL) guarantees serializability. Strict 2PL holds exclusive locks until commit.
• Timestamp ordering: each transaction gets a timestamp; conflicting operations are ordered by timestamp and aborted/restarted if out of order.
• Optimistic concurrency control: read, validate, then write; abort on conflict.
• Multiversion concurrency control (MVCC): keeps multiple versions so readers never block writers.
• Deadlock handling: prevention (wait-die, wound-wait), detection via wait-for graph, or timeout and rollback.
• Isolation levels: Read Uncommitted, Read Committed, Repeatable Read, Serializable — trading consistency against concurrency.

These mechanisms keep telecom databases (subscriber records, CDRs, billing) consistent under heavy concurrent load.

Process Scheduling in an Operating System

Process Scheduling is the activity of the operating system that decides which process in the ready queue will be allocated the CPU next, and for how long. Since a single CPU can execute only one process at a time, the OS must arbitrate among many competing processes. The component that makes this decision is called the scheduler (short-term scheduler), and the algorithm it follows is the scheduling algorithm.

Key objectives of process scheduling:

• Maximize CPU utilization and throughput (number of processes completed per unit time).
• Minimize turnaround time (submission → completion), waiting time (time spent in ready queue), and response time (submission → first response).
• Ensure fairness among processes and predictability of performance.
• Enforce priority and meet deadlines where required.

Basic terminology:

• Arrival time (AT): time at which a process enters the ready queue.
• Burst time (BT): CPU time required by the process.
• Completion time (CT): time at which the process finishes.
• Turnaround time (TAT) = CT − AT
• Waiting time (WT) = TAT − BT
• Response time (RT): time from arrival to first CPU allocation.

Scheduling decisions occur at four points: when a process switches from running → waiting, running → ready, waiting → ready, and when a process terminates. If scheduling is allowed at all these points, the algorithm is preemptive; if only at the first and last (running → waiting and termination), it is non-preemptive.

---

Types of Scheduling Algorithms

1. First Come First Served (FCFS)

Concept: The process that requests the CPU first is allocated the CPU first. Implemented with a FIFO queue. It is non-preemptive.

Characteristics:

• Simple to implement; no starvation.
• Once a process gets the CPU, it runs to completion or until it blocks for I/O.
• Average waiting time is often long and depends heavily on arrival order.

Merits: Easy to understand and code; fair in the order of arrival; no starvation.

Demerits: Suffers from the convoy effect — one long CPU-bound process at the head blocks many short processes behind it, raising average waiting time. Poor for time-sharing systems; response time can be very high.

Suitability: Batch systems where order of execution is not critical and interactive response is not required. Not suitable for interactive or real-time systems.

Example: Processes P1 (BT 24), P2 (BT 3), P3 (BT 3) arrive at time 0 in order P1, P2, P3.

• WT(P1) = 0, WT(P2) = 24, WT(P3) = 27
• Average WT = (0 + 24 + 27)/3 = 17 ms

If order were P2, P3, P1: Average WT = (0 + 3 + 6)/3 = 3 ms — showing order sensitivity.

---

2. Shortest Job First (SJF)

Concept: The process with the smallest next CPU burst is selected. It may be non-preemptive (once running, it finishes) or preemptive (then called Shortest Remaining Time First, SRTF).

Characteristics:

• Provably optimal in terms of minimum average waiting time for a given set of processes.
• Requires knowledge of the next CPU burst, which is estimated using exponential averaging of past bursts: $\tau_{n+1} = \alpha\,t_n + (1-\alpha)\,\tau_n,\quad 0 \le \alpha \le 1$

Merits: Gives the minimum average waiting time; good throughput; SRTF gives the best response time among non-priority algorithms.

Demerits: Difficult to predict burst time accurately; starvation of long processes is possible; preemptive version needs frequent context switches (overhead).

Suitability: Batch and interactive systems where burst times can be estimated; long-term scheduling in job pools. Not ideal for real-time systems with strict deadlines.

Example: P1 (BT 6), P2 (BT 8), P3 (BT 7), P4 (BT 3), all arriving at time 0.

Order: P4 → P1 → P3 → P2

• WT(P4) = 0, WT(P1) = 3, WT(P3) = 9, WT(P2) = 16
• Average WT = (0 + 3 + 9 + 16)/4 = 7 ms

---

2. Priority Scheduling

Concept: Each process is assigned a priority number; the CPU is given to the process with the highest priority. It may be preemptive or non-preemptive. Equal priorities are broken by FCFS.

Characteristics:

• Priorities may be static (fixed at creation) or dynamic (change with age/behaviour).
• A common remedy for starvation is aging — gradually increasing the priority of waiting processes.

Merits: Allows important/system-critical processes to be served first; flexible; supports real-time requirements.

Demerits: Starvation of low-priority processes; priority inversion problems; requires careful priority assignment.

Suitability: Real-time and time-critical systems (e.g., interrupt handling, system daemons), OS kernels, and systems where some tasks are inherently more important than others.

---

3. Round Robin (RR)

Concept: Designed for time-sharing. The ready queue is treated as a circular queue; each process gets the CPU for a fixed time quantum $q$ (typically 10–100 ms). If the burst exceeds $q$, the process is preempted and placed at the tail of the queue. It is preemptive.

Characteristics:

• Performance depends heavily on the choice of $q$.
• If $q$ is very large → behaves like FCFS.
• If $q$ is very small → too many context switches, overhead dominates.
• Rule of thumb: $q$ should be large enough that ~80% of bursts finish within one quantum.

Merits: Fair — every process gets a turn; good response time; no starvation; well suited to interactive systems.

Demerits: Average waiting time is often longer than SJF; context-switch overhead; performance sensitive to quantum size.

Suitability: Time-sharing and interactive systems (UNIX, Linux, Windows use variants); general-purpose OS scheduling.

Example: P1 (BT 24), P2 (BT 3), P3 (BT 3), $q = 4$ ms.

• P1 runs 0–4, P2 runs 4–7 (finishes), P3 runs 7–10 (finishes), P1 runs 10–14, 14–18, 18–22, 22–26, 26–30 (finishes).
• WT(P1) = 6 ms, WT(P2) = 4 ms, WT(P3) = 7 ms
• Average WT = (6 + 4 + 7)/3 ≈ 5.67 ms

---

4. Multilevel Queue Scheduling

Concept: The ready queue is partitioned into several separate queues (e.g., system processes, interactive, batch), each with its own scheduling algorithm. Processes are permanently assigned to a queue based on type.

Characteristics:

• Queues have fixed priorities; a lower queue runs only when higher queues are empty.
• Time-slicing between queues is also possible (e.g., 80% to foreground, 20% to background).

Merits: Separates process classes; gives fast service to interactive jobs; simple to implement.

Demerits: Inflexible — a process cannot move between queues; starvation of lower-priority queues; tuning of queue priorities is difficult.

Suitability: Systems with clearly distinct job classes — e.g., a system running both real-time control tasks and batch jobs.

---

5. Multilevel Feedback Queue (MLFQ)

Concept: Like multilevel queue, but processes can move between queues based on their behaviour and aging. A process using too much CPU is demoted; a process waiting long is promoted.

Characteristics:

• Defined by: number of queues, scheduling algorithm per queue, promotion/demotion policy, and entry queue.
• Typically the most general and flexible CPU-scheduling algorithm.

Merits: Adapts to process behaviour; favours short and interactive jobs; prevents starvation through aging; high flexibility.

Demerits: Complex to implement and tune; many parameters to configure; higher overhead.

Suitability: General-purpose and modern OS scheduling (used in variants by Linux, Windows, Solaris); systems with a mix of interactive and batch workloads.

---

Comparison Summary

Conclusion: No single algorithm is best for all situations. FCFS is simplest but suffers the convoy effect; SJF minimizes average waiting time but needs burst prediction and risks starvation; Priority scheduling serves critical tasks but needs aging; Round Robin gives fairness and good response time for interactive systems; and Multilevel Feedback Queue combines the strengths of all, making it the preferred choice in modern general-purpose operating systems.