Cambridge International

A Level Computer Science

(9618) – Revision Notes
Advance Data Representation
This pack is intended for students to who are taking
CIE A Level in Computer Science, either in
preparation for their A Level exam, or more likely
alongside year 2 of the course to improve fluency,
recall and pace on AS & A topics. It could be used
© 2024 Exams Papers Practice. All Rights Reserved
as lesson starters, or supplied to students for
independent use.

For more help, please visit [Link]

Chapte 16
r

Advanced
Data
Representatio
n © 2024 Exams Papers Practice. All Rights Reserved

AS & A Level Computer Science

9618
For more help, please visit [Link]
 Chapter
Outline
16.1 16.2 16.3
Data File Real
Types Organisation numbers

© 2024 Exams Papers Practice. All Rights Reserved

For more help, please visit [Link]

16.1 Data Types

Data Types
A data type is a classification that determines the type of data a variable can hold,
and specifying it is crucial as it defines the range of values and operations applicable to
that variable, ensuring accurate storage, manipulation, and interpretation of data
within a program.

“a” in ASCII

1100001
© 2024 Exams Papers Practice. All Rights Reserved

97 in denary

For more help, please visit [Link]

16.1 Data Types

Built-in VS User-defined data types

Built-in data type User defined data type

Built-in data types are predefined data User-defined data types are created by
types provided by a programming programmers to suit specific needs
language. within a program.
The programming language defines:
Eg. In Python, you can create user-
The range of possible values that can defined data types using classes.
be assigned to a variable when its type
has been chosen. Eg: Java Int Data
Type: -2,147,483,648 to © 2024 Exams Papers Practice. All Rights Reserved
2,147,483,647
The operations that are available for
manipulating values assigned to that
variable.
“a” + “b” = “ab”
3+5=8
For more help, please visit [Link]
16.1 Data Types

Composite VS Non-composite data types

Composite data Non composite data type

type
A composite data type refers to a data structure A non-composite data type, also known
that contains multiple components. Examples: as a primitive data type, represents a
Arrays, lists, dictionaries, structs. The following
single value and does not have internal
are the composite user-defined data types.
subcomponents. Examples: Integers,
Record Data Type floating-point numbers, characters, and
Boolean values, and enumerated data
type.
© 2024 Exams Papers Practice. All Rights Reserved

Class

For more help, please visit [Link]

16.1 Data Types

Enumerated Data Type

An enumerated data type in programming is a user-defined collection of named
constant values that represent a set of related items or options within a specific domain.
For example:

Order matters Pseudocode

© 2024 Exams Papers Practice. All Rights Reserved

Not a string

For more help, please visit [Link]

16.1 Data Types

Enumerated Data Type

An enumerated data type in programming is a user-defined collection of named
constant values that represent a set of related items or options within a specific domain.
For example:
Python

© 2024 Exams Papers Practice. All Rights Reserved

For more help, please visit [Link]

16.1 Data Types

Pointer Data Type

A pointer data type in programming stores the memory address of another variable or
data element in the computer's memory.

© 2024 Exams Papers Practice. All Rights Reserved

For more help, please visit [Link]

16.1 Data Types

Set Data Type

A set data type in programming is an unordered collection of unique elements
without duplicate values.

Unordered: Sets do not maintain elements in any specific

order.
Unique Elements: Sets only contain unique elements;
duplicates are automatically removed.

Unstructured: Set has no structure hence no indexing can

be associated© 2024
with the elements in the set.
Exams Papers Practice. All Rights Reserved

{4, 3, 5, 1,
{a, z,
2}s, f,
For more help, please visit [Link]
16.1 Data Types

Set Data Type Operations

• Check if a value exists in a set

{4, 3, 5, 1, • Adding a new data value

{a, z,
2}s, f,
• Removing an existing data value

• Adding one set to another set

© 2024 Exams Papers Practice. All Rights Reserved

c}
For more help, please visit [Link]
James Gan
16.1 Data Types

Set Data Type Operatios

Using set in Python to remove duplicated items in the list.

© 2024 Exams Papers Practice. All Rights Reserved

For more help, please visit [Link]

16.1 Data Types

Set Data Type Operatios

Using set in Python to find out the intersection of the two sets.

© 2024 Exams Papers Practice. All Rights Reserved

For more help, please visit [Link]

Subtopic
16.2 File organisation
1

Binary Code
All type of file is stored using a specific binary code that allows the file to be used as
intended.

© 2024 Exams Papers Practice. All Rights Reserved

For more help, please visit [Link]

Subtopic
16.2 File organisation
1

Text files and Binary files

Text files Binary files

A text file stores data in a human- A binary file stores data in a format
readable format according to a that the computer can interpret
character code (ASCII, Unicode). directly as sequences of bytes.
The organisation of a binary file is
based on the concept of a record.

File

Record
© 2024 Exams Papers Practice. All Rights Reserved Record

Field Value Field Value

s s
Field Value Field Value
s s

For more help, please visit [Link]

Subtopic
16.2 File organisation
1

Binary files
• The number of fields per record must be known
• The size of each field (number of bytes) must be known as well

Image file Audio file

Pixel 1 Pixel 2 1st ms 2nd ms

Left Left
Red Value Red Value Amplitu Value Amplitu Value
de de
Right
Blue Value Blue Value Amplitu Value Right
Amplitu
Value
de de

Pixel 3 Pixel 4 3rd ms 4th ms

© 2024 Exams Papers Practice. All Rights Reserved
Left Left
Red Value Red Value Amplitu Value Amplitu Value
de de
Right Right
Blue Value Blue Value Amplitu Value Amplitu Value
de de

For more help, please visit [Link]

Subtopic
16.2 File organisation
1

File organisation and access

Serial files Sequential files Direct-access files

A file organization method where A file organization method where A file organization method allowing
records are arranged in a linear records are arranged sequentially data retrieval or storage at any
sequence, accessed sequentially and accessed in a predefined location within the file without
from start to end. order, typically from the beginning needing to sequentially traverse the
to the end, and modification often entire file.
Real-life Scenario: Daily requires re-writing the entire file.
transaction logs in a financial Record
institution. Each day, the institution Real-life Scenario: Order 1
records transactions sequentially in processing in an e-commerce Record
a log file, appending new platform.
© 2024Orders
Exams Papersplaced by Reserved
Practice. All Rights 2
transactions at the end. customers are stored sequentially in
a file, and the system processes Record
them one by one in the order they 3
were received.
Record
4
For more help, please visit [Link]
Subtopic
16.2 File organisation
1

Two ways to achieve direct access

First Way: Use a sequential file with a separate index file.

An index is like a data structure TeamsName ID Local

that contains a sorted list of key
values and pointers to the actual Selangor FC 44343 Y

records in the table.

Penang FC 23455 N
ID Pointer

KL FC 54545 Y
23455
© 2024 Exams Papers Practice. All Rights Reserved
Scanning through the index table is a lot faster
44343
than scanning through the entire table due to the
usage of efficient data structure (hash table / B-
54545 tree) - We will learn more in chapter 23.

For more help, please visit [Link]

Subtopic
16.2 File organisation
1

Two ways to achieve direct access

Second Way: Use a hashing algorithm.

Fil
1
Dat e
2
I a
Nam Ag
D e e 3
207 Jac 2
4
6 k 5
107 Muhamm 2 5
© 2024 Exams Papers Practice. All Rights Reserved
3 ad 4
507 Davi 2 6
7 d 9 7
8
For more help, please visit [Link]
Subtopic
16.2 File organisation
1

Two ways to achieve direct access

Second Way: Use a hashing algorithm.

Dat Fil
I a
Nam Ag 1
D e e
e
207 Jac 2
6 k 5
2
107 Muhamm 2
3
507
ad
Davi
4 3
2
7 d 9
4
Hashing algorithm (example): 5
© 2024 Exams Papers Practice. All Rights Reserved
[Link] the ID number by 10.
6
[Link] the Remainder
7
8
For more help, please visit [Link]
Subtopic
16.2 File organisation
1

Two ways to achieve direct access

Second Way: Use a hashing algorithm.

Dat Fil
I a
Nam Ag 1
D e e
e
207 Jac 2
6 k 5
2
107 Muhamm 2
3
507
ad
Davi
4 3 107 Muhamm 2
2 3
ad
4
7 d 9
4
Hashing algorithm (example): 5
© 2024 Exams Papers Practice. All Rights Reserved
[Link] the ID number by 10.
6 207 Jac 2
[Link] the Remainder 6 k 5

7 507 Davi 2
7 d 9
8
For more help, please visit [Link]
Subtopic
16.2 File organisation
1

Two ways to achieve direct access

Second Way: Use a hashing algorithm.

Dat Fil
I a
Nam Ag 1
D e e
e
207 Jac 2
6 k 5
2
107 Muhamm 2
7
507
ad
Davi
4 3
2
7 d 9
A collision can occur in a hashing algorithm 4
when two different inputs produce the same 5
© 2024 Exams Papers Practice. All Rights Reserved
hash value.
6 207 Jac 2
6 k 5
107 Muhamm
ad
2 7 507 Davi 2
7 4 7 d 9
8
For more help, please visit [Link]
Subtopic
16.2 File organisation
1

Best way to reduce collision

A good hash function exhibits even distribution, minimal collisions, and produces hash values
that seem random, without predictable patterns or clustering.

One of the methods is to use a prime numebr of a similar size to the expected size of the file.

© 2024 Exams Papers Practice. All Rights Reserved

For more help, please visit [Link]

Subtopic
16.2 File organisation
1

Dealing with collisions

• Implement a sequential search method to locate an empty address immediately following
the calculated position.
• Reserve a set of additional addresses at the end of the file to accommodate overflow data.
• Establish a linked list accessible from each address for efficient data retrieval and
management.

© 2024 Exams Papers Practice. All Rights Reserved

For more help, please visit [Link]

Subtopic
16.2 File organisation
1

Two ways to achieve direct access

Second Way: Use a hashing algorithm.

Dat
a
Nam
e
Jac
k
Muhamm
ad
Davi
d

If the record does not have a

© 2024 Exams Papers Practice. All Rights Reserved
numeric field, then the ASCII
code for alphabetic characters
can be used in the calculation.

For more help, please visit [Link]

Subtopic
16.2 File organisation
1

File access

Serial files Sequential files Direct-access files

Access occurs sequentially from start Access also takes place sequentially, In direct access files using hashing,
to end, with data retrieved or but if the key value is known for the file access involves directly mapping
appended in a linear order. record containing the wanted data, the hashed key to a specific location
the process is faster because only in the file where the desired data is
key field values need to be read. stored.

However, in cases of collision where

multiple keys hash to the same
location, serial searching within that
© 2024 Exams Papers Practice. All Rights Reserved location might be necessary to
retrieve the correct data, potentially
Fil
impacting direct access
1
e efficiency.
2

3
4

5
6 207 Jac 2
6 k 5
7 507 Davi 2
7 d 9
For more help, please visit [Link] 8
Subtopic
16.2 File organisation
1

File deletion

Serial files Sequential files Direct-access files

Deleting in a serial file typically Data is transferred from the old file to Deleting in a direct access file
involves marking the record as a new one until the targeted record involves marking the specific location
"deleted" without physically for deletion or modification is as available, allowing it to be reused
removing it to maintain sequential encountered, after which any for new data.
order. changes are made, and the
remaining records are then copied to
the new file.

© 2024 Exams Papers Practice. All Rights Reserved

For more help, please visit [Link]

Subtopic
16.2 File organisation
1

Choice of file organisation

• Serial File: Utilise a serial file when data needs to be maintained in chronological order or
when continuous appending of data is required.
• Sequential File: Choose a sequential file when the data needs to be processed in a
predefined order, allowing efficient sequential reading or writing operations.
• Direct Access File: Opt for a direct access file when quick access to specific data by its
location or key is essential, offering faster retrieval and modification capabilities.

© 2024 Exams Papers Practice. All Rights Reserved

For more help, please visit [Link]

 16.3 Real Numbers

Representing Real Numbers

1
6.47 x 10
can be
written as
64.7
= 0.647 x 10
2

-1
647 x 10
© 2024 Exams Papers Practice. All Rights Reserved

For more help, please visit [Link]

 16.3 Real Numbers

Representing Real Numbers

1
6.47 x 10
can be
written as
64.7
= 0.647 x 10
2

-1
647 x 10
© 2024 Exams Papers Practice. All Rights Reserved

The only
sensible
choice
For more help, please visit [Link]
 16.3 Real Numbers

Fixed-point representation
Fixed-point representation is a numerical format used in computing where a specific number of
bits are allocated for the fractional and integer parts of a fixed-length binary number,
enabling representation of fractional values with a fixed precision.
000 = 0.125
001 = 0.25
010 = 0.375
011 = 0.5
100 = 0.625
101 = 0.75
Eg (8 110 = 0.875
111 = 0.000
bits):
© 2024 Exams Papers Practice. All Rights Reserved

sign
bit 3 bits for fractional part
4 bits for whole numbers
For more help, please visit [Link]
 16.3 Real Numbers 000 = 0.125
001 = 0.25
010 = 0.375
011 = 0.5
100 = 0.625
Fixed-point representation 101 = 0.75
110 = 0.875
111 = 0.000

1 1 0 1 1 1 0 1

sign
bit 3 bits for fractional part
4 bits for whole numbers

- 11.75
© 2024 Exams Papers Practice. All Rights Reserved

For more help, please visit [Link]

 16.3 Real Numbers
Largest positive value = 15.875
Smallest positive value = 0.125
Largest magnitude negative value = -15.875
Fixed-point representation Smallest magnitude negative value = -0.125

Eg (8
bits):

sign
bit 3 bits for fractional part
4 bits for whole numbers

Description Binary Denary

Code
© 2024 Exams Papers Practice. All Rights Reserved
Largest positive value 0 1111 15.875
111
Smallest positive value 0 0000 0.125
001
Smallest magnitude negative 1 0000 - 0.125
001
value For more help, please visit [Link]
Largest magnitude negative 1 1111 - 15.875
 16.3 Real Numbers

Floating-point representation
A representation of real numbers that stores a value for the mantissa and a value for the
exponent.

E
+
- Mx
© 2024 Exams Papers Practice. All Rights Reserved

R Has an implied value

of 2
For more help, please visit [Link]
 16.3 Real Numbers

Floating-point representation
Assume that we are using 8 bits:

E 4 bits
+
-
4 bits
Mx
© 2024 Exams Papers Practice. All Rights Reserved

R
For more help, please visit [Link]
 16.3 Real Numbers

Floating-point representation
There are multiple ways we can structure the 4 bits to change where is the binary
point.
Intege Point Fractional Value
r
011 1 3.5

M
011 0 3.0
+ 1 2.0
-
010

101 0 -3.0
4 bits © 2024 Exams Papers Practice. All Rights Reserved

100 1 -3.5

100 0 -4.0

3 largest and 3 smallest representations

For more help, please visit [Link]
 16.3 Real Numbers

Floating-point representation
There are multiple ways we can structure the 4 bits to change where is the binary
point.
Intege Point Fractional Value
r
0 111 0.875

M
0 110 0.75
+ 101 0.625
-
0

1 010 -0.75
4 bits © 2024 Exams Papers Practice. All Rights Reserved

1 001 -0.875

1 000 -1.0

3 largest and 3 smallest representations

For more help, please visit [Link]
 16.3 Real Numbers

Floating-point representation
There are multiple ways we can structure the 4 bits to change where is the binary
point.
Intege Value
r
0111 7

M
0110 6
+ 0101 5
- 1010 -6
4 bits © 2024 Exams Papers Practice. All Rights Reserved
-7
1001

1000 -8

3 largest and 3 smallest representations

For more help, please visit [Link]
 16.3 Real Numbers

Floating-point representation
Eg (8
bits):
sign
bit

+
- M E
Description Binary Denary
Code
© 2024 Exams Papers Practice. All Rights Reserved 7
Largest positive value 0 111 0.875 x 2 =
0111 112
-8
Smallest positive value 0 001 0.125 x 2 = 1 /
1000 2048
-8
Smallest magnitude negative 1 111 -0.125 x 2 = - 1 /
1000
value For more help, please visit [Link] 2048
7
Largest magnitude negative 1 000 -1 x 2 = - 128
 16.3 Real Numbers

Comparison
Fixed point
representation
Descriptio Binary Denary
n Code
Largest positive value 0 1111 15.875
111
Smallest positive value 0 0000 0.125
001
Smallest magnitude negative 1 0000 - 0.125
value 001
Largest magnitude negative 1 1111 - 15.875
value 111 Floating point
representation
Descriptio Binary Denary
n
© 2024 Exams Papers Practice. All Rights Reserved Code 7
Largest positive value 0 111 0.875 x 2 =
0111 112
-8
Smallest positive value 0 001 0.125 x 2 = 1 /
1000 2048
-8
Smallest magnitude negative 1 111 -0.125 x 2 = - 1 /
value 1000 2048
7
Largest magnitude negative 1 000 -1 x 2 = - 128
For more help, please visit [Link]
value 0111
 16.3 Real Numbers

Precision and normalisation

To achieve maximum precision, we need to normalise a floating-point number.

In practice, using the largest possible magnitude for the value represented by the mantissa would achieve
optimum precision.

Denary 2 Denary - 4
Floating-point binary Floating-point binary
Denary Denary
representation representation
Representation Representation
4 4
0.125 x 2 0 001 0100 -0.25 x 2 1 110 0100
© 2024 Exams Papers Practice. All Rights Reserved

3 3
0.25 x 2 0 010 0011 - 0.5 x 2 1 100 0011

2 2
0.5 x 2 0 100 0010 -1.0 x2 1 000 0010
For more help, please visit [Link]
 16.3 Real Numbers

Precision and normalisation

When the number is represented with the highest magnitude for the mantissa, the two most significant bits
are different.

Denary 2 Denary - 4
Floating-point binary Floating-point binary
Denary Denary
representation representation
Representation Representation
4 4
0.125 x 2 0 001 0100 -0.25 x 2 1 110 0100

3 3
0.25 x 2 0 010 0011 - 0.5 x 2 1 100 0011
© 2024 Exams Papers Practice. All Rights Reserved

2 2
0.5 x 2 0 100 0010 -1.0 x2 1 000 0010

For more help, please visit [Link]

 16.3 Real Numbers

Precision and normalisation

For positive numbers, the mantissa's bits are moved to the left until the leading bits become 0 followed by 1,
causing a decrease of 1 in the exponent value for each left shift.

Denary 2
Floating-point binary
Denary
representation
Representation
4
0.125 x 2 0 001 0100

3 Exponent Left shift

0.25 x 2 0 010 0011
decreases
© 2024 Exams Papers Practice. All Rights Reserved

2
0.5 x 2 0 100 0010

For more help, please visit [Link]

 16.3 Real Numbers

Precision and normalisation

The same process of shifting is used for a negative number until the most significant bits are 1 followed by 0,
causing a decrease of 1 in the exponent value for each left shift.

Denary - 4
Floating-point binary
Denary
representation
Representation
4
-0.25 x 2 1 110 0100

3 Exponent Left shift

- 0.5 x 2 decreases
1 100 0011
© 2024 Exams Papers Practice. All Rights Reserved

2
-1.0 x2 1 000 0010

For more help, please visit [Link]

 16.3 Real Numbers

Conversion of representations
Convert 9.75.

Convert the whole number part. Add a leading 0.

9.75 0100
1
Notes:
Convert the fractional part. .00 = 00
.25 = 01
9.75 11 .5 = 10
.75 = 11

Combine the two parts

© 2024 Exams Papers Practice. All Rights Reserved
9.75 01001.1
1
Shift the binary point until beyond “10” (for positive number) to achieve
normalisation
01001.1 0.10011
For more help, please visit [Link]
1 1
 16.3 Real Numbers

Conversion of representations
Convert 9.75.

This gives an exponent value of 4 (we shift the point 4 times to the left).

Assume that 14 bits are allocated (10 bits for the mantissa and 4 bits for the
exponent),

0.10011 010011100 0100

1 0 mantiss exponen
a t

© 2024 Exams Papers Practice. All Rights Reserved

For more help, please visit [Link]

 16.3 Real Numbers

Conversion of representations
Convert 9.73.

Convert the whole number part. Add a leading 0.

9.73 0100
1
Convert the fractional part.

9.73 0.73 x 2 = 1.46

(keep 1) .1

Method = Multiply by 2 and © 2024 Exams Papers Practice. All Rights Reserved
record the whole number (4
bits)

For more help, please visit [Link]

 16.3 Real Numbers

Conversion of representations
Convert 9.73.

Convert the whole number part. Add a leading 0.

9.73 0100
1
Convert the fractional part.

9.73 0.73 x 2 = 1.46

(keep 1)
.1011
0.46 x 2 = 0.92
(keep 0)
0.92 x 2==Multiply
Method 1.84 by 2 and © 2024 Exams Papers Practice. All Rights Reserved
(keep 1)
record the whole number (4
bits)
0.84 x 2 = 1.62

For more help, please visit [Link]

 16.3 Real Numbers

Conversion of representations
Convert 9.73.

Convert the whole number part. Add a leading 0.

9.73 0100
1
Convert the fractional part.

9.73 0.73 x 2 = 1.46 .1011

(keep 1)
0.46 x 2 = 0.92
(keep 0)
0.92 x 2==Multiply
Method 1.84 by 2 and © 2024 Exams Papers Practice. All Rights Reserved
(keep 1)
record the whole number (4
bits)
0.84 x 2 = 1.62
Combine the two parts

01001.1011
For more help, please visit [Link]
 16.3 Real Numbers

Conversion of representations
Convert 9.73.

Shift the binary point until beyond “10” (for positive number) to achieve
normalisation
01001.1011 0.1001101
1
This gives an exponent value of 4 (we shift the point 4 times to the left).

Assume that 14 bits are allocated (10 bits for the mantissa and 4 bits for the
exponent),

0.10011 010011011 0100

1 0 mantiss exponen © 2024 Exams Papers Practice. All Rights Reserved
a t

For more help, please visit [Link]

 16.3 Real Numbers

Conversion of representations
Convert -7.75.

Start by converting 7.75 to binary.

7.75 011
1
Notes:
Convert the fractional part. .00 = 00
.25 = 01
7.75 11 .5 = 10
.75 = 11

Combine the two parts

© 2024 Exams Papers Practice. All Rights Reserved
7.75 0111.11

Convert to two’s complement form.

one.c two.c
0111.11 1000.00 1000.01
For more help, please visit [Link]
 16.3 Real Numbers

Conversion of representations
Convert -7.75.

Shift the binary point until beyond “10” to achieve normalisation

1000.01 100001

This gives an exponent value of 4 (we shift the point 4 times to the left).

Assume that 14 bits are allocated (10 bits for the mantissa and 4 bits for the
exponent),

100001 100001000 0100

0 mantiss exponen © 2024 Exams Papers Practice. All Rights Reserved
a t

For more help, please visit [Link]

 16.3 Real Numbers

Problems with using floating-point

numbers
Approximation and Rounding Errors: Floating-point numbers involve approximations, and rounding
errors can become significant during computations, particularly in repetitive operations. Accumulation
of these small errors might lead to inaccuracies in the final result, especially in complex computations
or numerical algorithms.

Limited Range of Numbers: Floating-point representation has a finite range to store numbers,
resulting in limitations on both the minimum and maximum values that can be accurately represented.
This limitation can lead to underflow errors when representing extremely small numbers, causing loss
of precision or inaccuracies in calculations involving very small values.

© 2024 Exams Papers Practice. All Rights Reserved

For more help, please visit [Link]