1.

​ Data Representation

13.1 User-defined Data Types

Purpose of user defined data types

●​ To create a new data type

●​ To allow construction of data types not available in a programming language
(extends flexibility of a programming language)
●​ Constructed by the programmer

Composite

●​ Collection of data that consists of multiple elements of different (or the same) data
types which are grouped under a single identifier
●​ Can be user-defined or primitive
●​ Contain more than one data type in their definition
●​ Includes a record, set and class/object

Record

●​ Uses other data types in its definition to form a single new one
●​ Data types referenced can be primitive or user-defined
●​ Includes related items and a fixed number of items

TYPE record_name
DECLARE field_name1 : DATA TYPE
DECLARE field_name2 : DATA TYPE
DECLARE field_name3 : DATA TYPE
ENDTYPE

Set

●​ Includes a list of unordered elements

●​ Theory operations (such as intersection or union) can be applied to its elements
●​ Includes the data type it stores ias part of its definition
●​ All elements are of the same data type

​ TYPE <identifier> = SET OF DATA TYPE

​ DEFINE <set_name> = (value1, value2, value3, …) : <identifier>

 Non-Composite

●​ Can be defined without referencing another data type

●​ Can be a primitive type available in a programming language or a user-defined
type
●​ Contains only one data type in their definition
●​ Includes a pointer and any primitive/enumerated data type
➔​ Enumerated Data Type – has an ordered list of all possible values
➔​ Pointer Data Type – used to reference a memory location, stores
addresses/memory locations and indicates the type of data stored there

(Pseudocode for Non-Composite Data Types)

●​ Enumerated

TYPE <identifier> = (value1, value2, value3, …)

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

●​ Pointer

TYPE <identifier> = ^DATA TYPE

TYPE IntPointer = ^INTEGER

13.2 File Organisation and Access

File Organisation Methods

Serial Files

●​ Records are stored one after the other in chronological order

●​ New records are appended to the end of the file
●​ When searching – every record needs to be checked until the record is found or all
have been checked
●​ Examples include…
➔​ Creating unsorted/temporary transaction files
➔​ Creating data logging files

Sequential Files

●​ Files are stored and addressed one after the other

●​ A new version of the file has to be created to update it
●​ Files are stored with ordered records – records are stored in order of the key field
●​ New records are inserted in the correct position
●​ When searching – the key field is compared and every record is checked until it is
found, or the key field of a current record is greater than the one being searched
for

Random Files

●​ Records are stored in no particular order within the file (there is no sequencing)
●​ There is a relationship between the record key and its location within the file – the
location of the record is found using a hashing algorithm
●​ Updates to the file can be carried out directly

File Access Methods

Sequential Access Process (For Sequential and Serial Files)

●​ Records are checked linearly until the desired record is found/end of file is reached
●​ Starts searching for records one after the other from the physical start of the file
until the record is found or the end of the file is reached
●​ Most suitable when data is stored in a certain order based on a field – e.g. bank
stored data records in ascending order of account number

Direct (For Sequential and Random Files)

●​ Most suitable when a record is referenced by a unique address

●​ Allows a record to be found in a file without other records being read – records are
found by using the key field of the target record (the record’s location is found
using a hashing algorithm)

●​ Sequential Files

➔​ an index of all key fields is kept – the index is searched for the address of
the file location where the target record is stored
●​ Random Files
➔​ a hashing algorithm is used on the key field of the record to calculate
address of the memory location where the target record is expected to be
stored
➔​ Linear probing or Search overflow can be used to find a record if it is not at
the expected location
 Hashing algorithm

●​ Used in direct access methods on random and sequential files

●​ Is a mathematical formula - performs a calculation on the key field of a record
●​ Result of calculation gives the address of the memory location where the record is
located/should be stored

Hash Value Duplicates (a calculated hash value is a duplicate of another value for a
different record key)

Collisions

●​ occurs when two values/data items in the key field for two records result in the
same hash value (when passed through a hashing algorithm)
●​ Means the storage location identified by the algorithm may already be in use by
another record – two records cannot occupy the same address

Process of Collision Resolution

●​ When storing a record

➔​ Linear progression - record is stored is next free memory space after the
one identified by the hashing algorithm
➔​ Record is stored in the next free memory space in the overflow area
●​ When finding a record
➔​ search the overflow area linearly until the matching record key is found (if
not found, record is not in file)

13.3 Floating-point Numbers, Representation and Manipulation

Changing the bit allocation

●​ When the number of bits in the mantissa is raised, the precision/accuracy of the
represented number increases – when the bit number is lowered, the accuracy is
reduced
●​ When the number of bits in the exponent is raised, the range of possible numbers
can be represented is increased – when the bit number is lowered, the range
decreases
Why binary numbers are stored in normalised form

●​ To store a maximum range of numbers in a minimum number of bytes/bits

●​ Normalisation minimises the number of leading 0/1s represented (Numbers whose
mantissa begins with 10 or 01 are normalised)
●​ Maximises the number of significant bits – increases precision/accuracy when
storing very small/large numbers
●​ Avoids the possibility of many numbers having multiple representation

Storing floating point numbers

●​ Large numbers require a greater number of bits for the mantissa

​ Overflow

●​ Occurs following an arithmetic/logical operation – result is too large to be precisely

represented in the available system
●​ Numbers cannot be stored accurately in certain computer systems if they require
more bits than is available

Underflow

●​ Occurs following an arithmetic/logical operation – the result is too small to be

precisely represented in the available system (number does not have enough bits
to be represented)

*always refer to the loss in precision and state the number/digits would be truncated

Why A Binary Number Is Sometimes An Approximation

●​ Real (decimal) numbers can have a fractional part

●​ Binary numbers have limited fractional representation (limited to powers of 2)
●​ Fixed length of storage means you can’t store very large/small numbers – it’s not
possible to store all fractions with the level of precision that is provided
 Converting between denary and floating-point binary

M x 2E where M is the mantissa and E is the exponent

​ Both are always in two’s complement (There is a binary point following the -1 in
the mantissa)

​ Mantissa Representation:

-1 1/2 1/4 1/8 1/16 1/32 1/64 1/128

​ Exponent Representation:

-128 64 32 16 8 4 2 1

●​ Floating-point binary → Denary

1.​ Convert the number in the exponent to denary

2.​ Shift the mantissa binary point to the right by the number held in the
exponent
3.​ Convert to binary, where numbers after the point are ½, ¼, ⅛ and so on…

E.g. 01011010 x 00000100

➔​ 00000100 = 4
➔​ 0.1011010 - point shifts 4 places right
➔​ 01011.010 = 1 + 2 + 8 + ¼ = 11.25

●​ Denary → Floating-point binary

​ 1. Convert the number into binary, separating fractions using a binary point
​ 2. Move the binary point left until only one digit comes before it, counting the
amount of places the point moves up (gives you the exponent)

Eg. 4.75

➔​ 4.5 = 4 + ½ + ¼ = 0100.11
➔​ 0100.11 → 0.10011 - point is shifted 3 places left, hence the exponent is 3
➔​ 3 = 0011, so the final number is 010011 x 0011
2.​ Communication and Internet Technologies

14.1 Protocols

Purpose of Protocols

●​ Provide a standard set of rules to enable successful data transfer

●​ Enables communication/compatibility between devices from different
manufacturers or platforms
➔​ makes communications independent of software and hardware
●​ If two devices with different protocols were sending messages between each
other, they would not be able communicate properly

Purpose of SSL and TSL protocols

●​ Provide communications security over the internet/network (by providing

encryption)
●​ Enable two parties to identify and authenticate each other – allows them to
communicate with confidentiality and integrity

Protocol Suites

●​ The protocols in a stack determine the interconnectivity rules for a layered network
model such as the TCP/IP model

TCP/IP Protocol Suite

●​ Maintains connection between two hosts and ensures successful delivery

between them
●​ During data transfer, the self-contained modules (layers) are applied in order
using the device’s software
●​ Separate layers make hardware and software compatibility easier to implement
●​ Can be represented as a stack, with each layer having a separate functionality

Application
Transport
Internet
Link
 1. Application Layer (Protocols Used)

●​ HTTPS – for sending/receiving/transfer of web pages and hypertext documents

●​ FTP – for sending and receiving files over a network/between devices (used to
transfer data from server to client on the network)
●​ SMTP – push protocol for sending/uploading emails
●​ POP3 or IMAP – pull protocols for retrieving/receiving emails
➔​ Keeps the server and client in sync by not deleting the original email
●​ BitTorrent – provides peer-to-peer file sharing over a network
➔​ Allows sharing of files between many users connected together over the
internet
➔​ Allows more users to share files than a normal peer-to-peer network
would
➔​ Users share files directly with each other – there is no web server (all users
are of equal status)

Purpose of Application Layer

●​ Provides access to all programs that exchange data - interacts directly with the
user
●​ Used by web browsers or server software
●​ Enables data transfer to/from the Transport Layer - allows applications to access
services in other TCP/IP layers
●​ Defines the protocols that an application uses to allow the exchange of data

2. Transport Layer – handles packets

●​ Responsible for delivery of data from source host to destination host

●​ Breaks data into manageable packets (performs segmentation) and sends them to
the internet layer
●​ Adds a packet header and the sequence number to the header (sequences packets)
●​ Controls flow of packets
●​ Handles packet loss/corruption – ensures data arrives error free

3. Internet Layer – handles transmission of packets

●​ Identifies the intended network and host

●​ Transmits packets to the Data Link
●​ Routes packets independently – through optimum route
●​ Addresses packets with their source and destination IP addresses
●​ Uses an IP address and port number to form a socket
4. Link Layer (Network Access Interface) – Handles how data is physically sent

●​ Ensures the correct network protocols are followed

●​ Enables the upper layers to access the physical medium (allows communication
with the network layer)
●​ Responsible for transporting data within the network – formats data into frames
for transmission
●​ Maps IP addresses to MAC addresses

TCP/IP Layer Interactions

●​ Each layer can only accept input from adjacent layer (next higher or next lower
layer)
●​ There is an interface between the adjacent layers which the only interaction
between them
●​ Interactions are carried out by installed software
●​ User interaction takes place at the application layer of stack through protocols
●​ Direct access to hardware takes place at the Link layer of the stack
14.2 Circuit Switching, Packet Switching

Circuit Switching

●​ Data is transferred using a dedicated circuit/channel and implemented at the

physical layer
●​ Circuit is established before transmission starts
●​ Circuit lasts for for entire duration of transmission and closes after it ends
●​ Data is transferred using the whole bandwidth
●​ All data is transferred over the same route
●​ Transmission is generally bidirectional

Use

●​ When a dedicated path needs to be sustained throughout a call

●​ Where the whole bandwidth is required or real time communication is used
●​ E.g. standard voice communications, video streaming, private data networks
●​ Suitable for long continuous communication

Advantages

●​ No need to reassemble data - frames arrive in same order in which they are sent
●​ Entire bandwidth is available
●​ Simpler and fast method of data transfer – data is transmitted with a fixed data
rate and follows the same path (means no data is lost or disordered)
●​ Fast data transfer rate - suitable for real time transmission

Disadvantages

●​ No other transmission can occur when circuit is in use - wasted bandwidth (cannot
be shared)
●​ Not very secure - can be intercepted more easily as all data travels along same
route
●​ Significant cost and time required to establish dedicated connection between
stations
●​ Only one route is available - if an error occurs, transmission ends
●​ Can take time to set up circuit before start of transmission
●​ Circuit is always there, even it is not being used
Packet Switching

●​ Implemented at the network layer

Use

●​ On digital data networks such as the internet – for sending large files that don’t
need to be live streamed
●​ When it is necessary to overcome faulty lines through rerouting
●​ For secure communication and high volume data transmission
●​ When the entire bandwidth isn’t required
●​ E.g. emails, text messages, documents etc.

Transferring Messages Across Internet

●​ Data/message to be transmitted is divided into equal-sized packets (consist of a

header, payload and trailer)
●​ A packet header is attached to each packet containing key information
(source/destination IP addresses, packet number etc.)
●​ Each packet is dispatched independently and given its own route - the routing for a
packet depends on the network traffic
●​ Routes are determined using a routing table - optimum route is always taken
●​ Packets usually arrive out of order - are reassembled in the correct order at
destination (using sequence number in header)
●​ If packets are missing/corrupted a resend request is sent

Advantages

●​ Packets are more likely to arrive as they can be rerouted or retransmitted if an

error occurs
●​ Bandwidth can be shared - packets from multiple messages can share paths
●​ Secure - packets travel via different routes
●​ High data transmission rate is possible

Disadvantages

●​ Time delay occurs - packets need to be reassembled at destination, channel

bandwidth has to be shared with other packets, packets might need to be re-sent
●​ Requires a complex algorithm to function
●​ Needs lots of RAM to handle large amounts of data
 Function of a Router in Packet Switching

●​ Router examines the packet’s header – reads the IP address of destination

●​ Has access to a routing table – contains info about the netmask/gateway used,
available hops and the status of the routes along route
●​ It decides on the next hop/best route and sends the packet on its next hop

Benefits

●​ Accuracy – Ensures accurate delivery of message

●​ Completeness – Missing packets can be easily detected and a resend request sent
to message arrives complete
●​ Router can detect changes in networks and send data another way, ensuring it
arrives
●​ Allows simultaneous use of channel by multiple users
●​ Better security – packets are hashed and send by different routes

Drawbacks

●​ Time delays – due to correcting potential errors in packets caused by network

problems
●​ Requires complex protocols for delivery
●​ Unsuitable for real time transmission applications
3.​ Hardware and Virtual Machines

15.1 Processors, Parallel Processing and Virtual Machines

RISC (Reduced Instruction Set Computers)

●​ Uses few instruction sets & addressing modes

●​ Uses fixed length, single-clock cycle instructions
●​ Instructions only require one clock cycle (single-cycle)
●​ Uses many general purpose registers and a hard-wired CPU
●​ Makes use of pipelining – executes instructions in parallel, where the output of one
instruction is the input of the next
●​ Makes extensive use of RAM
●​ Design emphasis is on software

Pipelining

●​ Allows several instructions to be processed simultaneously – used to increase

instruction throughput during FE cycle

Process ​

●​ Instructions are divided into subtasks

➔​ Instruction fetch
➔​ Instruction decode
➔​ Operand fetch
➔​ Opcode/Instruction execute
➔​ Result store
●​ Each subtask (instruction stage) is completed during one clock cycle
●​ No two instructions can execute their same stage at the same clock cycle
●​ The second instruction begins in the second clock cycle, while the first instruction
has moved on to its second subtask etc. – while one instruction is being executed,
the next one can be fetched and so on…

CISC (Complex Instruction Set Computers)

●​ Uses many instruction formats and has a large instruction set

●​ Uses variable length, multi-clock cycle instructions
●​ Makes use of many different addressing modes
●​ Uses few registers and a programmable CPU
●​ Design emphasis is on hardware – requires complex circuits
●​ Makes frequent use of cache memory
Interrupt Handling (In both RISC and CISC)

1.​ The processor detects an interrupt at the start/end of the FE cycle

2.​ The current program is temporarily stopped and the status/contents of each
register are stored on a stack
3.​ The appropriate ISR routine is called and executed
4.​ After the interrupt has been serviced the registers are restored to their original
status (data is restored from the stack)

Effect of Pipelining (only in RISC)

●​ Adds additional complexity – there could be a number of instructions still in the

pipelining when interrupt is received
●​ All currently operating instructions are discarded except for the last one – the
interrupt handling routine is applied to the remaining instruction
●​ Once interrupt has been serviced the processor can restart with the next
instruction in the sequence

Computer Architecture

SISD – single instruction, single data

●​ One processor executes a single instruction using the same data set – data is
taken from a single source and only a single instruction is performed on it

SIMD – single instruction, multiple data

●​ Processors execute the same instruction on multiple different data sets

simultaneously
●​ Instructions can be performed sequentially (Pipelining)
●​ Parallel computers with multiple processors

MISD – multiple instructions, single data

●​ Performs different instructions/operations on the same set of data

●​ Each processor works on the same data set independently
●​ Parallel computers with multiple processors

MIMD – multiple instructions, multiple data

●​ Consists of many processors that operate asynchronously/independently

●​ Any processor can execute different instructions on different data sets
Massively Parallel Computers

●​ kind of network infrastructure

●​ a large number of computer processors or separate computers connected together
– simultaneously performing a set of coordinated computations
●​ communicate using a message interface (send messages between each other)

Virtual Machines

●​ Are an emulation of a computer system (and hardware/software) using a host

computer system
●​ Uses guest operating system for emulation

Benefits

●​ cost saving – new system can be tried on different virtual hardware without the
need to purchase the hardware
●​ different instruction set architectures can be emulated on a single computer
●​ the system can crash without affecting the host machine – virtual machine
provides protection to other software
●​ security – if a virus is downloaded on the emulated system, it only affects the VM
●​ more than one new computer system can be emulated – allows multiple new
systems to co-exist on a single computer (multiple VMs can be used on the same
computer)
●​ allows emulation of programs for new CS that are not compatible with the host
operating system – through the use of a guest operating system
●​ can emulate old software on a newer system using a compatible guest OS

Limitations

●​ cannot emulate some hardware – new hardware might have been developed after
the VM was
●​ using the machine means extra code has to be executed and more load is put on
the host computer – is less efficient, increases processing time, uses more RAM
(hence has poorer performance)
●​ increases the maintenance expenses as both host system and the virtual machine
must be maintained (is also more complex to manage & implement)
●​ VM may be affected by weaknesses of the host machine
 Roles of Host Operating System

●​ Is the normal OS used by the host machine

●​ Has control of all the resources of the host machine/computer (and can access all
the physical resources)
●​ Provides a user interface to operate the virtual machine software
●​ Runs the virtual machine software

Roles of Guest Operating System

●​ OS that runs within the virtual machine

●​ Controls the virtual hardware/software during the emulation – accesses actual
hardware through the virtual machine and host OS
●​ Provides a user interface for the emulated hardware/software
●​ Runs under the control of the host OS

15.2 Boolean Algebra and Logic Circuits

Combination Circuits – output depends entirely on the input values

Half-Adder Logic Circuit

●​ Used to perform binary addition

●​ Outputs a sum bit and a carry bit

INPUT OUTPUT

X Y sum carry
0 0 0 0
0 1 1 0
1 0 1 0
1 1 0 1

●​ Consists of a XOR and AND gate – XOR outputs sum, AND outputs carry
 Full-Adder Logic Circuit

●​ Two half-adders combined

●​ Has 3 inputs (X, Y and Cin) and 2 outputs (S and Cout)

INPUT OUTPUT

X Y Cin sum Cout

0 0 0 0 0

0 0 1 1 0

0 1 0 1 0

0 1 1 0 1

1 0 0 1 0

1 0 1 0 1

1 1 0 0 1

1 1 1 1 1

●​ Two half-adder circuits whose outputs are joined through an OR gate

Sequential Circuits – the output depends on the input value produced from a
previous output value

SR Flip-Flop

●​ stores a single bit of data – 0 or 1

●​ used in memory to create storage cells within RAM – each flip-flop stores a data
bit (memory is made up of many SR flip-flops)

​ Problems of SR Flip-Flops

●​ potential for circuit to arrive in an uncertain state

●​ circuit can become unstable if inputs do not arrive simultaneously
●​ Consists of 2 inputs & outputs
➔​ “SET” labelled S
➔​ “RESET” labelled R
➔​ ‘Q’ and ‘NOT Q’ as outputs

●​ Made up of 2 cross-coupled NOR or NAND gates

1. Using NOR Gates

​ ​ ​ ​ ​ ​ ​ If both S and R = 1, an invalid condition

occurs as Q and NOT Q will be equal.

(both SET and RESET cannot be done at once)

Any other combination is valid. If both

S and R = 0, there is no change.

​ * when assigning values, S and NOT Q will be the same, and R and Q will be the
same (aim is to get the gate inputs to be either 00 or 11)

INPUT OUTPUT

S R Q NOT Q

1 0 0 1

0 1 1 0
 2. Using NAND Gates

If both S and R = 0, an invalid condition

occurs as Q and NOT Q will be equal.

(both SET and RESET cannot be done at once)

Any other combination is valid. If both

S and R = 1, there is no change.

​ * when assigning values, the same applies; S and NOT Q will be equal, R and Q
will be equal

​ (truth table is the same, only difference is when no change or invalid state occurs)

JK Flip-Flops

●​ improved version of SR flip-flops – eliminates invalid input combinations

●​ used to produce shift registers in a computer or a simple binary counter\

Advantages

●​ validates all input combinations

●​ avoidance of unstable states and increased stability

●​ Uses a clock pulse as an input (to synchronise inputs) and adds additional gates

When J and K = 0, there is

no change to Q.

When J and K = 1, the value of

Q toggles after each clock pulse.

(flip-flop changes between SET and RESET state)

* the output value of Q will always be equal to J, NOT Q will be equal to K

Boolean Algebra

●​ form of algebra linked to logic gates

●​ based on TRUE and FALSE statements

​ Boolean Notation​

Logic Gate Notation

AND A.B

OR A+B

NOT

NAND

NOR

De Morgan’s Laws

​
Karnaugh Maps

●​ method of obtaining a simplified boolean algebra expression from a truth table

​ Advantages

●​ minimises number of boolean expressions

●​ minimises number of logic gates – provides a more efficient circuit

Rules of Simplification

●​ works by grouping together ​adjacent cells containing 1s

➔​ groups cannot be diagonal – they can wrap around

➔​ only 2n cells in each group (e.g. only 2/4/8… 1s allowed in one group)
➔​ each 1 must be in at least one group – overlapping of groups is allowed
➔​ groups should be as large as possible
➔​ there should be the fewest amount of groups possible

Example 1:

Example 1:
 4.​ System Software

16.1 Purpose of an Operating System

Maximising Use of Resources

●​ implements process scheduling – increases efficiency of CPU

●​ manages main memory
●​ optimises input/output operations – direct memory access (DMA) allows
hardware to access main memory independently of the CPU, meaning the CPU is
not utilised and free to carry out other tasks during data transfer

User Interface

●​ hides the complexities of the computer/hardware/operating system from the user

●​ provides appropriate access systems for users with differing needs
●​ avoids complex commands involving memory locations or computer hardware
●​ e.g. a graphical user interface uses icons for navigation

Process Management

Multi-tasking

●​ Allows computers to (appear to) carry out more than one process at a time

​ Implementation

●​ Processor time, hardware and resources are shared between tasks

●​ Scheduling is used to decide which process is carried out next - endures
multi-tasking operates efficiently
●​ One task of a higher priority can interrupt another currently running task

Interrupt Handling

●​ transferring control to another routine when a service is required

Process States

●​ Ready – program is waiting to run on the CPU for allocated amount of time
●​ Running – program is currently running/being executed on the CPU
●​ Blocked – program execution is halted, waiting for an event to occur
 Process Changes

●​ Running → Ready
➔​ The time slice of the running process expires
➔​ There is a process with a higher priority in the ready queue (the running
process gets preempted)
➔​ An interrupt arrives at the CPU – the process running on the CPU gets
preempted
●​ Ready → Running
➔​ Process is selected by CPU to be executed – the OS scheduler has
allocated this given time to the process
●​ Running → Blocked
➔​ Process needs to carry out an input/output operation or wait for a
resource to be available
➔​ Process cannot proceed with execution before a specified event takes
place
●​ Blocked → Ready
➔​ Event or input/output operation has occurred, program can resume

Scheduling – managing the processes running on the CPU

●​ Allows more than one task to appear to be executed at the same time (enables
multi-tasking)
●​ Allows high priority jobs to be completed first
●​ Keeps the CPU busy at all times – this ensures all processes execute efficiently
and reduces wait times for all processes

Scheduling Routines

Shortest Job First

●​ Short processes are executed first and followed by longer processes (executed in
ascending order of CPU time required)
●​ Leads to an increased throughput – as more processes can be executes in a smaller
amount of time

Round Robin

●​ Each process is served by the CPU for a fixed time

●​ Starvation doesn’t occur – as each process is given a fixed time to be executed
every round robin cycle
 First Come First Served

●​ No complex logic – each process is executed one by one

●​ Received processes are queued
●​ Starvation doesn’t occur – every process will eventually get a chance to run

Shortest Remaining Time

●​ Processes are placed in queue (consists of a ready and blocked queue)

●​ If a process with a shorter execution/burst time is queued, the process currently
in line is preempted and the shorter process runs first
●​ Processes will run until executed or a process with a shorter execution time is
added
●​ Starvation may occur – if processes with a shorter burst time keep queuing, then
the longer processes may never run

How the OS Kernel acts as an Interrupt Handler

●​ Receives a signal when an interrupt is generated

●​ Checks priority of interrupt and reviews status of current interrupts
●​ Consults the interrupt dispatch table (IDT) - saves the contents of the registers on
the kernel stack
●​ Restored the register contents once the interrupt is serviced

Virtual Memory

●​ is created temporarily
●​ secondary storage is used to simulate additional main memory
●​ extends RAM – means the CPU appears to be able to access more memory space
than the actual RAM available
●​ only data in use needs to be in main memory – data can be swapped between
RAM and virtual memory as necessary

Reasons for Use

●​ when RAM is running low – e.g. when a computer is running many processes at
once
●​ for more efficient use of RAM – if programs are not immediately needed, they can
be moved from RAM to virtual memory
Paging – reading/writing blocks of data from/to secondary storage when required

●​ memory is divided into fixed size blocks

●​ dividing of memory into pages done by the operating system
●​ faster access times than segmentation

Segmentation

●​ In segmented memory, the virtual address space is broken into varying sized
blocks (sections) - segment size is calculated by the compiler
●​ Each segment has a name, size and is numbered - its number is used as an index in
the segment map table
●​ During execution segments from virtual memory are loaded into physical memory
●​ Address is specified by the user - contains the segment name and offset value
●​ An offset value determines the size of the segment
●​ Segment map table maps virtual addresses to physical addresses (contains
segment number and offset value)
●​ Slower access times than paging

Page Replacement

●​ ‘Page Fault’ – an interrupt raised by hardware that occurs when a requested page
is not yet loaded into main memory
●​ The OS replaces an existing page with a new one – done by swapping pages
between secondary and main/primary memory

FIFO Algorithm (First In, First Out)

●​ OS keeps track of all pages in memory using a queue structure

●​ The oldest page is at the front of the queue and is the first to be removed when a
new page is added
●​ Page usage is not considered during replacement
●​ Suffers from Belady’s Anomaly – more page faults with an increasing number of
page frames

LRU Algorithm (Last Recently Used Replacement)

●​ Replaces the page which has not been used for the longest time
●​ Implemented using a linked list consisting of all pages in memory – most
recently used page is at the front, least recently used at the back
​ Clock Page Replacement

●​ Uses a circular queue structure – has one single pointer that acts as a head and
tail
●​ Has an R-flag which can be 0 or 1
➔​ If R=0 – the page being pointed to is removed and a new page is inserted
into its place , else a new page is inspected
➔​ If R=1 – the next/following page is inspected, the pointer moving until a
page where R=0 if found

Disk Thrashing

●​ Problem that occurs when virtual memory is being used (due to frequent transfers
between virtual and physical memory)
➔​ As main memory fills up, more pages need to be swapped between virtual
and physical memory
➔​ This swapping leads to a very high rate of hard disk access - results in
excessive head movements
➔​ Latency increases as hard disk head movements take a relatively long time
➔​ Eventually, more time is spent swapping the pages/data than processing it -
program may freeze or not run

16.2 Translation Software

Interpreter

●​ examines source code one statement at a time

●​ checks each statement for errors
➔​ …if no error is found, the statement is executed
➔​ …if an error is found, it is reported and the interpreter halts
●​ interpretation is repeated for every iteration in loops
●​ interpretation has to be repeated every time the program is run

Compilation Stages

Lexical Analysis
●​ converting a sequence of characters into a sequence of tokens

Syntax Analysis

●​ uses parsing algorithms to interpret the meaning of a sequence of tokens

●​ checks code matches the grammar of the language
 ●​ syntax errors are reported
●​ a parse tree is produced

Code generation
●​ converting an intermediate representation of source code into an executable form

Optimisation
●​ minimising a program’s execution time and memory requirement

Backus-Naur Form Notation

●​ Is a formal method of defining the grammatical rules of a programming language

​ <variable_name> ::= option1 | option2 | option3 … ;

➔​ <> is used to enclose an item

➔​ ::= is basically a = or ←, assigning options to a variable
➔​ | means OR – allows a variable to have multiple choices

​ Example
●​ To define a hexadecimal number, the following definitions can be made:
​ <digit> ::= 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0 ;
​ <letter> ::= A | B | C | D | E | F ;
​ <hexnum> ::= <digit> | <letter> | <hexnum> <digit> | <hexnum> <letter>

➔​ This states that only digits between 0-9 and letters from A-F are valid
➔​ Many BNF definitions are recursive, allowing the hexadecimal number to
have multiple digits and letters

Reverse Polish Notation

●​ Used to carry out evaluation of expressions

➔​ Provides an unambiguous method of representing an expression
➔​ Reads from left to right
➔​ Doesn’t require brackets or rules of precedence (BODMAS)

Data Structures used to evaluate in RPN

●​ Stack – operands are popped from stack in reverse order to how they were pushed
●​ Binary Tree – allows both infix and postfix to be evaluated (tree traversal)
​ Infix vs Postfix

●​ Infix refers to regular algebraic equations e.g. 3 + 4 evaluates to 7

●​ Postfix is used in RPN e.g. 3 4 + evaluates to 7
➔​ When writing postfix notation, the operator comes after the two numbers it
is being performed on (2 4 * → 8 and 15 3 / → 5)
➔​ Brackets are not used – 5 3 + 7 2 - * evaluates to (5 + 3) * (7 - 2)
➔​ Numbers are grouped with the operator to their right – 8 - 2 3 * is 8 - 2*3

RPN evaluation using stacks

●​ Expression is read from left to right, one item at a time

●​ Each element is checked to see whether it is an operator or a value
●​ Values are pushed onto a stack until an operator is found
●​ Operator is then applied to the last two values on the stack
●​ Result is pushed back onto the stack
●​ Process repeats until only one value remains (the result)

​ Eg. a b * 2 / c d / * (where a = 20, b = 3, c = 10 and d = 5)

3 2 10 10 2

20 20 60 60 30 30 30 30 60
5.​ Security

17.1 Encryption, Encryption Protocols and Digital Certificates

Key Cryptography

●​ Ensures a message is authentic/from a trusted source

●​ Ensures message has not been altered during transmission
●​ Makes sure only intended receiver is able to understand a message
●​ Non-repudiation – neither sender or receiver can deny the transmission happened

Asymmetric Encryption

●​ Provides better security – by using a pair of different keys

●​ One of the keys is used to encrypt the message, the matching one is used to
decrypt it
●​ Only the public key is available to everyone, the private key is kept secret
●​ Is a longer process, as it is more complex
●​ Length of keys is longer (usually 2048 bits)

Process

●​ The receiver’s computer uses an algorithm to generate a matching pair of keys

(public and private)
●​ The public key is sent to the sender’s computer
●​ The sender encrypts the document/file/data using the public key to create cipher
text
●​ The sender’s computer sends the cipher text to the receiver’s computer – can only
be decrypted using the receiver's private key

Detecting Alterations

●​ The message, together with the digital signature, is decrypted using the receiver’s
private key
●​ The digital signature received is decrypted with the sender’s public key to recover
the digest sent
●​ The decrypted message received is hashed with the agreed hashing algorithm to
reproduce the message digest received
●​ The two digests (received and reproduced) are compared – if they are the same,
then the message has not been altered
Symmetric Encryption

●​ Uses a single key which is used/shared by all to encrypt and decrypt messages
●​ Simple process that can be carried out quickly - risk of compromise is higher
●​ Length of keys is shorter (usually 128/256 bits)

Quantum Cryptography

●​ Protects security of data transmitted over fibre optic cable

●​ Is a virtually unhackable encryption system

Benefits

●​ Detects any eavesdropping (due to change in photon properties)

●​ Once transferred, the integrity of the key can be guaranteed – it cannot be copied
or decrypted later
●​ More secure, longer keys can be used

Limitations

●​ Limited range – works only over relatively short distances

●​ Requires a dedicated fibre-optic line and specialist hardware – is expensive
●​ Polarisation of light may be altered during transmission through fibre-optic cable
●​ Lacks many vital features and has high error rates (still new and being developed)
– e.g. digital signatures, certified mail etc.

Private Key

●​ An unpublished/secret key that is never transmitted anywhere

●​ Has a matching public key
●​ Is used to decrypt data that was encrypted with its matching public key

Purpose and Example Situations of SSL/TLS

Secure Socket Layer

●​ Encrypts data being transferred over the internet – decides on which encryption
algorithms are to be used
●​ Performs data integrity checks and data compression

Transport Layer Security

●​ Provides encryption, authentication and data integrity in a more effective way
than SSL
●​ Ensures privacy and security of data between devices communicating over the
internet – provides third-party eavesdropping
 Examples of where SSL/TLS would be used

●​ Online banking and online financial transactions

●​ Sending and receiving emails, sending software to a restricted list of users
●​ Using cloud storage facilities or a VPN

SSL/TLS use when Client-Server Communication is Initiated

●​ A SSL/TLS connection is initiated by an application which becomes the client

●​ The application which receives the connection becomes the server
●​ Every new session begins with a handshake
●​ A digital certificate is requested/sent from the client/server
●​ The client verifies the server’s digital certificate and obtains the server’s public key
●​ The encryption algorithms are agreed upon by the server and client – the
symmetric session keys are then generated

Digital Certification

Digital Signatures

●​ An enquiry is made to Certificate Authority (CA)

●​ The enquirer sends their public key and all required information (e.g. to prove
identity) to CA
●​ The enquirer’s details are checked by the CA – If details are verified then the public
key is agreed upon
●​ The CA creates/issues a certificate that includes the enquirer’s public key
●​ Encrypting data is sent to the CA using their public key and sent by the CA using
their private key

How it’s produced before a message is sent

●​ Message is hashed using the agreed hashing algorithm to produce a digest

●​ The message digest is then encrypted with the sender’s private key to form the
signature

Digital Certificate

●​ An electronic/online document used to authenticate the identity of a

website/individual/organisation
●​ Typically issued by the CA
●​ Contains information for identifying an individual/website owner and a public key
●​ Provides the public key which can be used to validate the private key associated
with the signature
6.​ Artificial Intelligence (AI)

18.1 Artificial Intelligence

How graphs aid AI

●​ Artificial Neural Networks can be represented using graphs

●​ Graphs provide structures for relationships
●​ AI problems can be defined as finding a path in a graph
●​ Graphs may be analysed by a range of algorithms e.g. Dijksta’s algorithm

Purpose of A* and Dijkstra’s Algorithms

●​ To find the optimal shortest and most cost-effective route between two nodes
based on distance/cost/time

Artificial Neural Network

●​ Part of AI that is meant to simulate the function of a human brain

●​ Key component of machine learning
●​ Have self-learning capabilities – enables production of better results as more data
becomes available
●​ Can solve complex problems humans cannot/find it difficult to

Artificial Neural Networks

Multiple Hidden Layers in an Artificial Neural Network

●​ Enables deep learning to take place

●​ Needed when the problem you are trying to solve has a higher level of complexity
(requires more layers to solve)
●​ Enables the neural network to learn and make decisions on its own
●​ Improve accuracy of results – more hidden layers means more complex learning
capabilities

How Artificial Neural Networks Enable Machine Learning

●​ They are intended to replicate the way human brains work

●​ Weights/values are assigned between nodes – adjusted through training to give
more accurate results
●​ The output layer provides the results
●​ Data is input at the input layer and is passed into the system
 ➔​ it is then analysed at each subsequent (hidden) layer where characteristics
are extracted/outputs are calculated
➔​ reinforcement learning takes place through repeating the training/learning
process
●​ Decisions can be made without being specifically programmed
●​ The deep learning net will have created complex feature detectors
●​ Back propagation (of errors) will be used to correct any errors that have been
made.

Deep Learning

●​ simulates data processing abilities of the human brain to make decisions

●​ uses artificial neural networks which are modelled after the human brain –
structures algorithms in layers – an input layer, output layer and many hidden
layers
●​ uses large number of hidden layers to progressively extract higher level features
from the raw input (has more success)
●​ is a specialised form of machine learning
●​ trained using large amounts of unlabeled data

Reasons For Use

●​ makes good use of unstructured data

●​ outperforms other methods of machine learning if the data size is large
●​ enables machines to process data with a nonlinear approach
●​ is effective at identifying hidden patterns (ones that are too complex for humans to
spot/are undetectable)
●​ can provide more accurate outcome with higher numbers of hidden layers

Reinforcement Learning

●​ based on feedback – AI learns in an interactive environment through actions and

seeing the results of each action (works through trial and error, learns through its
own experiences)
●​ for each good action, the AI gets positive feedback, for each bad one it receives
negative feedback
●​ Node weightings are adjusted to achieve correct outcome – the AI uses feedback to
improve its performance in similar tasks

Reasons for Use

●​ enables autonomous learning using feedback without any labelled data

Machine Learning

Supervised Learning

●​ allows data to be collected/a data output to be produced from a previous

experience
●​ a known input and associated outputs are given – uses sample data with known
outputs (labelled input data)
●​ able to predict future outcomes based on past data

Unsupervised Learning

●​ helps all kinds of unknown patterns in data to be found – enables learning by

allowing the process to discover previously undetected patterns on its
●​ only requires input data to be given
●​ uses any data – not trained using a right output (uses unlabeled input data)
7.​ Computational Thinking and Problem-solving

19.1 Algorithms

Binary Search

●​ Necessary condition – the elements in the list being searching must be

ordered/sorted in ascending/descending order
●​ The time to search a list increases with an increasing number of items in the list
●​ Starts in the middle of the array/list
●​ Works by finding the mid-point of an array/list and determines which side contains
the item to be found – it discards the half of the array/list not containing the search
item

Process

●​ Find middle index/item

●​ Check the value of the middle index in the list
●​ The item searched for has been found if the index value is equal to it
●​ Otherwise, discard half the list that does not contain the searched item
●​ Repeat the previous steps until the item searched for is found, or there is only one
index left in the list and it is not the item searched for

Linear Search

●​ sequentially checks each element of the array/list until the matching element is
found, or the end of the array/list is reached.
●​ does not require the elements to be sorted.
●​ will usually do more comparisons of records/iterations against the target (before
finding it) than a binary search
●​ starts at the beginning of the array/list.

​ Binary VS. Linear Searches

●​ time to search increases linearly in relation to the number of items in the list for a
linear search and logarithmically for a Binary search
●​ time to search increases less rapidly for a binary search and time to search
increases more rapidly for a linear search
Big O Notation

●​ is used to indicate the time/space complexity of an algorithm.

●​ Linear search → O(n)
●​ Binary search → O(log 2n) / O(Log n)

●​ O(log n) is a time complexity that uses logarithmic time – the time taken goes up
linearly as the number of items rises exponentially

Performance of a sorting algorithm is affected by…

●​ Initial order of data

●​ Number of data items to be sorted
●​ The efficiency of the sorting algorithm

Queue

●​ Uses FIFO data structure – data is removed in the order it is received

●​ Is of varying length
●​ Data is ‘enqueued’ and ‘dequeued’ at different ends
●​ Has two movable pointers

Stack

●​ Uses FILO data structure – data is removed in the reverse order to which is it
received
●​ Is of varying length
●​ Data is popped and pushed onto/off a stack from the same end
●​ Has one movable pointer

Uses of a Stack

●​ Recursion
●​ Implementation of ADTs
●​ Procedure calls
●​ Interrupt handling
●​ Evaluating an RPN expression

Linked List Implementation

●​ Is a dynamic data structure (not restricted in size)

●​ Has freedom to expand or contract – by adding/removing nodes as necessary
●​ Allows more efficient editing using pointers than an array
 Array Implementation

●​ Is a static data structure, generally fixed in size

●​ When array is full, stack cannot be extended any further

19.2 Recursion

Recursion

●​ A process using a function/procedure that calls itself

●​ Must have a base case (stopping condition)
●​ Must have a general case – which calls itself recursively, changes its state and
moves towards the base case

Why Stacks are Effective for Implementation

●​ Stacks have a LIFO data structure

●​ Each recursive call is pushed to the stack and is then popped as function ends
●​ Enables backtracking/unwinding to maintain the required order

​ Winding and Unwinding

●​ Winding – the statements following a recursive function call are not executed
until the general case has reached base case
●​ Unwinding – occurs once the base case has been reached

​ Benefits of Recursion

●​ Can require fewer programming statements than an iterative approach (shorter

and more effective code)
●​ Can solve complex problems in a simpler way than an iterative solution could /
provides simpler solutions to problems

Drawbacks

●​ Very repetitive and requires more storage space (demanding use of stack),
meaning stack overflow can occur
●​ Infinite recursion can occur

Translating Recursive Programming Code

●​ The compiler must produce object code to

➔​ Push return addresses/values of local variables onto a stack with each
recursive call
➔​ Pop return addressed/values of local variables off the stack after the base
case is reached
8.​ Further Programming

20.1 Programming Paradigms

Programming Paradigm

●​ A set of programming concepts

●​ Defines the structure and capability of a programming language

Low-Level

●​ Uses the instruction set of a processor

●​ Makes use of different addressing modes – immediate, direct, indirect, indexed and
relative

Imperative

●​ Uses variables – changed using assignment statements, rely on an

iterative/repetitive method
●​ Statements provide an explicit sequence of commands for the computer to perform
(in the order written) – each line of code changes something in the program being
run, commands update the program state

Object Oriented

●​ Uses the concept of class, inheritance, encapsulation and polymorphism

Object-Oriented Programming Terminology

Properties/Attributes

●​ The data items or data types defined in a class

●​ Private attributes
➔​ Enforce encapsulation (ensures they are hidden)
➔​ Ensure attributes are only accessible using the class’s own methods/within
the class

Methods
●​ the modules (e.g. functions) in a class implementing the behaviours that act on the
attributes (properties)

Inheritance
●​ methods and properties contained in one class are reused/made available to a
derived class
 Polymorphism
●​ allows methods to be redefined (take on different behaviours) for derived classes

Encapsulation
●​ process of putting properties and methods inside a class (ensures sensitive data is
hidden) together as a single unit

Getter
●​ method that is used to return the value of a property

Setter
●​ method that is used to update/set the value of a property

Instance
●​ an occurrence of an object

Structure/Contents of a Class

●​ Attributes/properties and their respective data types - these are variables bound to
the class
●​ Methods - subroutines that act upon the attributes
●​ Getters and Setters - methods that fetch/update the attribute contents
●​ Constructor - used to create instances of objects in the class

Object vs. Class

●​ The class is only defined once, but many objects can be created from it - acts as a
template from which objects are created
●​ Objects are allocated memory space when created
●​ Classes are not allocated memory space when defined
●​ A class cannot be manipulated, but objects can (a class is not available in memory)
●​ Classes are defined, objects are created/declared
●​ Classes can use inheritance, objects cannot

Declarative

●​ Instructs a program on what needs to be done instead of how to do it – specifies

desired result rather than method of acquiring it
●​ Uses facts, rules and queries to satisfy goals
●​ Can be logical (states program as set of logical relations) or functional
(constructed by applying functions to arguments)
20.2 File Processing and Exception Handling

Exception Handling Routine

●​ Responds to unexpected events while a program is running – prevents programs

from halting unexpectedly
●​ Traps runtime errors
●​ Produces meaningful error messages

Exception

●​ Unexpected event that occurs during the execution of a program

●​ Causes the program to halt execution
●​ Examples of Exceptions – end of file, programming/user error, hardware failure,
division by zero (runtime errors)
 Paper 4 (Python)

These are basic templates for programming concepts that come up often in the Paper 4.
They differ from paper to paper, but the general code is always similar:

Linear and Binary Search

●​ Linear search

➔​ One by one, compares element at each index position with desired item
➔​ Can also utilise a boolean Found variable (used especially when something
has to be executed if the item is not found)

●​ Binary search

➔​ “First”: the first index/element of section being searched - initialised to 0

➔​ “Last”: the last index/element of section being searched - initialised to last
index of array (the position of the last element)
➔​ The array is halved until element/data at MidValue index position matches
DataToFind
➔​ If the value at the MidValue position is smaller than DataToFind, the upper
half of the section is discarded (hence, MidValue becomes the last element
in the new section)
➔​ If the value at the position is larger, the lower half of the section is
discarded (hence, MidValue becomes the first element in the new section)
 ➔​ This is done repeatedly until the entire array has been searched or the
value is found and returned (-1 is returned if the value has not been found)

Insertion and Bubble Sort

●​ Insertion sort

➔​ Opposite to a bubble sort, the insertion sort compares the current value
with the ones that come before it
➔​ Outside ‘for’ loop: ensures the code runs through each element in the array
and moves it into the right slot (swaps it with the one that was there
before)
➔​ ‘Current’: stores the current variable being compared against all others
before it
➔​ Inside ‘while’ loop: compares Current value with all other elements that
come before it, swapping it with the ones that are larger
➔​ When ‘while’ loop stops running, the value is slotted into the latest index
position

Representation of Algorithm
●​ Bubble sort

➔​ 1st ‘for’ loop: contents run as many times as there are elements in the array
➔​ 2nd ‘for’ loop: contents run through the array, each time leaving out one
more element from the end (what the ‘-i’ is for)
➔​ Comparison: depending on whether descending or ascending order is
wanted, the statement will be slightly different
➔​ Swap: elements in arrays are swapped, usually through use of a variable
for temporary storing of an element’s contents

Representation of Algorithm

Recursive Algorithms (TBA)

Files

●​ Reading from a file

➔​ Implement exception handling

➔​ The “textname.txt” depends on specific file name given in question
➔​ The “\n” is used to indicate a new line, and is removed from the read line
when inserting it into the array
(Would otherwise save it as “linedata\n” instead of just “linedata”)
➔​ Always close the file after use

➔​ When transferring file contents to an array, a ‘for’ loop is used (runs

through each line individually)
➔​ Each line is read separately and appended to the array
Classes/Objects (OOP)

●​ Declaring a class

➔​ ‘def__init__’ is the constructor

➔​ ‘self.__’ sets the attributes (values) to private (‘self.’ would be public)

●​ ‘Get’ methods - return a value from the class

➔​ Always include ‘self’ in function parameters

➔​ Function is indented into the class, same way as the constructor

●​ ‘Set’ methods - change a value to given parameter

●​ Creating objects from declared classes

➔​ “ObjectName” would be the name of the object being created

➔​ Values in brackets will depend on the declared class - order of given
parameters has to match with constructor E.g.

def_init_(self, Subject, Code, Grade) → ClassName(“Mathematics”,9709,”A”)

●​ Working with objects

 ➔​ Returns the value from object
➔​ Sets the variable Value1 to 20

➔​ Appends an element of type ClassName to array

➔​ Returns Value1 from object held in index i
➔​ Sets Value1 of object held in index i to 20

Exception Handling

➔​ All code that should be executed is indented into “try:” command

➔​ Code under “except:” command will execute if an error (exception) occurs in
code above

Encoding ADTs (Abstract Data Types)

1. Stacks

➔​ Stacks use an array and a TopPointer, which usually points to the next free
space in the array/stack

●​ Adding an item - Push

 ➔​ If statement checks that the Pointer isn’t pointing to a value out of the
stack range (index 20 implies 21st element, so if the stack only stores 20,
the stack would already be full)
➔​ When a value is appended to the stack, the TopPointer is always
incremented

●​ Removing an item - Pop

➔​ If statement checks the stack isn’t already empty

➔​ Value of TopPointer is decremented and the value currently stored there is
returned
➔​ This element is removed from stack using the .pop() function

2. Queues

●​ Initialising a queue structure

➔​ Heapointer points to the first element in the queue (initially -1 as there are
no elements to point to yet)
➔​ TailPointer points to next available slot in the queue (this is initially the first
element in the empty array, so index 0)
➔​ For a circular queue, both the Head and Tail pointers are initialised to 0 (A
variable storing the number of items in the queue is also used)
●​ Adding items to a queue

➔​ If TailPointer points to index 20 (21st element in the array), the queue is

already full
➔​ Otherwise, value is appended to the queue and TailPointer is incremented
➔​ If the queue was empty before, HeadPointer is now set to 0
➔​ For a circular queue, if the TailPointer value is 20, it would be reset to 0,
pointing back to the start of the queue

●​ Outputting an item from a queue

➔​ If HeadPointer == TailPointer, it means all other queue elements have

already been outputted and the queue is empty
➔​ For a circular queue, if the HeadPointer value is 20, it would be reset to 0,
pointing back to the start of the queue (when dequeuing, variable storing
the number of items in queue is also decremented)
3. Linked Lists

●​ Declaring/initialising a linked list and pointer variables

➔​ This code will depend on the specifics of the question, but generally -1 is
used to indicate an empty node (index 0 is the data, index 1 is a pointer)
➔​ FirstNode is set to -1 as there is no node to point to yet (as all are empty)
➔​ FirstEmpty points to the first empty node (so is set to 0 at start, as it points
to the first array element)
➔​ This particular list has 20 nodes - last node appended has pointer value set
to -1, indicating a null pointer
●​ Inserting nodes into a linked list

➔​ Line 7: only inserts a new node if the list isn’t full ( if FirstEmpty = -1, it
means there are no more empty nodes)
➔​ Line 9: nextEmpty stores the pointer of the next empty node
➔​ Line 10: Stores value in empty node
➔​ Line 11: Node now points to the one before it in the linked list
➔​ Line 12: FirstNode now points to the node with the newly stored value
➔​ Line 13: FirstEmpty now points to the next empty node
●​ Removing nodes from a linked list

➔​ Line 6: if the most recent node has the value to be removed…

➔​ Line 7: the first node will now be the one the most recent node is pointing
to (this pointer is stored temporarily)
➔​ Line 8: pointer of node will now point to an empty node as it becomes part
of the empty list
➔​ Line 9: FirstEmpty will now point to this node
➔​ Line 10: FirstNode will now point to the next node that isn’t empty

➔​ Line 12: if the list isn’t empty…

➔​ Line 13: Pointer value starts of as FirstNode and will be used to index the
nodes in the list
➔​ Line 14: -1 is just a temporary value, gets replaced by value of Pointer later
➔​ Line 15: loop runs while the Pointer hasn’t indexed through all the nodes
or the node containing the value to be removed hasn’t been found yet
➔​ Line 16: the PreviousNode will now contain the value of the Pointer before
it is incremented
➔​ Line 17: Pointer gets incremented
➔​ Line 19: node at PreviousNode now points to the node that the one being
removed is pointing to
 ➔​ Line 20: node being removed now points to an empty node as it becomes
part of the empty list
➔​ Line 21: value of index 0 is set to -1 to indicate it is empty
➔​ Line 22: FirstEmpty now points to the removed node

●​ Outputting a linked list

➔​ Pointer value is used to index through all the nodes, starting at FirstNode
➔​ While loop runs until last node is reached, which will be indicated with a
null pointer (-1)
➔​ Pointer is incremented by being set to the pointer stored in the current
node being printed