A2 Comp Sci

Data Representation

Why use User Defined Data Types (UDDTs)?

• To group a specific set of related data under a single identifier

• Make program code clearer and easier to read/maintain

• To produce a data structure that precisely matches the requirements of a real-world problem

Non Composite VS Composite

Non Composite:

- Enumerated

• A non composite user defined data type consisting of an ordered list containing all possible values for a variable

• Key Features:

• Ordered - elements exist in a specific sequence

• Unique elements - no repeat or duplicate values permitted

• All items on the list belong to the same data type

• Pseudocode example:

• TYPE Spectrum = (Red, Orange, Yellow, Green, Blue, Indigo, Violet)

- Pointer

• A non composite user defined data type used to store and reference a memory address while indicating the data type stored at that location    

• Pseudocode example:

• TYPE Word = ^STRING

Composite

- Record

• A composite data type that combines a fixed number of related items/fields, which can be of different data types, under a single identifier

• Pseudocode example:

• TYPE BookingRecord

                 DECLARE BookingID : STRING

                 DECLARE SeatNumber : 1 .. 12 // 1 to 12 inclusive

• DECLARE CurrentBooking : BookingRecord

- Set

• A composite data type consisting of an unordered collection of unique elements of the same data type with supports mathematical set theory (Union, Internsection)

• Pseudocode example:

• TYPE SymbolSet = SET OF CHAR

• DEFINE Operators (‘+’, ‘-’, ‘/’, ‘*’) : SymbolSet

- Class

• Encapsulates both properties/attributes and methods/procedures/functions with a single object structure

File Organisations

Hashing algorithm:

• A mathematical formula applied to a record’s key field to generate the physical storage address where the record is stored or retrieved

Collision:

• Occurs when two distinct record keys generate the exact same hash value after passing through the hashing algorithm. Because two records cannot occupy the same physical address, a collision resolution strategy is required

Collision resolution strategies:

- Linear Probing / Closed hashing:

• Starts at the calculated hashed space and searches subsequent memory slots linearly/sequentially, placing the record in the first available empty space

- Overflow Area / Open hashing:

• Stores colliding records in a separate, dedicated overflow area, searching it linearly for the first free space

Process to Find a Record in a Random File^:

1. Direct file access is initiated.

2. Apply the hashing algorithm to the target record's key field to calculate its storage address

3. Read the calculated address and inspect the record key

4. If the key at that location matches the target key, retrieve the record

5. If the key does not match (indicating a collision occurred during writing), execute the collision strategy

• Linear Probing: Search linearly from that address onwards until the key is matched

• Overflow Area: Search the overflow area linearly until the key is matched

6. If an empty slot is encountered (or end of overflow area is reached) without a match, report record not found

Floating Point:

Reasons for normalisation:

• Maximum precision - eliminating redundant bits

• Maximum range - allows representing the largest possible range of numbers in the smallest number of bits

• Allows for unique representation - prevents multiple representations of same value

Bit Allocation Trade Offs

Increasing Mantissa bits:

• Increases precision/accuracy of representation

• Decreases the range of numbers that can be stored

Increasing the Exponent bits:

• Increases the range of numbers (enable storing very large/small numbers)

• Decreases precision/accuracy, increasing rounding errors

Communication and Internet Technologies

Protocol:

• A standard set of rules for communication between the computer systems

- Why are they essential?

• Estabilishing standards - sets a mandatory set of rules for transferring data across networks

• Ensures compatibility - enables communication and compatibility between hardware and software platforms from different manufacturers

• Makes network communications independent of specific hardware/software

• Without protocols, 2 devices using different rules wouldn’t be able to transmit or interpret messages

Each layer only interacts with the layers above/below it

Outgoing transmission (Top to Bottom):

• The user/application software interfaces with the application layer at the top. As data moves down the stack, each layer adds its own header information before handing it off to the lower layer

Incoming transmission (Bottom to Top):

• When receiving data, frames are accepted by the Link Layer and passed upwards through adjacent layers, stripping headers until reaching the application layer

1. Application Layer

• Primary Purpose: Provides user services and programs (such as web browsers or email clients) access to network transmission capabilities

• Key Functions:

  • Defines protocols used by applications to exchange data across networks

  • Interacts directly with user-level software applications

  • Provides mechanisms for securing communications (such as encryption and authentication)

  • Handles application-specific error detection and recovery

2. Transport Layer

• Primary Purpose: Responsible for logical end-to-end, error-free delivery of data between applications running on source and destination hosts

• Key Functions:

  • Segmentation & Reassembly: Breaks outgoing data into smaller segments/packets and reconstructs them at the destination

  • Sequence Control: Adds sequence numbers to packet headers to reorder arriving packets into the correct sequence

  • Error & Flow Control: Provides flow control mechanisms to regulate connections and prevent data loss, using checksums and Automatic Repeat Requests (ARQ) to retransmit corrupted or lost packets

3. Internet Layer

• Primary Purpose: Identifies the intended network and host, formatting data into datagrams and routing them across intermediate networks

• Key Functions:

  • IP Addressing: Attaches headers containing source and destination IP addresses to packets

  • Routing: Determines the optimum independent route for datagrams across the network

  • Sockets: Combines an IP address with a port number to create a socket for targeted host-process addressing

4. Link Layer

• Primary Purpose: Manages links between directly connected physical nodes on local network segments and interfaces directly with transmission hardware

• Key Functions:

  • Framing: Formats datagrams into physical frames for transmission

  • Address Resolution: Maps logical IP addresses to physical MAC addresses

  • Physical Media Control: Handles physical transmission error checking, correction, and hardware protocol adherence

Application Layer Protocols Reference Guide

• HTTP / HTTPS (Hypertext Transfer Protocol / Secure):

  • Purpose: Used for transferring web pages, hypermedia documents, images, and data files securely between web servers and client browsers over the World Wide Web

• FTP (File Transfer Protocol):

  • Purpose: Used for interactive uploading, downloading, and transferring files between client and server locations on a network

• SMTP (Simple Mail Transfer Protocol):

  • Type: Push protocol

  • Purpose: Used for sending email messages from a client computer to a mail server, or transferring emails between mail servers

• POP3 (Post Office Protocol 3):

  • Type: Pull protocol

  • Purpose: Used for downloading/retrieving emails from a mail server to a local client computer (typically removes messages from the server upon download)

• IMAP (Internet Message Access Protocol):

  • Type: Pull protocol

  • Purpose: Used for retrieving and reading emails from a mail server while synchronizing messages across multiple devices without removing them from the server

BitTorrent Protocol

• Network Model: Peer-to-Peer (P2P) network model where all connected user computers act as peers of equal status without relying on a central web server

• Key Definitions & Components:

  • Torrent Descriptor File: A small file containing metadata about the file to be shared

  • Swarm: The group of connected computers simultaneously sharing and downloading pieces of a file

  • Tracker: A central server that maintains records and IP addresses of all computers in the swarm to help them connect

  • Seed: A peer that possesses a complete copy of the file and continues uploading it to others

  • Leech: A peer that downloads significantly more data than it uploads

• Operational Process:

  1. The target file is split into small, equal-sized pieces

  2. A peer downloads the torrent descriptor file and connects to the tracker.

  3. The tracker shares the IP addresses of other peers in the swarm.

  4. Peers simultaneously download missing pieces from multiple peers while uploading received pieces to others

  5. Once a peer completes the full file download, it becomes a seed

Transport Layer Security (TLS)

TLS relies on two distinct protocols to secure network communications:

1. Handshake Protocol: Establishes a secure and reliable connection between devices by authenticating the client and server and negotiating encryption algorithms

2. Record Protocol: Encrypts and authenticates application data, managing transmission formats to preserve confidentiality and message integrity

Transmission Methods: Circuit Switching vs. Packet Switching

Circuit Switching

• Mechanism: A dedicated physical circuit/channel is established between sender and receiver prior to transmission, maintained throughout the communication, and closed upon completion. Data flows in a continuous stream over a single fixed route

• Appropriate Uses: Real-time voice calls, live video streaming, or private networks requiring continuous bandwidth

Packet Switching

• Mechanism: Messages are divided into small, equal-sized packets. Each packet receives a header containing source/destination IP addresses, packet numbers, etc., and travels independently across dynamic optimum routes. Packets arriving out of order are reassembled at the destination.

• Appropriate Uses: General data networks (Internet), email, web pages, and file transfers where connection resilience and line sharing are needed.

Router Mechanics & Error Recovery in Packet Switching

Function of a Router

1. Header Inspection: Examines arriving packet headers to extract destination IP addresses.

2. Routing Table Consultation: Consults an internal routing table containing netmasks, gateways, adjacent routers, and line statuses

3. Route Determination: Determines the optimum next hop or best path based on network traffic and congestion

4. Hop Counter Management: Decrements the packet's hop counter (TTL) by 1 at each router pass

5. Forwarding: Dispatches the packet to its next intermediate hop

Error Recovery & Completeness

• Re-send Requests: The destination host checks arriving packets for damage or missing sequence numbers. If a packet is missing or corrupted, a re-send request is generated

• Hop Count Expiry: If a packet's hop count is decremented to zero, the packet is retired/dropped to prevent infinite loops, which triggers a re-send request

System Software

1. Purposes of an Operating System (OS)

Core Operating System Functions & Abstraction

• Hardware Abstraction: The OS conceals low-level hardware complexity from the user through multiple mechanisms:

  • User Interface (UI / GUI): Provides intuitive interaction (icons, menus, point-and-click) so users avoid typing complex low-level code or hardware instructions.

  • Device Drivers: Software that translates OS commands into hardware-specific instructions, allowing control of peripherals (e.g., printers) via the OS rather than directly on the peripheral device.

  • Device Mapping: Identifies physical and virtual devices across a network and manages their status.

  • Top-Layer Abstraction: The user interacts only with the top application layer (e.g., in TCP/IP protocol suites), hiding lower network transport and framing complexities.

Process Management & Multi-Tasking

• Multi-Tasking: The concurrent execution of multiple programs/processes sharing CPU time and hardware resources so they appear to run simultaneously.

• Efficiency & Monitoring: The OS monitors process states, uses scheduling routines to maximize resource usage, and ensures processes do not clash or starve each other.

The Three Process States

Processes exist in one of three primary states:

1. Running State: CPU execution time is currently allocated, and the process instructions are actively being executed by the processor.

2. Ready State: The process is waiting in the ready queue for its allocated CPU time slice; it is fully prepared to execute.

3. Blocked State: The process cannot run because it is waiting for an I/O operation (e.g., disk read/write) or external event to complete.

State Transitions (Running \(\rightarrow\) Ready)

A process transitions from Running to Ready under the following conditions:

• The allocated time quantum / time slice expires in a pre-emptive scheduling scheme (e.g., Round Robin).

• The running process is pre-empted by a process with a higher priority entering the ready queue.

• An interrupt signal arrives at the CPU.

Process Scheduling

• Purpose of Scheduling:

  • Ensures CPU idle time is minimized and all processes are executed in a timely manner.

  • Prevents process starvation and guarantees fair access to CPU resources.

  • Manages execution order according to job priority.

Scheduling Algorithms

1. Round Robin (RR):

   • Mechanism: A pre-emptive routine where processes are placed in a queue and each process is allocated a fixed time quantum (time slice). When a time slice ends, the process's state is saved, it is returned to the queue, and the next process is restored.

   • Benefit: Guarantees equal CPU access, eliminates process starvation, and minimizes average response time.

2. Shortest Job First (SJF):

   • Mechanism: A non-pre-emptive routine where queued jobs are sorted and executed in ascending order of estimated CPU burst time. Once execution starts, it runs to completion or until blocked.

   • Benefit: Maximizes process throughput and significantly reduces overall waiting times for short tasks. (Note: Long jobs may suffer starvation if short jobs are continuously added).

3. Shortest Remaining Time (SRT):

   • Mechanism: A pre-emptive version of SJF. If a newly arriving process has a shorter remaining execution time than the currently running process, the current process is pre-empted.

   • Benefit: Short processes complete extremely rapidly and waiting times are minimized.

4. First Come First Served (FCFS):

   • Mechanism: A non-pre-emptive routine where jobs are queued strictly by arrival order and executed one by one.

   • Benefit: Simple logic with minimal OS processing overhead; prevents starvation since every process is eventually served.

Interrupt Handling & The Kernel

• Kernel: The fundamental central core of the Operating System that interfaces between hardware and software.

• Interrupt Handling Routine:

  1. The kernel receives an interrupt signal from hardware or software.

  2. It evaluates interrupt priority against the currently running task.

  3. If higher priority, the system shifts into kernel mode.

  4. The kernel consults the Interrupt Descriptor Table (IDT) / Interrupt Vector Table (IVT).

  5. The contents of CPU registers and current process state are saved onto the kernel stack.

  6. The specific Interrupt Service Routine (ISR) is executed, after which the previous process state is restored from the stack.

Memory Management

• Virtual Memory: A technique using secondary storage (hard disk or SSD) to extend physical RAM when main memory runs low, enabling large programs or many concurrent tasks to execute.

Division Methods: Paging vs. Segmentation

• Disk Thrashing: A critical memory management failure occurring when RAM is exhausted and virtual memory is heavily used. Pages are constantly swapped back and forth between main RAM and secondary storage at an excessive rate, causing heavy hard drive latency. Eventually, more CPU time is spent swapping pages than executing instructions ("thrash point"), causing system lockup.

2. Translation Software (BNF, RPN & Compilers)

Translators: Compilers vs. Interpreters

• Compiler: Translates the entire high-level source code into machine code / object code prior to program execution.

• Interpreter: Executes high-level source code directly without generating a standalone executable file:

  1. Examines source code one line / statement at a time.

  2. Checks statement for syntax errors.

  3. If error-free, executes the statement immediately.

  4. If an error is found, execution halts and an error report is generated.

  5. Translation must be repeated every time the program runs (including repeated loop iterations).

Stages of Compilation

Compilation progresses through four distinct sequential stages:

1. Lexical Analysis:

   • Takes modified source code, removes unnecessary whitespace and comments.

   • Converts character sequences into a stream of categorized tokens.

   • Identifiers (variable names, functions) are cataloged into a Symbol Table.

   • Invalid tokens trigger error reports; valid token streams are passed to Syntax Analysis.

2. Syntax Analysis (Parsing):

   • Receives the token stream from the Lexical Analyser.

   • Checks tokens against the syntax and formal grammar rules of the programming language.

   • Constructs a Parse Tree.

   • Outputs syntax error reports if language rules are broken.

3. Code Generation:

   • Converts the verified intermediate representation / parse tree into machine code or assembly code instructions.

4. Code Optimisation:

   • Reorders code and eliminates redundant instructions to improve efficiency.

   • Purposes: Minimizes program execution time, CPU cycles, and memory/storage usage.

   • Examples:

     • Constant Folding: Replacing constant calculations (e.g., replacing 2 * 6 with 12 at compile time).

     • Redundant Instruction Removal: Eliminating unnecessary register load/store instructions when values are already held in the accumulator.

Formal Syntax Description

• Backus-Naur Form (BNF): A formal context-free metadata notation used to define the syntax rules of a programming language.

  • ::= means "is defined as".

  • | means "OR".

  • <non-terminal> represents sub-rules (e.g., <digit> ::= 0 | 1 | 2).

  • Recursion: Used to express repetition (e.g., <word> ::= <letter> | <word><letter>).

• Syntax Diagrams: Graphical flowcharts defining syntax rules, utilizing directed arrows, options, and loops to depict valid language structures.

Reverse Polish Notation (RPN / Postfix)

• Definition & Benefits:

  • An unambiguous postfix mathematical notation where operators follow their operands.

  • Evaluated strictly from left to right without requiring brackets or operator precedence rules (BODMAS).

Stack Evaluation of RPN Expressions

RPN expressions are evaluated using a Stack data structure:

1. Read the RPN expression from left to right, item by item.

2. If the item is an operand / value, push it onto the stack.

3. If the item is an operator, pop the top two values from the stack.

4. Apply the operator to those two values and push the resulting calculated value back onto the stack.

5. Repeat until the end of the expression is reached; the final remaining stack element is the result.

Security

1. Key Terminology & Security Objectives

• Plain Text: The original, unencrypted text/data before it is processed by an encryption algorithm.

• Cipher Text: Text that has been encrypted from plain text using an encryption algorithm.

• Public Key: A cryptographic/encryption key in a matched pair that is published/known to all users and can be obtained by anyone to encrypt messages or decrypt a sender's digital signature.

• Private Key: A secret, unpublished key that is kept secure by its owner, never transmitted anywhere, and used to decrypt data encrypted with its matching public key.

• Core Objectives of Cryptography:

  • Authenticity: Proves the message came from a genuine, trusted source.

  • Confidentiality: Ensures only the intended recipient with the decryption key can read the message.

  • Integrity: Guarantees that the message has not been altered or tampered with during transmission.

  • Non-Repudiation: Prevents either the sender or the receiver from denying that the transmission occurred.

2. Symmetric vs. Asymmetric Key Encryption

3. Asymmetric Key Communication Workflows

A. Sending a Private/Confidential Message (Public Key Encryption)

1. The recipient generates a matched key pair (public key and private key) of encryption keys

2. The recipient makes their public key available to the sender (or to everyone).

3. The sender encrypts the message (plain text) using the recipient's public key to create cipher text.

4. The sender transmits the cipher text to the recipient.

5. The recipient decrypts the cipher text using their private key.

B. Sending a Verified Message (Digital Signature / Authentication)

1. The sender generates a matched key pair.

2. The sender makes their public key publicly available.

3. The sender encrypts the message (or message digest) using their private key.

4. The sender transmits the message to the group/recipient.

5. Anyone receiving the message can decrypt it using the sender's public key, confirming the sender's identity and providing non-repudiation.

4. Digital Certificates

• Definition: An electronic/online document issued by a Certificate Authority (CA) to authenticate/prove the online identity of an individual, organisation, or website.

• Common Contents:

  • Name of the certificate holder (Subject)

  • Subject’s public key

  • Certificate serial number & version number

  • Validity period (start date and expiration date)

  • Subject’s digital signature

  • Digital signature of the CA / Certificate issuer details

Process to Acquire a Digital Certificate

1. The organisation generates a public and private key pair locally using a web browser or RSA key generator.

2. The organisation submits a request to a Certificate Authority (CA).

3. The CA responds with its own public key and digital certificate signed with the CA's private key.

4. The organisation gathers authentication details to prove its identity and sends this information (along with its public key) to the CA, encrypted using the CA's public key and signed with the organisation's private key.

5. The CA verifies the submitted details and issues the signed digital certificate containing the organisation's public key.

5. Digital Signatures

• Purpose: Used to verify the origin/authenticity of a message and ensure that it has not been altered during transmission.

Creating a Digital Signature (Sender Side)

1. The original message is processed through an agreed hashing algorithm to generate a fixed-size message digest.

2. The message digest is encrypted using the sender's private key to form the digital signature.

3. The digital signature is attached to the message and sent.

Checking/Verifying a Digital Signature (Receiver Side)

1. The recipient receives the message and attached digital signature.

2. The recipient decrypts the digital signature using the sender's public key to recover the original message digest sent by the sender.

3. The recipient hashes the received message using the agreed hashing algorithm to produce a new message digest.

4. The recipient compares the two message digests:

   • If identical: The message has not been altered, and the sender's identity is verified.

   • If different: The message was modified during transmission or the signature is invalid.

6) SSL / TLS Protocols (Secure Sockets Layer / Transport Layer Security)

• Purpose:

  • Provide end-to-end communication security, privacy, and data encryption over a network/internet.

  • Enable clients and servers to authenticate each other and maintain data integrity.

• Typical Use Cases:

  • Transmitting sensitive credentials (passwords, session cookies, input forms).

  • Protecting non-public or financial data in transit against eavesdropping or modification.

Client-Server SSL/TLS Handshake Process

1. Initiation: A client application initiates a connection request to the server.

2. Session Start: The client and server begin an SSL/TLS handshake.

3. Certificate Request: The client requests the server's digital certificate (or the server sends it automatically).

4. Verification: The client verifies the server’s digital certificate and extracts the server’s public key.

5. Session Key Negotiation: Encryption algorithms are agreed upon, and temporary symmetric session keys are generated for the session.

6. Secure Channel Established: Encrypted communication commences using the symmetric session key.

7. Quantum Cryptography

• Purpose: Uses the principles of quantum mechanics (e.g., properties of light photons) rather than mathematical algorithms to generate encryption keys, producing virtually unbreakable encryption and detecting eavesdropping.

Benefits

• Virtually Unhackable: Relies on rapidly changing quantum states and laws of physics.

• Eavesdropping Detection: Any attempt to intercept or observe the transmission alters the quantum state/polarisation of the photons, instantly alerting the receiver.

• Guaranteed Key Integrity: Keys cannot be cloned or copied due to the no-cloning theorem.

• Enhanced Security: Supports longer, more secure key exchanges suitable for sensitive secrets.

Drawbacks

• Short Range: Currently limited to relatively short transmission distances.

• High Cost & Specialised Hardware: Requires expensive dedicated optical fibre lines and specialised hardware.

• Transmission Vulnerabilities: Photon polarisation can be accidentally altered as light travels through fibre optic cables, causing errors.

• Lack of Features: Currently lacks secondary features like digital signatures or certified mail.

• Misuse Potential: High level of security can be exploited by criminals or hostile actors to hide communications from law enforcement.

Further Programming

1. Programming Paradigms Overview

A programming paradigm is a fundamental style or approach to computer programming. Cambridge Paper 3 covers four primary paradigms:

2. Object-Oriented Programming (OOP)

Key Definitions & Terminology

• Class: A template or blueprint from which objects are created. It defines the structure including attributes/properties with data types, methods (subroutines acting on attributes), getters/setters, and a constructor.

• Object / Instance: An occurrence or instantiation of a class during the execution of a program.

• Encapsulation: The process of putting properties (data) and methods together as a single unit. It restricts external access to data and hides values of a structured data object inside a class.

• Inheritance: The process by which a derived class (subclass) inherits/takes all properties (attributes) and methods from a parent class (superclass or base class). Represents an "is a" relationship. Inherited attributes and methods can be extended, copied, or overridden in the subclass.

• Polymorphism: Allows methods with the same name to be redefined or behave differently in derived/inherited classes or subclasses.

• Aggregation: The process by which one class contains another class or represents a hierarchy of nested classes/objects. Represents a "has a" relationship between classes.

• Property / Attribute: Data items, variables, or characteristics defined within a class.

• Method: A programmed function, procedure, or subroutine defined as part of a class that implements behaviors and acts on properties.

• Getter: A method used to access or return the value of a property/attribute.

• Setter: A method used to update or change the value of a private property/attribute.

• Constructor: A special method (e.g. PUBLIC PROCEDURE NEW) used to initialize attribute values when instantiating objects of a class.

Class vs. Object: Key Differences

Standard Pseudocode Syntax for OOP

CLASS Node
    PRIVATE Content : STRING
    PRIVATE Pointer : INTEGER

    PUBLIC PROCEDURE NEW(NewContent : STRING, NewPointer : INTEGER)
        Content <- NewContent
        Pointer <- NewPointer
    ENDPROCEDURE

    PUBLIC FUNCTION GetContent() RETURNS STRING
        RETURN Content
    ENDFUNCTION

    PUBLIC PROCEDURE SetContent(Value : STRING)
        Content <- Value
    ENDPROCEDURE
ENDCLASS

(Reference: Official Mark Schemes)

3. Declarative Programming (PROLOG Logic Programming)

Declarative logic programming states a program as a set of logical relations using facts, rules, and goals.

Core Components

1. Facts (Clauses): Stated truths representing relationships or properties.

   • Example: customer(petrov).

   • Example: owns(projector, petrov).

2. Variables & Goals: Variables start with an uppercase letter (e.g. Owner, Pet, List). Querying a goal returns all matching substitutions.

   • Goal Query: owns(projector, Owner) returns Owner = petrov, susan, sammy.

3. Rules: Conditional logic structured as Head IF Body.

   • AND Logic: Expressed using AND or commas ,.

   • NOT Logic: Expressed using NOT or \+.

   • Syntax Example:

     may_buy_device(D, A) IF device(D) AND customer(A) AND NOT owns(D, A).
     

4. Low-Level Programming & Assembly Language

Assembly programs execute instructions directly using processor registers, primarily the Accumulator (ACC).

Addressing Modes

• Immediate Addressing (#n): The operand contains the denary value n directly (e.g. LDM #500 loads the number 500 into ACC).

• Direct Addressing (<address>): The operand specifies the memory address whose contents are loaded into ACC (e.g. LDD 500 loads the contents stored at location 500 into ACC).

• Indirect Addressing (<address>): The location at <address> contains a second address; the contents of this second address are loaded into ACC (e.g. LDI 500).

Assembly Instruction Set Reference Table

5. File Processing

File handling covers sequential processing (text files) and random access processing (binary files using record structures).

Pseudocode File Operations

User-Defined Record Data Types (UDTs)

Records are defined using TYPE ... ENDTYPE before file operations:

TYPE TAccount
    DECLARE AccountNumber : INTEGER
    DECLARE LastName : STRING
    DECLARE FirstName : STRING
ENDTYPE

DECLARE Customer : TAccount

(Reference: Official Mark Schemes)

6. Exception Handling

Definition & Core Purpose

• Definition: Exception handling is a process that responds to unwanted or unexpected events when a program is running to prevent the program/computer from halting or crashing unexpectedly.

• Implementation Mechanism: Managed using exception handling routines such as try ... except / catch constructs to catch runtime errors and display meaningful error messages.

Key Reasons for Including Exception Handling

1. To trap runtime errors before they reach the OS.

2. To prevent a program from terminating unexpectedly during execution.

3. To produce meaningful error messages to inform the user of issues.

Causes & Specific Examples of Exceptions

Hardware and Virtual Machines

Module 1: Virtual Machines (VMs) & OS Roles

1. Definitions & Core Architecture

• Virtual Machine (VM): A standalone software environment running on a physical computer that emulates the hardware and/or software of another computer system. It is not a physical machine, but VM software contains all components of a physical computer system. The host machine provides all the physical resources e.g RAM/ROM and is controlled via a host operating system. A guest OS runs within the VM/host OS and multiple guest OS can run on the same VM

• Host Operating System: The primary operating system installed on the physical machine. It controls all physical hardware resources (such as RAM, ROM, and processor access), runs the virtual machine software, and provides the user interface to operate it.

• Hypervisor: The software layer running between the host OS and guest OS that creates, manages, and executes virtual machines while allocating host physical resources to the guest OS.

• Guest Operating System: The operating system running inside the virtual machine. It controls virtual hardware/software during emulation, provides a virtual user interface, and accesses physical host hardware indirectly via the hypervisor and host OS. Multiple guest OSs can run on the same physical host.

2. Benefits of Virtual Machines

1. Compatibility & Legacy Software: Allows applications or legacy software incompatible with the host computer or host OS to run via a compatible guest OS.

2. System Isolation & Protection: Suspicious software, crashes, or malware inside a guest OS are contained entirely within the VM and cannot infect or crash the host machine or other VMs.

3. Cost Savings: Eliminates the need to buy additional physical hardware to test or run multiple software environments.

4. Multi-OS Testing: Allows multiple operating systems or new computer system architectures to coexist and be emulated on a single machine.

3. Limitations & Drawbacks of Virtual Machines

1. Degraded Performance: Less efficient than running on native physical hardware due to indirect hardware access requests, execution of extra emulation code, and shared system resources (CPU/RAM load).

2. Hardware Constraints: Performance is strictly dependent on host capabilities, and certain modern hardware/software features cannot be fully emulated or directly accessed.

3. Maintenance Complexity: Setting up, managing, and maintaining both the host OS and virtual machine environments increases overall administrative complexity and cost.

4. Inaccurate Performance Metrics: Software response times and performance benchmarks cannot be accurately measured inside a virtual machine.

Module 2: Processor Architecture (RISC vs. CISC)

1. Characteristics of RISC (Reduced Instruction Set Computer)

• Instruction Set: Uses a small/low number of simple, fixed-length, and fixed-format instructions.

• Clock Cycles: Instructions execute in a single clock cycle.

• Registers & Memory: Uses many general-purpose registers. Memory access is restricted strictly to explicit LOAD and STORE instructions, making heavy use of RAM.

• Control Unit & Cache: Uses a hardwired control unit. Cache is split into separate data and instruction caches.

• Hardware Design: Emphasis is placed on software, requiring simpler circuits with fewer physical transistors. Highly suitable for pipelining.

2. Characteristics of CISC (Complex Instruction Set Computer)

• Instruction Set: Uses a large instruction set with variable-length instructions and many instruction formats.

• Clock Cycles: Instructions are complex and converted into micro-instructions requiring multiple clock cycles.

• Registers & Memory: Uses fewer general-purpose registers. Many instruction types address memory directly using a wide range of complex addressing modes.

• Control Unit & Cache: Uses micro-coded / programmable control units. Relies heavily on cache memory.

• Hardware Design: Emphasis is placed on hardware with complex internal circuitry. Has lower/poorer pipelineability.

3. Summary Comparison Table

Module 3: Pipelining & Interrupt Handling

1. Pipelining Concepts & Stages

• Definition: An instruction execution technique where multiple instructions are processed concurrently to increase CPU instruction throughput (number of instructions completed per unit of time).

• The 5 Pipeline Stages:

  1. Instruction Fetch (IF)

  2. Instruction Decode (ID)

  3. Operand Fetch (OF)

  4. Instruction Execute (IE)

  5. Write Back Result (WB)

• Execution Rules:

  • Each subtask stage completes in 1 clock cycle.

  • No two instructions can execute the exact same subtask stage during the same clock cycle.

  • Subsequent instructions begin in successive clock cycles (e.g., Instruction 2 starts IF on Clock Cycle 2 while Instruction 1 moves to ID).

2. Interrupt Handling Process

1. The processor checks for an interrupt at the start or end of a fetch-execute cycle.

2. If detected, current program execution stops temporarily, and the status of all registers is pushed/saved onto the stack.

3. The Interrupt Service Routine (ISR) is executed to process the interrupt.

4. Once serviced, register contents are restored from the stack, and normal program execution resumes.

3. Effect of Pipelining on Interrupt Handling

• Pipelining adds complexity because multiple instructions in different stages of completion are in the pipeline when an interrupt arrives.

• Flushing the Pipeline: All instructions currently in operation inside the pipeline are discarded (flushed), except for the last instruction that has reached the write-back stage.

• The ISR is then applied to service the interrupt.

• Once serviced, the processor restarts fetching starting from the next sequential instruction.

Module 4: Parallel Processing & Computer Architectures

1. Flynn's Taxonomy

• SISD (Single Instruction, Single Data): Sequential architecture containing one processor, one control unit, and one memory unit. Executes a single instruction stream on a single data stream.

• SIMD (Single Instruction, Multiple Data): Parallel architecture using multiple/array processors. Performs the exact same operation simultaneously across multiple different data streams. Takes advantage of pipelining.

• MISD (Multiple Instruction, Single Data): Parallel architecture where multiple processors independently perform different operations on the same single data stream simultaneously.

• MIMD (Multiple Instruction, Multiple Data): Parallel architecture with many processors that execute different instructions on different data sets asynchronously / independently.

2. SIMD vs. MISD Comparison

• Similarities:

  • Both are parallel processing architectures using multiple processors.

  • Both may incorporate pipelining.

  • Neither is suited for pure sequential software (such as compilers or office software).

• Differences:

  • SIMD executes 1 instruction across many data streams; MISD executes many instructions on 1 data stream.

  • MISD is more complex than SISD architectures.

3. Massively Parallel Computers

• Involves linking together an extremely large number (thousands) of processors or computers to form a single powerful system.

• All processors work simultaneously on the same problem, with each processor responsible for its assigned part.

• Processors communicate via interconnected data networks or shared memory pools.

Module 5: Boolean Algebra, Logic Circuits & Memory Components

1. Half Adder vs. Full Adder

• Half Adder:

  • Purpose: Adds two single binary bits.

  • Inputs: A, B

  • Outputs: Sum (E), Carry (F)

  • Logic Equations:

    • Sum E = A XOR B [ or A'B + AB' ]

    • Carry F = A AND B [ or A . B ]

• Full Adder:

  • Purpose: Adds two binary bits plus an incoming Carry bit from a previous addition stage.

  • Inputs: A, B, Carry-In (C)

  • Outputs: Sum (Y), Carry-Out (Z)

  • Sum-of-Products (SoP) Expressions:

    • Sum Y = A'B'C + A'BC' + AB'C' + ABC (In word form: NOT A AND NOT B AND C OR NOT A AND B AND NOT C OR A AND NOT B AND NOT C OR A AND B AND C)

    • Carry-Out Z = A'BC + AB'C + ABC' + ABC (In word form: NOT A AND B AND C OR A AND NOT B AND C OR A AND B AND NOT C OR A AND B AND C)

2. SR Flip-Flop

• Purpose: Used to store a single binary digit / bit (1-bit memory).

• Circuit Construction: Constructed using two cross-connected NAND gates or two cross-connected NOR gates.

• Inputs/Outputs: Inputs labeled Set (S) and Reset (R), with outputs Q and NOT Q (Q').

3. Karnaugh Maps (K-Maps)

• Benefit: Makes simplifying logic expressions easier without using complex Boolean algebra; guaranteed to produce an optimal sum-of-products solution.

• Looping Rules: Group adjacent 1s in powers of 2 (1, 2, 4, 8, 16), wrap loops around grid edges, and make groups as large as possible to eliminate redundant variables.

4. Essential Boolean Algebra Laws

• De Morgan's Laws:

  • (A . B)' = A' + B' (NOT (A AND B) = NOT A OR NOT B)

  • (A + B)' = A' . B' (NOT (A OR B) = NOT A AND NOT B)

• Double Negation Law:

  • (A')' = A (NOT (NOT A) = A)

• Absorption Laws:

  • A + (A . B) = A

  • A . (A + B) = A

• Distributive Laws:

  • A . (B + C) = (A . B) + (A . C)

  • A + (B . C) = (A + B) . (A + C)

• Identity & Annulment Laws:

  • A . 1 = A

  • A + 1 = 1

  • A . 0 = 0

  • A + 0 = A

Artificial Intelligence

Artificial Intelligence (AI)

• Definition: A broad field of computer science focused on creating computer systems that simulate intelligent behavior and make decisions autonomously or assist in solving complex problems.

Graph Data Structure in AI

• Graph Definition: An abstract data structure used to model relationships between entities using vertices (nodes) and edges.

• Graph Components:

  • Vertices / Nodes: Represent entities such as locations, states, objects, or people.

  • Edges: Connect pairs of nodes to represent possible paths, links, or relationships between them.

  • Weights / Labels: Values assigned to edges (or nodes) representing cost, distance, time, or penalty associated with traversing that path.

  • Cycle: A sequence of connected nodes that starts and ends at the exact same node.

• Purpose of Graphs in AI:

  • Records relationships between entities in complex domains.

  • Models problems as graph traversal tasks to find optimal routes (e.g., navigation maps).

  • Provides the structural foundation for Artificial Neural Networks (ANNs), where nodes represent artificial neurons and edges represent weighted connections.

2. Graph Search Algorithms

Search algorithms are used in AI to find the optimal, shortest, or most cost-effective path between nodes on a graph based on edge weightings such as distance, time, or cost.

Dijkstra’s Algorithm

• Definition: An unguided search algorithm that finds the shortest path from a starting node to all other nodes in a graph.

• Key Characteristics:

  • Guaranteed Shortest Path: Always finds the absolute shortest path to every node.

  • Exploratory Nature: Systematically checks every vertex and path without guidance toward a specific destination.

  • Constraint: Cannot process graphs with negative edge weights.

• Standard Algorithm Execution Steps:

  1. Initialization: Set the starting node distance to 0 and all other node distances to infinity (\(\infty\)).

  2. Distance Updates: Calculate tentative distances for adjacent unvisited nodes and update them if a shorter path is calculated.

  3. Tracking Visited Nodes: Mark nodes as visited once their shortest distance is finalized.

  4. Iteration: Repeat the process across multiple paths until all target nodes are visited.

A* Algorithm

• Definition: A guided pathfinding algorithm that finds the shortest route between two specific nodes using a heuristic function.

• Heuristic Formula: \[f(n) = g(n) + h(n)\]

  • \(g(n)\): The actual cumulative path cost calculated from the start node to the current node.

  • \(h(n)\): The heuristic cost—an intelligent estimate/guess of the remaining distance/cost from the current node to the destination node.

  • \(f(n)\): The total estimated cost of the path passing through the current node.

• Key Characteristics:

  • Targeted Search: Prioritizes nodes with lower \(f(n)\) values, focusing exploration toward the target destination rather than evaluating all nodes.

  • Negative Edge Weights: Capable of working with negative edge values/weights.

  • Heuristic Reliance: If the heuristic values (\(h\)) are inaccurate, A* may fail to find the absolute shortest path.

Key Differences: Dijkstra vs. A* Algorithm

3. Machine Learning (ML) Paradigms

Machine Learning is a branch of AI involving algorithms and computer programs that automatically improve their performance at tasks through experience and training data without being explicitly programmed.

Supervised Learning

• Definition: A machine learning category where models are trained using labelled training data.

• Mechanism: Input data is paired with known target outputs. The model learns mappings between inputs and outputs to predict future outcomes from past data.

• Human Involvement: Requires initial human input to label data and set expected targets.

Unsupervised Learning

• Definition: A machine learning category where models are trained using unlabelled training data.

• Mechanism: Data is provided without explicit instructions or target outputs. The algorithm autonomously analyses the dataset to discover hidden patterns, structures, similarities, or data clusters.

• Human Involvement: Does not require human intervention or pre-labelled outcomes during training.

Reinforcement Learning

• Definition: A machine learning paradigm where an autonomous agent learns to make optimal decisions in an interactive environment through trial and error.

• Mechanism:

  • The agent performs actions in an environment and observes the results.

  • Positive Feedback / Reward: Granted for performing desirable actions.

  • Negative Feedback / Punishment: Received for bad actions or errors.

  • Node weightings are adjusted dynamically to maximize total accumulated reward without needing labelled dataset training.

Regression Methods in Machine Learning

• Definition: A supervised learning technique used to model mathematical relationships between variables for trend forecasting and prediction.

• Mechanism:

  • Plots a best-fit line or curve mapping how independent variables (causes) influence dependent variables (effects).

  • Employs calculus to compute the error gradient between predicted values and actual dataset points.

  • Goal: Minimizes the total error difference between predicted values and actual outcomes.

4. Artificial Neural Networks (ANNs) & Deep Learning

Artificial Neural Network (ANN)

• Definition: A structural component of AI modeled on the data-processing architecture and functioning of the biological human brain.

• Structural Architecture:

  • Input Layer: Receives raw external input data and feeds it into the network.

  • Hidden Layer(s): Intermediate layers containing interconnected processing nodes (neurons) that extract features, analyze patterns, and perform calculations.

  • Output Layer: Computes and delivers the final decision or classification result.

• Weights and Biases:

  • Numerical weights are assigned to connections between nodes.

  • During training, these weights are continually adjusted based on error feedback to minimize prediction discrepancies and optimize accuracy.

Deep Learning

• Definition: A specialized subfield of machine learning that utilizes Artificial Neural Networks containing multiple hidden layers.

• Role of Multiple Hidden Layers:

  • Allows deep learning networks to extract high-level, complex, non-linear features progressively from raw data.

  • Solves highly complex problems and identifies hidden patterns undetectable by humans.

  • Greater numbers of hidden layers yield higher decision accuracy and performance.

• Strengths:

  • Outperforms traditional ML methods when processing large volumes of unstructured data.

  • Features are learned automatically without requiring manual feature engineering.

• Applications:

  • Virtual assistants / AI agents, chatbots, self-driving vehicles, natural language processing (NLP), facial/image recognition, Large Language Models (LLMs), automated translation, fraud detection, and game-playing AI.

Back Propagation of Errors Method

• Definition: An essential training algorithm used in neural networks to adjust connection weightings iteratively and refine prediction accuracy.

• Sequential Process:

  1. Output Evaluation: The initial predictions generated by the network are compared against the expected/target outputs.

  2. Error Gradient Calculation: Calculus is used to determine the error gradient (the discrepancy between predicted and actual outcomes).

  3. Feedback Transmission: The calculated error values are propagated backward through the network layers.

  4. Weight Adjustment: Connection weights of neurons are adjusted proportionally to reduce the output error.

  5. Iteration: The forward-pass and back-propagation steps repeat until errors reach an acceptably low threshold.