Define a linear search
Finds an item in a list by checking each item in turn
What are the key points of a linear search?
- Starts at the first item
- Searches in sequence
- Can be represented in an array or binary tree
What are the advantages of a linear search?
Easy to implement
Works on ordered or unordered lists
Easy to add items
What are the disadvantages of a linear search?
Usually most inefficient on longer lists
Define a binary search
An algorithm for finding an item in a sorted list.
Starts at the middle and repeatedly divides the list containing the item in half
What are the key points of a binary search?
- Starts at the middle item
- Halves the items needed to search after each check
- Can be represented by an array or linked list
What are the advantages of a binary search?
Efficient
Suitable for large data sets
What are the disadvantages of a binary search?
Only works on ordered lists
Slow to add items, as they must be placed in the right place
Define a bubble sort
Orders a list of items by comparing and swapping pairs of items.
It ‘bubbles’ the smallest/largest number to the ends
How does a bubble sort work?
- Starts at the first item
- Compares with the adjacent item, swapping if necessary
- Moves on until all pairs have been compared
- If any were swapped then a new pass will start
What are the advantages and disadvantages of a bubble sort?
Advantage: works well on small lists
Disadvantage: slow to work
Define an insertion sort
Slots each item into the correct position in a data set
How does an insertion sort work?
- Compares the second item to the one before
- Will continue along until the current item is less than the one before
- Compares the current item with all before to find the correct location
- Moves the items to their new positon
- Repeats until everything is in position
What are the advantages and disadvantages of an insertion sort?
Advantage: works well on small lists
Disadvantage: slow to work
Define a merge sort
Uses ‘divide and conquer’ to quickly sort data.
Creates multiple sub-problems, which are each solved individually before being re-joined.
How does a merge sort work?
- Repeatedly divides the list in half until each item has its own list
- Compares adjacent lists to order them into a new list
- Removes old lists
- Repeats with adjacent lists until one list formed
Define a quick sort
Sorts a set of data at a high speed using ‘divide and conquer’.
It creates sub-programs which are solved individually then combined.
A pivot value will be chosen to compare the items to when dividing the list.
How does a quick sort work?
- Sets a pivot value
- Compares each item to the pivot value, adding those less than to one list and greater than to another
- A pivot is chosen for the new lists
- Repeats until each item has its own list
- Conjugates the lists from left to right
Define the ‘Dijkstra’s Shortest Path algorithm’
Finds the shortest distance between the starting node and target node using a weighted tree
Define the ‘A* algorithm’
Finds the shortest path between two vertices on a weighted tree using heuristics. Won’t consider every vertex
What are the advantages and disadvantages of Dijkstra’s Shortest Path?
Advantage:
Finds the shortest time to a location
Disadvantage:
Every vertex must be investigated
What are the advantages and disadvantages of the A* algorithm?
Advantages:
Optimal in regards to efficiency
Works well for complex problems
Disadvantages:
The speed of execution is dependant on the heuristic accuracy
Can have complexity problems
How is the Dijkstra’s Shortest Path algorithm carried out?
- Two lists are formed: visited and unvisited nodes
- Node distances are infinity, other than the starting node, all fill the unvisited list
- For the current node: neighbouring unvisited nodes are examined by calculating the total distance to them from the start
- If the new distance is less than the known distance, the distance and previous node information is updated
- Add the current node to the visited list and move to the next shortest-distance-away node
- Repeat until all nodes have been visited
How is the A* algorithm carried out?
- Fundamentally the same as Dijkstra’s
- Each node has a heuristic value, e.g. the distance or time to the final node
- The nodes are ordered by heuristic + weight
- Once the final node has been reached and expanded, unvisited nodes are ignored as the shortest path is found
-
1.1.1 Structure and Function of the Processor23
-
1.1.2 Types of processor14
-
1.1.3 Input, Output and Storage12
-
1.2.1 Operating systems83
-
1.2.2 Applications generation45
-
1.2.3 Software development34
-
1.2.4 Types of Programming Language69
-
1.3.1 Compression, Encryption and Hashing32
-
1.3.2 Databases34
-
1.3.3 Networks74
-
1.3.4 Web Technologies8
-
1.4.1 Data types12
-
1.4.2 Data structures51
-
1.4.3 Boolean Algebra22
-
1.5.1 Computer Related Legislation9
-
1.5.2 Moral and Ethical issues6
-
2.1 Computational Thinking15
-
2.2.1 Programming Techniques11
-
2.2.2 Computational Methods13
-
2.3.1 Algorithms30
