[Concepts] Paper 3


CHAPTER 1: DATA REPRESENTATION

1.1 USER-DEFINED DATA TYPES

1.1.1 Introduction to User-Defined Data Types

Definition: User-defined data types are data types designed by the programmer. When object-oriented programming is not being used, a programmer may choose to utilize user-defined data types for a large program as their use can reduce errors and make the program more understandable.

Why Use User-Defined Data Types:

1.1.2 Non-Composite User-Defined Data Types

Enumerated Data Type: A non-composite user-defined data type that is a list of possible data values. The values defined have an implied order of values to allow comparisons.

<PSEUDOCODE>

TYPE Season = (Summer, Winter, Autumn, Spring)

DECLARE ThisSeason : Season
DECLARE NextSeason : Season

ThisSeason ← Autumn
NextSeason ← ThisSeason + 1 // NextSeason is set to Spring

Characteristics:

Pointer Data Type: Used to reference a memory location. It may be used to construct dynamically varying data structures. The pointer definition has to relate to the type of the variable being pointed to.

<PSEUDOCODE>

TYPE IntegerPointer = ^INTEGER

DECLARE IPointer : IntegerPointer
DECLARE MyInt1 : INTEGER
DECLARE MyInt2 : INTEGER

// Store address of MyInt2 in IPointer
IPointer ← @MyInt2

// Access data at address pointed to by IPointer
IPointer^ ← 33

// Store address of MyInt1 in SecondPointer
SecondPointer ← @MyInt1

Pointer Notation:

1.1.3 Composite User-Defined Data Types

Record Data Type: A data type that contains a fixed number of components that can be of different types. Allows the programmer to collect values with other data types together when these form a coherent whole.

<PSEUDOCODE>

TYPE TEmployeeRecord
DECLARE FirstName : STRING
DECLARE LastName : STRING
DECLARE Salary : REAL
DECLARE Position : STRING
ENDTYPE

DECLARE Employee1 : TEmployeeRecord

Employee1.FirstName ← "John"
Employee1.LastName ← "Doe"
Employee1.Salary ← 2830.80
Employee1.Position ← "Project Manager"

Set Data Type: Allows a program to create sets and to apply mathematical operations defined in set theory. All elements in the set should be unique.

<PSEUDOCODE>

TYPE Days = SET OF STRING
DEFINE Today(Monday, Tuesday, Wednesday, Thursday, Friday) : Days

Operations on Sets:

Class (in OOP): In object-oriented programming, a program defines the classes to be used. Then, for each class, the objects must be defined. A Class includes variables and methods (functions or procedures that an object can run).

1.2 FILE ORGANISATION AND ACCESS

1.2.1 Types of Files

Text Files:

Binary Files:

1.2.2 Methods of File Organisation

Serial Files:

Advantages:

Disadvantages:

File Access: Sequential access only

Uses:

Sequential Files:

File Access Methods:

  1. Sequential Access: Read key field values until required value found
  2. Direct Access: Use index to look up address of record location

Random Files:

Advantages:

1.2.3 Hashing Algorithms

Definition: Takes the key field as input and outputs a value for the record's position relative to the file's start.

Example:

<TEXT>

If key field is numeric: Divide by suitable large number and use remainder
Position = Key MOD FileSize

Handling Collisions: When two different keys produce the same position, use the next available position in the file.

File Access:

1.3 FLOATING-POINT NUMBERS

1.3.1 Floating-Point Representation

Definition: The approximate representation of a real number using binary digits.

Format:

<TEXT>

Number = ±Mantissa × Base^Exponent

1.3.2 Converting Denary to Floating-Point Binary

Steps:

  1. Convert whole number part to binary
  2. Add sign bit (0 for positive, 1 for negative)
  3. Convert fractional part by multiplying by 2 and recording whole parts
  4. Combine parts and adjust exponent
  5. Normalise the number

Example: Converting 8.75 to floating-point (8-bit: 4 for mantissa, 4 for exponent)

<TEXT>

Step 1: Convert whole number
8 = 1000

Step 2: Convert fractional part
0.75 × 2 = 1.5 → 1
0.5 × 2 = 1.0 → 1
0.0 × 2 = 0 → 0
0.75 = 0.11 (binary)

Step 3: Combine
8.75 = 1000.11

Step 4: Normalise
1000.11 = 0.100011 × 2^4

Step 5: Represent
Mantissa: 10001100 (0.100011 with padding)
Exponent: 0100 (4 in 4-bit two's complement)
Sign: 0

Final: 0 10001100 0100
(Sign) (Mantissa) (Exponent)

1.3.3 Normalisation

Purpose:

Process:

1.3.4 Problems with Floating-Point Numbers

  1. Rounding Errors:

    • Binary representation of fractions is often approximate
    • Can become significant after multiple calculations

  2. Overflow:

    • Result too large to represent
    • Occurs when exponent exceeds maximum

  3. Underflow:

    • Result too small to represent
    • May be rounded to zero

  4. Inability to Store Zero:

    • Normalised form requires mantissa to be 0.1 or 1.0
    • Zero must be handled as special case

1.3.5 Precision vs Range

Increase Effect
Mantissa bits Better precision
Exponent bits Larger range

Trade-off: Must balance precision and range based on application needs

CHAPTER 2: COMMUNICATION AND INTERNET TECHNOLOGIES

2.1 PROTOCOLS

2.1.1 Introduction to Protocols

Definition: A protocol is a set of rules governing communication between computers. It ensures the computers that communicate understand each other.

Key Terms:

2.1.2 TCP/IP Protocol Suite

Four Layers:

Layer Purpose
Application Encodes the data being sent
Transport Breaks data into packets, adds port numbers
Network/Internet Adds IP addresses for routing
Link Adds MAC addresses, handles transmission
Physical Converts to signals for transmission

Data Flow - Sender Side:

  1. Application Layer: Encodes data in appropriate format
  2. Transport Layer: Creates packets with port numbers
  3. Network Layer: Adds sender and receiver IP addresses
  4. Link Layer: Formats into frames, adds error checking
  5. Physical Layer: Converts to signals for transmission

Data Flow - Receiver Side: Reverse of sender side, stripping headers at each layer

2.1.3 Key Protocols

Protocol Full Name Purpose
HTTP Hyper Text Transfer Protocol Handles transmission of data to/from websites
HTTPS Hyper Text Transfer Protocol Secure Secure HTTP with encryption
FTP File Transfer Protocol Handles file transmission across networks
SMTP Simple Mail Transfer Protocol Sending emails (push protocol)
POP3 Post Office Protocol 3 Receiving emails (pull protocol)
IMAP Internet Message Access Protocol Advanced email retrieval
BitTorrent - Peer-to-peer file sharing

2.1.4 BitTorrent Protocol

Components:

How It Works:

  1. Peers obtain torrent file (small)
  2. Torrent file points to tracker
  3. Tracker lists all peers in swarm
  4. Peers download chunks from each other
  5. Peers upload chunks to other peers

2.2 CIRCUIT SWITCHING AND PACKET SWITCHING

2.2.1 Circuit Switching

Definition: A method of data transfer where a dedicated communication channel is established before transmission begins.

Characteristics:

Advantages:

Disadvantages:

Example Use:

2.2.2 Packet Switching

Definition: A method of data transfer where the message is broken into parts and sent over optimum routes to reach its destination.

Characteristics:

Advantages:

Disadvantages:

2.2.3 Router Function

Definition: A device that connects two or more computer networks and directs incoming packets to their receiver according to network traffic.

Functions:

2.3 SSL/TLS

2.3.1 SSL and TLS

SSL (Secure Socket Layer):

TLS (Transport Layer Security):

When to Use:

Handshake Process:

  1. Client sends request to server
  2. Server sends digital certificate (includes public key)
  3. Client validates certificate
  4. Client generates session key, encrypts with server's public key
  5. Server decrypts session key
  6. Secure session established

CHAPTER 3: HARDWARE AND VIRTUAL MACHINES

3.1 RISC AND CISC PROCESSORS

3.1.1 RISC (Reduced Instruction Set Computers)

Characteristics:

3.1.2 CISC (Complex Instruction Set Computers)

Characteristics:

3.1.3 Pipelining

Definition: Instruction-level parallelism where the fetch-decode-execute cycle is separated into several stages.

Five Stages:

  1. Instruction Fetch (IF)
  2. Instruction Decode (ID)
  3. Operand Fetch (OF)
  4. Instruction Execution (IE)
  5. Result Write Back (WB)

Advantages:

Disadvantages:

Interrupt Handling in Pipelines:

3.1.4 Parallel Processing Architectures

SISD (Single Instruction Single Data):

SIMD (Single Instruction Multiple Data):

MISD (Multiple Instruction Single Data):

MIMD (Multiple Instruction Multiple Data):

Massively Parallel Computers:

3.2 BOOLEAN ALGEBRA AND LOGIC CIRCUITS

3.2.1 Boolean Algebra Laws

Identity Law:

<TEXT>

A + 0 = A
A · 1 = A

Null Law:

<TEXT>

A + 1 = 1
A · 0 = 0

Idempotent Law:

<TEXT>

A + A = A
A · A = A

Inverse Law:

<TEXT>

A + A' = 1
A · A' = 0

Commutative Law:

<TEXT>

A + B = B + A
A · B = B · A

Associative Law:

<TEXT>

(A + B) + C = A + (B + C)
(A · B) · C = A · (B · C)

Distributive Law:

<TEXT>

A + B·C = (A + B) · (A + C)
A · (B + C) = A·B + A·C

De Morgan's Laws:

<TEXT>

(A + B)' = A' · B'
(A · B)' = A' + B'

3.2.2 Karnaugh Maps (K-Maps)

Purpose: Simplify Boolean expressions and reduce number of gates needed.

Benefits:

Methodology:

  1. Fill K-map from truth table
  2. Group '1's in powers of 2 (1, 2, 4, 8)
  3. Wrap around edges allowed
  4. Within each group, only constant values remain
  5. Write expression from groups

Example K-map (2 variables):

<TEXT>

AB'
0 1
A 0 0 1
1 1 1

3.2.3 Half Adders and Full Adders

Half Adder:

A B Sum Carry
0 0 0 0
0 1 1 0
1 0 1 0
1 1 0 1

Sum = A XOR B Carry = A AND B

Full Adder:

3.2.4 Flip-Flops

SR Flip-Flop:

JK Flip-Flop:

Purpose:

3.3 VIRTUAL MACHINES

3.3.1 Concept of Virtual Machines

Definition: Software that provides an exact copy of hardware. The process interacts with the software interface provided by the OS, which provides this copy. The OS kernel handles interaction with actual host hardware.

Benefits:

Drawbacks:

Examples:

CHAPTER 4: SYSTEM SOFTWARE

4.1 PURPOSES OF AN OPERATING SYSTEM

4.1.1 Resource Optimisation

How OS Maximises Resources:

4.1.2 User Interface

Purpose: Hides complexities of hardware from user. Allows users to interact with application programs without knowing hardware details.

Types:

4.1.3 Process Management

Process: A program being executed which has an associated Process Control Block (PCB) in memory.

Process States:

PCB Contents:

4.1.4 Scheduling Routines

First-Come-First-Served (FCFS):

Round Robin:

Priority-Based:

Shortest Job First:

Shortest Remaining Time:

4.1.5 Memory Management

Paging:

Virtual Memory:

Benefits:

Disk Thrashing:

4.1.6 OS Structure

User Mode:

Kernel/Privileged Mode:

4.2 TRANSLATION SOFTWARE

4.2.1 Compilation Stages

Lexical Analysis:

Syntax Analysis:

Code Generation:

Optimization:

4.2.2 Interpreters vs Compilers

Feature Compiler Interpreter
Translation Entire program before execution Line-by-line
Output .exe file No executable
Execution speed Faster Slower
Error reporting All errors at end Stops at first error
Debugging Difficult Easier

4.2.3 BNF (Backus-Naur Form)

Purpose: Formal mathematical way of defining syntax unambiguously.

Components:

Example:

<TEXT>

<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<integer> ::= <digit> | <integer> <digit>

4.2.4 Reverse Polish Notation (RPN)

Definition: A method of representing expressions without brackets or special punctuation. Uses postfix notation where operator is placed after variables.

Example:

Advantages:

Evaluation:

CHAPTER 5: SECURITY

5.1 ENCRYPTION AND ENCRYPTION PROTOCOLS

5.1.1 Encryption Concepts

Plain Text: Original data before encryption.

Cipher Text: Result of applying encryption algorithm to data.

Encryption: Process of making cipher text from plain text.

Key: Value used by encryption/decryption algorithm.

5.1.2 Symmetric Key Encryption

Definition: Same key used for encryption and decryption.

Process:

  1. Sender and receiver share secret key
  2. Sender encrypts plain text with key → cipher text
  3. Cipher text transmitted
  4. Receiver decrypts with same key → plain text

Advantages:

Disadvantages:

Examples:

5.1.3 Asymmetric Key Encryption

Definition: Different keys for encryption and decryption.

Public Key:

Private Key:

Sending Private Message:

  1. Receiver sends public key to sender
  2. Sender encrypts message with public key
  3. Only receiver (with private key) can decrypt

Sending Verified Message:

  1. Sender encrypts with private key
  2. Anyone can decrypt with public key
  3. Message verified as from sender

5.1.4 Digital Signatures

Process:

  1. Calculate hash of message (digest)
  2. Encrypt digest with sender's private key → digital signature
  3. Send message + signature
  4. Receiver decrypts signature with public key → digest
  5. Receiver calculates hash of message
  6. If digests match → message authentic

5.1.5 Digital Certificates

Purpose: Verify that public key belongs to claimed entity.

Certificate Contents:

Obtaining Certificate:

  1. Entity contacts Certification Authority (CA)
  2. CA confirms entity's identity
  3. CA creates certificate with entity's public key
  4. CA signs certificate with its private key
  5. Entity posts certificate on website

5.1.6 SSL/TLS Protocol

Purpose: Provide secure communication between client and server.

Uses:

Process:

  1. Client connects to server (port 443)
  2. Server sends certificate
  3. Client validates certificate
  4. Client generates session key
  5. Client encrypts session key with server's public key
  6. Server decrypts session key
  7. Secure session begins

5.2 MALWARE AND RESTRICTION METHODS

5.2.1 Types of Malware

Type Description Exploits
Virus Replicates inside executable files Executable files
Worm Runs independently, propagates to networks Shared networks
Spyware Collects and transmits information Background processes
Phishing Emails requesting confidential info User trust
Pharming Bogus website redirects Website appearance

5.2.2 Restriction Methods

Malware Restriction Method
Virus Anti-virus software with daily scans
Worm Firewall protection
Spyware Real-time anti-spyware
Phishing Check sender email address
Pharming Verify website URL

CHAPTER 6: ARTIFICIAL INTELLIGENCE

6.1 INTRODUCTION TO AI

6.1.1 Definition

Artificial Intelligence: The ability of computers to perform tasks that usually only humans would be able to do (decision-making, speech recognition, etc.).

Machine Learning (ML): A subfield of AI where computers learn to perform tasks without being explicitly programmed. Uses historical training data to produce a model for predictions.

Deep Learning (DL): A subset of ML where computers learn using neural networks similar to human brain function.

6.1.2 Types of Machine Learning

Supervised Learning:

Unsupervised Learning:

Reinforcement Learning:

6.1.3 Classification, Regression, and Clustering

Classification:

Regression:

Clustering:

6.2 ARTIFICIAL NEURAL NETWORKS

6.2.1 Structure

Layers:

  1. Input Layer: Accepts inputs in various formats
  2. Hidden Layers: Perform calculations, find patterns
  3. Output Layer: Provides results

Nodes:

6.2.2 Back Propagation

Definition: "Backward propagation of errors" - standard method for training neural networks.

Process:

  1. Input data fed to network
  2. Network generates output
  3. Output compared to expected result
  4. Error calculated
  5. Error propagated backwards through network
  6. Weights adjusted
  7. Process repeated until acceptable error

6.2.3 Graph Theory in AI

Graph Components:

Real-World Uses:

In AI:

6.3 GRAPH SEARCH ALGORITHMS

6.3.1 Dijkstra's Algorithm

Purpose: Find shortest path between nodes in weighted graph.

How It Works:

  1. Start at initial node
  2. Calculate distances to all connected nodes
  3. Select node with smallest distance
  4. Update distances through that node
  5. Repeat until destination reached

Limitations:

6.3.2 A* Algorithm

Purpose: Informed search algorithm using heuristics to find shortest path efficiently.

Formula:

<TEXT>

F = G + H

Advantages over Dijkstra:

CHAPTER 7: COMPUTATIONAL THINKING AND PROBLEM-SOLVING

7.1 RECURSION

7.1.1 Essential Features

Base Case:

Recursive Case:

Unwinding:

7.1.2 Advantages and Disadvantages

Advantages Disadvantages
Simpler, more natural solutions Less efficient (time and space)
Elegant for tree-like problems Stack overflow risk
Reduced code complexity Hard to debug

7.1.3 How Compilers Handle Recursion

Stack Usage:

  1. Before call: Save current state (registers, local variables) onto stack
  2. Make recursive call
  3. During return: Restore state from stack

Unwinding:

7.1.4 Examples

Factorial:

<PYTHON>

def factorial(n):
if n <= 1:
return 1
else:
return n * factorial(n-1)

Fibonacci:

<PYTHON>

def fibonacci(n):
if n <= 1:
return n
else:
return fibonacci(n-1) + fibonacci(n-2)

7.2 ALGORITHM COMPLEXITY

7.2.1 Big O Notation

Notation Name Example
O(1) Constant Array index access
O(log n) Logarithmic Binary search
O(n) Linear Linear search
O(n log n) Linearithmic Merge sort
O(n²) Quadratic Bubble sort

7.2.2 Comparing Algorithms

Time Complexity:

Space Complexity:

CHAPTER 8: FURTHER PROGRAMMING

8.1 PROGRAMMING PARADIGMS

8.1.1 Low-Level Programming

Characteristics:

Addressing Modes:

8.1.2 Imperative (Procedural) Programming

Characteristics:

Examples:

8.1.3 Object-Oriented Programming (OOP)

Key Terms:

Inheritance Example:

<PYTHON>

class Person:
def __init__(self, name, age):
self.name = name
self.age = age
def get_name(self):
return self.name

class Student(Person): # Inherits from Person
def __init__(self, name, age, student_id):
super().__init__(name, age) # Call parent constructor
self.student_id = student_id

8.1.4 Declarative Programming

Characteristics:

Example:

8.2 FILE PROCESSING

8.2.1 File Modes

Mode Purpose
READ Read from file
WRITE Write to file (overwrites)
APPEND Add to end of file
RANDOM Direct access

8.2.2 Serial File Operations

Reading:

<PYTHON>

file = open("data.txt", "r")
while not EOF(file):
line = READFILE(file)
process(line)
CLOSEFILE(file)

Writing:

<PYTHON>

file = open("data.txt", "w")
WRITEFILE(file, "data")
CLOSEFILE(file)

8.2.3 Sequential File Operations

Search:

Add:

Delete:

8.2.4 Random File Operations

Hashing:

<TEXT>

Position = Hash(Key) MOD FileSize

Direct Access:

<PYTHON>

SEEK(file, position)
GETRECORD(file, record)
PUTRECORD(file, record)

8.3 EXCEPTION HANDLING

8.3.1 Exceptions

Definition: Runtime errors that cause program to terminate if not handled.

Common Exceptions:

8.3.2 Handling Exceptions

Try-Except Structure:

<PYTHON>

try:
# Code that might cause error
file = open("data.txt", "r")
data = file.read()
except FileNotFoundError:
print("File not found")
except Exception as e:
print(f"Error: {e}")
finally:
# Always executes
if 'file' in locals():
file.close()

Purpose: