1.3 Fundamentals of algorithms Flashcards
Define implementation
Creating code to produce a programmed solution
Define depth first graph traversal
A method for traversing a graph that starts at a chosen node and explores as far as possible along each branch away from the starting node before backtracking to visit unvisited nodes. It is often implemented with a recursive algorithm
Define breadth first graph traversal
A method for traversing a graph that explores nodes closest to the starting node first before progressively exploring nodes that are further away. A queue is used to keep track of the nodes to visit
What are the 3 ways of traversing a binary tree and their uses?
- Pre-order: Can be used with expression trees to evaluate the expression using prefix notation
- In-order: The equivalent of a binary search of the tree
- Post-order: Will produce Reverse Polish Notation
Define traversal
The process of reading data from a tree or graph by visiting all of the nodes
Define pre-order traversal
A method of traversing a tree by visiting the root, traversing the left subtree, and traversing the right subtree
Define in-order traversal
A method of traversing a tree by traversing the left subtree, visiting the root, and traversing the right subtree
Define post-order traversal
A method of traversing a tree by traversing the left subtree, traversing the right subtree, and then visiting the root
What are base and general cases of recursion?
A base case of a recursive function is the point at which the function will stop calling itself. The general cases of a recursive function are all the other cases of the function where it calls itself
Define single source
In the Dijkstra’s algorithm it means that the shortest path is calculated from a single starting point
Define shortest path
The shortest distance between two vertices based on the weighting of the edges
Define linear search
A simple search technique that looks through data one item at a time until the search term is found
Define binary search
A technique for searching ordered data that works by splitting datasets in half repeatedly until the search data is found
Define binary tree search
A technique for searching a binary tree that traverses the tree until the search term is found - it will move down the tree depending on if the target node is expected to be found on the left or right of the current node
Define infix notation
Expressions that are written with the operators within the operands
Define postfix notation
Expressions that are written with the operators after the operands - this is also known as Reverse Polish Notation
Define prefix notation
Expressions that are written with the operators before the operands - this is also known as Polish Notation
Why is Reverse Polish Notation used?
An interpreter has no inherent undersanding of the order of mathematical operations, so by using RPN, the need for brackets is removed, and operations can be processed
How do the locations of operands in expressions link to binary trees?
- In-order traversal of a binary tree of an expression would give an expression in infix format
- Post-order traversal of a binary tree of an expression would give an expression in RPN
- Pre-order traversal of a binary tree of an expression would give an expression in Polish Notation
How do you evaluate RPN?
Commonly RPN is evaluated using a stack
Define 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
Define merge sort
A technique for putting data in order by splitting lists into single elements and then merging them back together again
