13 Data Representation

• Larger exponent =

  Increased range
• Larger Mantissa =

  Increased precision
• Rounding Errors

  Some errors cannot be stored precisely + must be rounded, as size of mantissa and exponent are fixed, producing rounding errors
• Underflow


  Division calculation by a very large number produces a number too small for the smallest possible value that can be stored
• Overflow


  Calculation produces a number too large compared to the largest possible value that can be stored
• Normalisation Errors

  1. Value 0 cannot be stored, as mantissa must always start with either 01/10

  2. To store 0, you have to create a number which is very close to 0
• How To Normalise Binary Shift

  - Shift bits left until you get 01/10

  - Reduce exponent by number of places that floating point was shifted

  - Resulting number ALWAYS gets smaller
• Normalised Negative


  No leading ones after floating point, always starts with 1.0
• Normalised Positive

  No leading zeros after floating point, always starts as 0.1
• Location of floating is always

  Between the first two digits of the mantissa
• Exponent

  Power of 2 that the mantissa is raised to
• Mantissa

  Fractional part of number
• Floating Point Binary

  - Enables efficient use of registers to represent very large/small numbers with a high level of precision

  - Represents real numbers
• How hashing algorithms are used in file access

  - Hashing algorithm can be used to create an index

  - Key is entered to the algorithm to generate the index

  - The record can then be retrieved
• Hashing Algorithms

  - Attempts to map a big data set into a small set

  - Numeric value needs to be generated from the data in order to perform the calculation

  - Must generate unique indices

  - Needs to create a uniform spread of indices
• Direct File Access

  - Records are accessed directly without having to read other records

  - For sequential files; index can be used to find and access files directly

  - For random files; hashing algorithm is used to generate location
• Sequential File Access

  - Records are searched in order starting from physical start of file

  - For serial files; if record is required, each record must be checked until record is found

  - For sequential files; search can stop if a record larger than the search value is found
• Benefits/Drawbacks of Random

  B - Instant retrieval of records O(1)

  D - Gaps in data

  D - Collisions lead to data requiring chaining/linear probing

  D - Complexity of hashing algorithm
• Benefits/Drawbacks of Sequential

  B - Fast retrieval using search algorithms

  B - No gaps in data, efficient use of storage medium

  D - Slow insertion of data
• Benefits/Drawbacks of Serial

  B - Fast storage bc little processing

  D - Slow file searching/retrieval as files need to be searched linearly
• Serial v Sequential Organisation

  - In both kinds records are stored one after the other

  - ...And need to be accessed one after the other

  - Serial files are stored in chronological order

  - Sequential files are stored with ordered records

  - ..And stored in the order of the key field

  - In serial files, new records are added in the next available space/records

  - In sequential, new records are inserted in the correct position
• Random File Organisation

  - Records are saved in a place defined by generating a hash value on a key field

  - Direct access
• Sequential File Organisation

  - Records are saved/ordered by a key field

  - Accessed sequentially/directly
• Serial File Organisation


  - Records are saved in order of creation

  - Accessed sequentially
• Classes

  Composite data type, which combines several different data types into one type
• Sets

  - List of unordered elements

  - Can be acted on with set operations like intersection/union
• How to declare a pointer

  TYPE = ^

  
  

  EG. TYPE namePointer = ^STRING // pointer that points to a string variable
• Pointers

  - Used to reference a memory location

  - References no other data types
• How to define enumerated data types in pseudocode

  TYPE = (value1, value2, value3, ...)
• Enumerated Data Types

  - Reference no other data types

  - Used for values that have an order such as months, days, star signs, etc.
• Examples of Non-Composite Data Types

  - Primitive Types (INT, STR, etc.)

  - Enumerated

  - Pointers
• Non-Composite Data Type

  Defined without referencing another data type
• Why are user defined data types needed?

  - Programmer can use specific data types that exactly match a program's requirements

  - By defining new data types; you increase the set of data types available to you to support your applications

  - Data structures are self documenting, providing meaningful identifiers to the data
• User-Defined (Record)

  Any data type not provided by the programming language that must be defined before use
• Composite (Record)

  Made up of/references other existing data types
• Record

  - Composite user defined data type

  - Several related variables (possibly different types) stored under a single identifier

  - Record must consist of a fixed number of items

  - Allows programmer to pass/refer to several variables using a single identifier