Fundamentals of algorithims

. In a depth-first search, a branch is fully explored before backtracking .Depth-first traversal uses a stack. Depth-first traversal is used for navigating a maze

a node is fully explored before venturing on to the next node. Breadth-first traversal uses a queue. Useful for determining the shortest path

You can perform a binary search or an unordered list

This is reverse polish notation

It is unambigous Can be calculated on stacks

This is the instruction given

is the mathematical signs + -

An algorithm is a set of instructions which completes a task in a finite time and always terminates.

A linear search can be conducted on any unordered list. It is the most simple to program, but it has a comparatively high time complexity O(n)

A binary search can be used on any ordered list. If the list is unordered, the data must be sorted by a sorting algorithm. A binary search works by looking at the midpoint of a list and determining if the target is higher or lower than the midpoint. O(log(n))

Its only difference is binary search being conducted on a binary tree

a connected, undirected graph with no cycles.

a rooted ordered tree O(log(n))

The bubble sort algorithm uses the idea of swapping the position of adjacent items to order them. It has a time complexity of O(n²) so it is very inefficient.

A merge sort orders arrays by splitting them into smaller lists, and then reforming them - the ‘divide and conquer’ method. It is quicker than a bubble sort; it has a time complexity of O(nlogn).

finds the shortest path between two nodes in a graph, this is simila to breadth first

Simpler for a machine/computer to evaluate Simpler to code algorithm;

(Starting at LHS of expression) push values/operands on to stack; Each time operator reached pop top two values off stack (and apply operator to them) Push result (of applying operator) to stack; When end of expression is reached the top item of the stack is the result