3 - Fundamentals of Algorithms

A* algorithm

An algorithm that finds the shortest path between two nodes and uses a heuristic function to optimise performance.

Backtracking

A technique for solving problems recursively.

Big O

A formal notation for expressing the time or space complexity of an algorithm.

Binary search

An algorithm to search for an item in a sorted data set. It discards half of the remaining data with each comparison and repeats the process until the item is found or until the data set is exhausted.

Breadth-first search

A method of searching a graph data structure that visits all nodes adjacent to the current node before moving on. Uses a queue to support the process.

Bubble sort

A sorting algorithm that repeatedly compares pairs of values within a list and swaps them if they are out of order.

Constant time

The time complexity of an algorithm where the time taken to run it does not depend on the size of the input data set.

Depth-first search

A method of searching a graph data structure that explores as far as possible along an unexplored branch before backtracking and selecting a new branch to explore. Uses a stack to support the process.

Depth-first tree traversal

An algorithm for traversing a tree data structure that starts at the root node and explores as far as possible along each branch before backtracking.

Dijkstra's shortest path algorithm

An algorithm that finds the shortest path between the start node and all other nodes in a given graph.

Exponential time

The time complexity of an algorithm where the time taken to run it increases by an exponential factor on each single addition to the input data set.

Heuristic

"An approach to solving a problem that will provide an approximate or ""good enough"" solution to an intractable problem."

In-order traversal

A method of traversing a tree so that a node is processed after its left subtree has been examined and before its right subtree has been examined.

Insertion sort

A sorting algorithm that progressively evaluates items in a list and inserts them into the correct place in an ordered sublist.

Linear search

An algorithm that searches for an item in a list of items by systematically examining each item one after another.

Linear time

The time complexity of an algorithm where the time taken to run it rises in direct proportion to the size of the input data set.

Logarithmic time

The time complexity of an algorithm where the time taken to run it is proportional to the logarithm of the size of input data set.

Merge sort

A sorting algorithm that works by repeatedly splitting data into sublists and merging pairs of sublists ordering the items as they are merged.

Post-order traversal

A method of traversing a tree so that a node is processed after both its left and right subtrees have been examined.

Pre-order traversal

A method of traversing a tree so that a node is processed before either its left or right subtrees are examined.

Quick sort

An algorithm that sorts a list by repeatedly selecting a pivot value around which the list is systematically rearranged until the whole list is sorted. R

Shortest path

The sequence of edges between two nodes of a graph with the lowest total weight.

Space complexity

The amount of memory needed to run an algorithm relative to the size of its input.

Time complexity

The amount of time needed to run an algorithm relative to the size of its input.

Tree traversal

The systematic process of visiting (checking/updating) each node in a tree exactly once.