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.
