Fundamentals of Algorithms Flashcards
Traversal
The process of reading data from a tree or graph by visiting all the nodes.
There are two ways of traversing a graph. Name them, and explain what they do.
Depth First - A method that explores as far into a graph as possible before backtracking to visit unvisited nodes.
Breadth First - A method for traversing graphs that visits the nodes closest to a starting point first. A queue is used to keep track of the nodes to visit.
There are three ways of traversing a binary tree. Name them and explain what they do.
Binary Tree - A structure where each node can only have up to two child nodes attached to it.
Pre-Order - a method of traversing a tree by visiting the root, traversing the left subtree, and traversing the right subtree. Basically, Visit, Left, Right
In-Order - Left, Visit, Right (The equivalent of a binary search)
Post-Order - Left, Right, Visit
Recursion
A technique where a function can call itself in order to complete a task
Dijkstra’s Algorithm
https://www.youtube.com/watch?v=5GT5hYzjNoo
Linear Search
A simple search technique that looks through data one item at a time until the search term is found.
Binary Search
A technique for searching data that works by splitting datasets in half repeatedly until the search data is found.
Binary Tree Search
A technique for searching a binary tree that traverses the tree until a search term is found.
Reverse Polish Notation (RPN)
Another term for postfix notation
Infix
Expressions that are written with the operators within the operands, eg 2 + 3
Interpreter
Software that translates and executes programs line by line by converting programming statements either into machine code or by calling instructions to carry out the high-level language statements.
Prefix
Expressions that are written with the operators before the operands, eg + 2 3
Postfix
Expressions that are written with the operators after the operands, eg 2 3 +
Apply Reverse Polish Notation to these expressions:
2 + 3
(5+4)/(4-1)
2 3 +
5 4 + 4 1 - /
Remember, BODMAS is applied, so brackets are evaluated first.
Bubble Sort
A technique for putting data in order by repeatedly stepping through an array, comparing adjacent elements and swapping them if necessary until the array is in order.
Iteration
Repeating the same process several times in order to achieve a result.
Merge Sort
A technique for putting data in order by splitting lists into single elements and then merging them back together again.
