stolen copy EOY Revision_Theory

Data Validation (definition)

Data validation involves checking data to see if it conforms to specific requirements, before further processing

How many data validation techniques are there?

5

State all the data validation techniques

1. Range Check

2. Length Check

3. Format Check

4. Presence Check

5. Check Digit

Data Verification (definition)

Data verification is a process in which data is checked for accuracy and consistency after data migration (i.e. data being moved or copied from one place to another). It ensures that the data entered is what the user intended to enter.

What are the data verification techniques?

1. Double Entry (enter the required data twice)

2. Proofreading data (checks entered data against existing database)

3. Check sum (checks data contents are correct and not modified midway)

How many types of errors are there generally?

3

What are the types of errors?

1. Syntax Erros

2. Runtime errors

3. Logic Errors

When does syntax error occur?

When one or more rules of the programming language are violated → interpreter unable to understand the code

When does runtime error occur?

When the code follows the rules of the programming language → interpreter unable to execute the code

When does logic error occur?

When the code follows the rules of the programming language → program runs successfully → result is incorrect

When does a stack overflow error occur?

When recursive functions do not have a well-defined base case and recur infinitely

What are the three test cases to use when testing a program?

1. Normal Test Case

2. Abnormal Test Case

3. Extreme Test Case

What results do normal test cases yield?

Usually well-defined results that can be checked

What results do abnormal test cases yield?

Usually errors

What results do extreme test cases yield?

Usually return a result
If no possible valid result → error

What are some reasons critical data can be lost disastrously?

1. Natural disasters (e.g. fire, earthquake, or flooding) resulting in destruction of computer and storage equipment

2. Data corruption due to improperly configured software or malfunctioning hardware

3. Human error leading to data loss (e.g. accidental deletion of data)

What are Data Backups?

Additional copies of a data available that enables an organisation to restore it in the event of disastrous data loss

What should be done to data backups?

They should

• be created at regular intervals so that the backups are not too outdated

• be stored offsite (i.e. not in the same location as the data in use), so that disasters causing loss of the original data are unlikely to affect the backup

• be tested regularly, to ensure that the backups are not themselves corrupted, and the data backups can actually be restored without error

Why is data archival needed?

A company or organisation may have data that is no longer in active use, but still has to be retained. Keeping such data on the companies’ computers takes up storage space that is needed for other ongoing projects. The company can archive such data by copying it to cheaper storage (e.g. external hard drives)

Can lists in pseudocode be resized?

No

When you want to remove some contents of a list and replace it, how do you do it in pseudocode?

Create a new list and add to it

Can +=, -=, /= be used in pseudocode?

No

Can you check if a certain item belongs to a certain place (membership check) in pseudocode?

No

Can variables be of any type in pseudocode?

No

What is the comment key in pseudocode?

//

What is the only abstract data type allowed in pseudocode?

Array

What is the starting index for pseudocode?

1

For every if, for and while, function, what must be added for pseudocode?

END…

Write this in pseudocode

for i in range(len(data)):
    # loop through

FOR i ← 1 TO Data.Length

    // loop a code

ENDFOR

Write this in pseudocode

for item in data:
    # do something with item

FOR i ← 1 TO Data.Length

    Item ← Data[i]

    // do something with Item

ENDFOR

Pseudocode for membership check(dn to know)

FUNCTION In(item : INTEGER, Data: ARRAY) RETURNS BOOLEAN

    FOR i ← 1 TO Data.Length
        If Data[i] = item
            THEN
                RETURN TRUE

         ENDIF
    ENDFOR
    RETURN FALSE
ENDFUNCTION

IF In(Item, Data)
    THEN
    // do something…
ENDIF

What are the Three main labels for Decision Tables?

Rules, Conditions, Actions

How to determine the number of columns for Rules for decision table?

2ⁿ (where n is the number of conditions)

How are the first three rows of conditions written for decision table?

1. Half Yes Half No

2. YY NN YY NN

3. YNYNYN

What can be written for the actions for decision table?

X or -

When writing pseudocode for decision tables, when is “input” used?

When the value is to be changed by the code and returned using output

What is the base for Denary numbers?

10

What is the base for Binary numbers?

2

What is the base for Hexadecimal numbers?

16

How to convert from Decimal to Hexadecimal?

Divide the number by 16, and the Hex is the remainders in the opposite order

How to convert from Decimal to Binary?

Divide the number by 2, and the Bin is the remainders in order

How to convert from Binary to Decimal?

(Number x 2^position) x total number of numbers (position starts from 0)

How to convert from Hexadecimal to Decimal?

(Number x 16^position) x total number of numbers (position starts from 0, number in opposite order)

What are some uses of Hexadecimal in Computing?

1. Memory addresses and other hardware related values

2. Representation of colour values

3. Error messages

4. Memory dump

5. Debugging

6. MAC Addresses

7. IP addresses (IPV6)

8. ASCII / Unicode etc

How many bits does ASCII use to represent how many symbols?

7 bits to represent 128 symbols / characters

(2⁷ = 128)

How many bits does extended ASCII use to represent how many symbols?

8 bits to represent 256 characters / symbols

(2⁸ = 256)

(ASCII) Denary for character ‘a’

97

(ASCII) Denary for character ‘A’

65

(ASCII) Denary for character ‘0’

48

How many values can n (binary) bits represent?

2ⁿ

How many bits is a byte? Hence, how many values are represented?

8 bits, 256 values

How many binary bits can one hexadecimal digit represent? Why?

4 because 2⁴ = 16 and hex is base 16

What does a float consist of?

1. Sign

2. Significand (Mantissa)

3. Exponent

What is a binary float?

Floats with base 2

What operators can Booleans operate with? Name some examples.

Logical operators
E.g. And, Or

How many categories of characters does Unicode contain?

8

Name all the categories of characters that unicode has

1. 154 scripts from almost all languages

2. Emojis

3. Math Symbols and Arrows

4. Linguistic Symbols

5. Technical Symbols

6. Arrows and box-drawing characters

7. Symbols & Miscellaneous

8. A private-use area for font designers to include their own symbols

How many different encodings of Unicode do you need to know?

1

What is the encoding of Unicode that you need to know?

UTF-8

How many bytes does Unicode UTF-8 use per character?

up to 4

Which Unicode encoding is the most common one used on the internet? Why?

UTF-8.
It is backward-compatible with ASCII because ASCII is a subset of UTF-8

Which Unicode encoding is the most uncommon one used on the internet?

UTF-32

Encapsulation (definition)

The bundling of data and methods that act on the data into an object

Encapsulation (purpose)

• Protects the data against inadvertent modification

• Supports information hiding by separating the interface of the object or class from its implementation

What does a class diagram consist of?

1. Class name, a singular noun starting with an uppercase letter

2. Class attributes, with a + prefix for public and a - prefix for private attributes

3. Class methods, with a + prefix for public and a - prefix for private methods, () at the end

How does encapsulation protect private data against inadvertent modification or access?

Any program accessing an object will only be able to see the public methods and attributes, and the private attributes are hidden from the program, and can only be accessed if there are public methods that allows the getting and setting of the attributes.
Hence, private data is protected against inadvertent modification as methods need to be called to access to it, ensuring that access to it is intentional

How does encapsulation separate interface and implementation?

The private attributes are not part of the public interface of the class → the main program cannot access it → thus will not rely on them

Any changes made to the private attribute does not affect the main program

Polymorphism (definition)

The ability of methods with the same name in different classes to exhibit different behaviours at runtime

Polymorphism (purpose)

Promotes code generalisation

When are two classes polymorphic?

When they share a common public interface

How does polymorphism promote code generalisation?

Even though the implementations of the classes’ methods may be different, since the name is the same, the same method can be called and no class-checking is needed. The code is generalised because the methods that serve the same purpose have the same name

Inheritance (definition)

The ability of a child class to access public methods of a parent class

Inheritance (purpose)

To promote code reuse.
The child class can override or extend public methods of the parent class without having to repeat the code already in the parent class method

How does inheritance work?

The subclasses (child classes) inherit from the superclass (parent class) → they can access the public attributes and methods of their superclass

How is inheritance shown in class diagrams?

Hollow triangular arrow point from the child class to the parent class

How does code reuse work in inheritance?

1. When the subclasses use the same code as the superclass to implement a method, they do not need to implement any additional code or the same method again. Thus, they reuse the code that was already implemented in the superclass.

2. If the subclasses would like to add additional code to the existing methods in the parent class, they can call the method from the super class under their own method and add the information. This also demonstrates code reuse.

What does a hash function do?

• Takes an input key of any length

• And returns an output location of fixed size

  (The output must have finite range to be used in an array)

• Returns the same location for each unique key

To be hashable, what must the key be (requirement)? Why?

Immutable (the same)
so that its hashed index is always the same

What are the Hashtable operations?

1. Adding a key-value pair

2. Retrieving the value with a key

3. Removing a key

4. Updating the value associated with the key

What are the hashtable operations and what are the steps to carry them out?

1. Adding a key-value pair

   1. Hash the key to a location

   2. Store the value in the hash table at the hash index

2. Retrieving a value with a key

   1. Hash the key to a location

   2. Retrieve the value from the hash table at the location

3. Removing a key

   1. Hash the key to a location

   2. Store a sentinel value (e.g. None) in the hash table at the location

4. Updating the value associated with a key

   1. Hash the key to a location

   2. Store the value in the hash table at the location

What is a hash collision?

When some keys hash to the same index since the number of possible keys is much larger than the number of locations

To minimise the chance of hash collisions, what properties should an ideal hash function demonstrate?

The hash function should use all input data so that

A small difference in input results in large difference in output location so that

the output is uniformly distributed across the entire output range

When is a hash collision likely to happen?

When there is a

1. a poor hash function

2. a small hash table

How many hash table resolution methods are there?

2

What are the hash table collision resolution methods?

1. Open addressing (a.k.a. closed hashing)

2. Closed addressing (a.k.a. open hashing)

(Understanding) How is open addressing implemented?

When a hash collision occurs, a rehashing function is used to open up a new location to store the value. If the new location is occupied again, another rehashing function is called until there are no more locations left to generate.

When retrieving a value using its key, since the same key may have been rehashed multiple times, the key and the value must be stored together to ensure that the key matches the key used to add the value

What are the operations of open addressing?

1. Adding a key-value pair / updating the value associated with a key

2. Retrieving a value with a key

3. Removing a key

How is a key-value pair added into a hash table using open addressing?

1. Hash the key to a location

2. Check the existing key at the location for a match.

   1. if the key matches, store the key and value at the location and stop here

   2. if the key does not match, go to step 3

3. Rehash the key to get a new location and repeat from Step 2

   1. If no more locations are available, return the sentinel value or raise an error

How is a value from the hash table retrieved using the key?

1. Hash the key to a location

2. Check the existing key at the location for a match.

   1. if the key matches, return the associated value

   2. if the key does not match, go to step 3

3. Rehash the key to get a new location and repeat from Step 2

   1. If no more locations are available, return the sentinel value or raise an error

How is a key (and its associated value) removed from the hash table using open addressing?

1. Hash the key to a location

2. Check the existing key at the location for a match.

   1. If the key matches, store the sentinel value at the location.

      If necessary, update subsequent rehashed locations.

   2. if the key does not match, go to step 3

3. Rehash the key to get a new location and repeat from Step 2

   1. If no more locations are available, raise an error

(Understanding) How is closed addressing implemented?

Each location is a linked list. If a hash collision occurs, the key and the value are stored in the linked list at that location.

When retrieving the value using the key, the linked list must be walked through until a matching key is found, implying for the need to store the key and value together

What are the operations of closed addressing?

1. Adding a key-value pair

2. Retrieving a value with a key

3. Removing a key

4. Updating the value associated with the key

How is a key-value pair added into a hash table using closed addressing?

1. Hash the key to a location

2. Check if the linkedlist at the location contains the key.

   1. if the key is found in the linkedlist, update the associated value and stop here

   2. if the key is not found, add the key-value pair to the linkedlist

How is a value from a hashtable retrieved using its key using closed addressing?

1. Hash the key to a location

2. Check if the linkedlist at the location contains the key.

   1. if the key is found, return the associated value

   2. if the key is not found, return an appropriate value or raise an error

How is a key (and its associated value) removed from the hash table using closed addressing?

1. Hash the key to a location

2. Check if the linkedlist at the location contains the key.

   1. if the key is found in the linkedlist, remove it from the linkedlist.

   2. if the key is not found, display an error or return an appropriate value

What should be done when the hash table is full?

The hash table will need to be resized. This involves

1. creating a new hash table

2. copying each key-value pair from the old table, rehashed (with the new table size)

3. inserted to the new table

How many types of sort algorithms are there?

2

Sort the sort algorithms into their types

Linear algorithms

1. Bubble Sort

2. Insertion Sort

Divide-and-conquer algorithms

1. Merge Sort

2. Quick Sort

What are the key steps for bubble sort?

1. For each consecutive pair of elements, if the smaller-index element is greater than the larger-index element, swap their positions.

2. After the first iteration, the largest element should be at the end of the array.

3. Repeat for n iterations, where n is the number of elements in the array.

What are the optimisations for bubble sort?

1. In the final iteration, only the first element is unsorted, while all the other elements are sorted. Logically, this iteration can be skipped, since the remaining unsorted element must be the smallest; it is therefore already in the correct position.

2. The Bubble Sort algorithm can skip sorted elements. This means that it can skip the last element on the second iteration, skip the last 2 elements on the third iteration, etc.

3. In any iteration, if no swaps are made at all, that implies that the array is already sorted. The subsequent iterations may be skipped.