Fundamentals of algorithms Flashcards
Breadth-first traversal
A method of traversing a graph by using a queue to visit all the neighbours of the current node before doing the same to each of the neighbours until the entire graph has been explored.
Depth-first traversal
A method of traversing a graph by using a stack to travel as far along one route as possible and then backtracking and doing the same for the remaining routes until the entire graph has been explored.
In-order traversal
A traversal in the order: traverse the left subtree, visit/pop the node then traverse the right subtree.
Post-order traversal
A traversal in the order: traverse the left subtree, traverse the right subtree, then visit/pop the node.
Pre-order traversal
A traversal in the order: visit/pop the node, traverse its left subtree then traverse its right subtree.
Infix notation
A mathematical notation where the operator is written between the operands.
Prefix notation
A mathematical notation where the operator is written before the operands.
Postfix/reverse Polish notation
A mathematical notation where the operator is written after the operands.
Linear search
An algorithm to search a list for a particular item by iterating through the list and checking each element until the required item is located, or the end of the list is reached.
Binary search
An algorithm to search a sorted list for a particular item by repeatedly halving the sublist which could contain the item.
Binary search tree
An algorithm to search a binary tree for a particular item by traversing the tree in the right direction until the item is found.
Bubble sort
A sorting algorithm that iterates through a list, comparing each element to its successor and swapping elements if the successor is greater than the current element. This is repeated until no more swaps can be made.
Merge sort
A divide-and-conquer sorting algorithm that recursively halves the list into sublists until all sublists are of length 1. The sublists are then merged back together in such a way that they are always sorted, until the full single list is obtained.
Dijkstra’s shortest path algorithm
An algorithm to find the shortest path between two nodes on a graph by using a priority queue to keep track of the shortest distance (cost) to each node from the starting node until the destination is found.
