Chapter 19 computational thinking and problem solving
01 September 2025 19:14
How to write algorithm for linear search :
Linear search where every each element of an array is checked in order from lower bound to upper bound until element is found or
upper bound is reached
How to write an algorithm for a binary search
Binary search is more efficient if the list is sorted already , binary search works by checking the middle item of the list, and the half
that doesn’t have the item is discarded:
Binary search uses less comparisons
New Section 1 Page 1
Write algorithm for bubble sort
New Section 1 Page 2
Write an algorithm for insertion sort
Insertion sort sorts data into a list of alphabetical or numerical order
New Section 1 Page 3
Insertion sort sorts data into a list of alphabetical or numerical order
Write an algorithm for finding inserting and deleting
Setting up:
Finding:
New Section 1 Page 4
Finding:
Inserting:
Deleting:
New Section 1 Page 5
Binary trees
Each node can only have two child nodes, if node is less than current node branch left else branch right
Creating :
New Section 1 Page 6
Creating :
Finding:
Inserting:
New Section 1 Page 7
New Section 1 Page 8
How to implement 1 adt from another ADT
When adt is defined is can be refered to other data types
New Section 1 Page 9
Comparison of algorithms using Big O notation :
Big o order of time complexity
New Section 1 Page 10
Chapter 13
01 September 2025 22:18
User defined data types:
They define their own data types based on primitive data types provided by a programming
language, or data types that they have defined previously in a program. These are called user-
defined data types.
Define non-composite data type
A non-composite data type can be defined without referencing another data type. It can be a
primitive type available in a programming language or a user-defined data type.
There are two types enum and pointer data type
Enum: An enumerated data type contains no references to other data types when it is defined. In
pseudocode, the type definition for an enumerated data type has this structure:
Pointer : A pointer data type is used to reference a memory location. This data type needs to have
information about the type of data that will be stored in the memory location:
Define composite data types
A data type that refers to any other data type in its type definition is a composite data type.
There are 2 types sets and classes
Sets: A set is a given list of unordered elements that can use set theory operations such as
intersection and union. A set data type includes the type of data in the set.
Methods of file organisation :
Serial file organisation:
The serial file organisation method physically stores records of data in a file, one after another, in
the order they were added to the file. New records are appended to the end of the file. Serial file
organisation is often used for temporary files storing transactions to be made to more permanent
files.
Sequential file organisation:
The sequential file organisation method physically stores records of data in a file, one after another,
in a given order. The order is usually based on the key field of the records as this is a unique
identifier. New records must be added to the file in the correct place
Random file organisation:
The random file organisation method physically stores records of data in a file in any available
position. The location of any record in the file is found by using a hashing algorithm
Methods of file access
New Section 1 Page 11
Methods of file access
Sequential access:
The sequential access method searches for records one after another from the physical start of the
file until the required record is found, or a new record can be added to the file. This method is used
for serial and sequential files.
For a serial file, if a particular record is being searched for, every record needs to be checked until
that record is found or the whole file has been searched and that record has not been found. Any
new records are appended to the end of the file. For a sequential file, if a particular record is being
searched for, every record needs to be checked until the record is found or the key field of the
current record being checked is greater than the key field of the record being searched
Direct access:
The direct access method can physically find a record in a file without other records being physically
read. Both sequential and random files can use direct access. This allows specific records to be found
more quickly than using sequential access.
New Section 1 Page 12
