Fundamentals of algorithms

a level computer science topic three paper one aqa

what are the two types of simple graph traversal algorithms

breadth first search, and depth first search

what is breadth first search (BFS) used for

finding the shortest path via a node based method

what is depth first search (DFS) use for?

maze navigation via an edge based technique

how does BFS work

visits all nodes from a given vertex before moving on to their neighbouring nodes, and repeats this layer by layer, adding nodes onto the queue so long as they are not already in the list of visited nodes

How does DFS work

makes use of a stack and traverses as far down the graph from the start node, until it finds an unexplored path, it then repeats this consecutively until all paths have been explored.

• edges are visuted and nodes at the end of the edges are added to the visited nodes list

what are the two approaches that can be applied to DFS

iterative or recursive

what are the three types of simple tree traversal algorithms

pre order, post order and in order

how does pre order tree traversal work and why is it used

it works via following the root to left to right and is used in copying trees

how does the post order tree traversal work and why is it used

it works via following left to right to root, and is used to convert from infix to RPN

how does in order tree traversal work and why is it used

it works via following the left to the root to the right, and is used to output the contents of a binary tree in ascending order

what are the advantages of reverse polish notation

• operators are in the order which they need to be used

• removes the need for brackets

• expressions are in a form suitable for the stack based approach

• interperators based on stacks can then be used

• potentially faster execution as equations are in format that computer uses

what is referred to as the time complexity

how the runtime of an algorithm grows relative to the size of the input data

what are the three types of searches for algorithms

linear search, binary search, binary tree search

what is a binary search

a search on an ordered list, where the midpoint is found and the list is divided into half, where one half is discarded and the process repeats until there is only the searched item

what is the time complexity for a binary search

O(logn)

what is a binary tree search

when a list is ordered into a binary tree, and traversed to the left or the right depending on what is being searched for

what is the time complexity for a binary tree search

O(logn)

what are the two types of sorting algorithms

bubble sort and merge sort

what is a bubble sort

where elements are swapped if they are in the wrong order until the data is ordered via multiple passes through the list

what is the time complexity of a bubble sort

O(n²)

what is a merge sort

when a list of data items are divided into smaller subarrays that are then ordered and merged back together

what is the time complexity for a merge sort

O(nlogn)

what is an example of an optimizational algorithm

Dijkstra’s shortest path algorithm

what does dijkstra’s shortest path algorithm do?

finds the shortest path between one specified node and all other nodes on a weighted graph

what is dijkstras shortest path algorithm used for?

GPS navigation, IP routing, telephone networking