SLR5 Algorithms Flashcards
Breadth-first traversal
“A method of searching a graph where we start at a node and then explore all the neighbouring nodes first, before moving onto the next level neighbours.”
Depth-first traversal
“A method of searching a graph where we start at a node and then explore as far as possible along each branch or path before backtracking.”
Pre-order tree traversal
“This method processes all the nodes of a tree by processing the root, then recursively processing all subtrees.”
Post-order tree traversal
“This method processes all the nodes of a tree by processing all subtrees, then the root.”
In-order tree traversal
“This method processes all the nodes of a tree by recursively processing the left subtree, then the root and, finally, the right subtree.”
Infix form
“A form of mathematical notation which places the operators between the operands – e.g. 4 + 5 = 9.”
Reverse Polish Notation
“A form of mathematical notation in which every operator follows all of its operands. The importance of this in computing is that this notation does not require parentheses, is unambiguous and computers to solve equations written in this way by using stacks.”
Linear search
“Involves examining each entry in turn until a match is found or the end of the file is reached. Unless the file is in some useful order, a serial search has to be used.”
Binary search
“A particularly efficient search method. It only works if records in the file are in sequence. It involves accessing the middle record and determining if the target has been found. If not, the search determines whether the target is before or after the middle record in the sequence. This process is repeated in the area where the target record is expected to be until it is found.”
Bubble sort
“It is inefficient when sorting large amounts of data as the time taken is related to the square of the number of items. If 10 items take 1ms, then 100 times will take 100ms (this is 10 times the number of items and so, the time will be 102 or 100 times longer).”
Merge sort
“A type of divide and conquer algorithm that was incited by John von Neumann. First, the list is divided into the smallest unit (one element), then each element is compared with the adjacent list to sort and combine the two adjacent lists. Finally, all elements are sorted and combined.”
Dijkstra’s shortest path
“A graph search algorithm that solves the single-source shortest-path problem for a graph with non-negative edge path costs, producing a shortest-path tree. This algorithm is often used in routing and as a subroutine in other graph algorithms. It picks the vertex at the shortest distance, calculates the distance to each unvisited neighbour, and updates the neighbours’ distance if smaller. It then marks the visited vertex when done with neighbours.”
“A method of searching a graph where we start at a node and then explore all the neighbouring nodes first, before moving onto the next level neighbours.”
Breadth-first traversal
“A method of searching a graph where we start at a node and then explore as far as possible along each branch or path before backtracking.”
Depth-first traversal
“This method processes all the nodes of a tree by processing the root, then recursively processing all subtrees.”
Pre-order tree traversal
