Fundamentals of Algorithms Flashcards
What are the two ways of traversing a graph and describe them
Depth first - Starts at chosen node and explores as far as possible (deep) along each branch away from the starting node before backtracking.
Breadth first - Starts at chosen node and visits the closest ones first. (a queue can be used to keep track of nodes to visit)
What is a binary tree?
A structure where each node can only have up to 2 child nodes attached to it.
What are the three ways of traversing a binary tree and describe how to do them?
Top Tip: Draw a line below the tree, going all the way around and into every crevasse .
Pre-order - goes to the LEFT of the line (before)
In-order - goes below the line (inline)
Post-order - goes to the RIGHT of the line (after)
What’s the difference between an adjacency matrix and an adjacency array?
They both display the same information, except one uses either a 0 or a 1 to show if is connected to a node whereas lists just display the ones they are connected to. For example:
List - A | B, C
| A | B | C | D |
Array - A | 0 | 1 | 1 | 0 |
Define the term single source in Dijkstra’s algorithm.
It means that the shortest path is calculated from a singular starting point.
Explain the steps involved in following Dijkstra’s algorithm
1) Start from the first vertex
2) Work out the weight/cost for each edge between that vertex and other connected vertices
3) Move on to the next nearest vertex and repeat the process, except taking into account the previous weightings/costs.
4) Repeat this process, storing information about the shortest route (smallest weighting) until you reach the destination vertex.
What is a Linear Search?
A simple search technique that compares items one by one
What is Binary Search?
A technique for searching data that works by splitting datasets in half repeatedly until the search item is found.
What tree traversal would you use to perform a binary tree search?
In-order
What is reverse polish notation/postfix notation
A way of writing mathematical operations where the operators come after the operands (numbers)
What is infix notation?
NORMAL - where expressions are written with the operators within the operands.
What is the easiest method of creating Reverse polish notations?
Use a stack:
1) Push digits onto the stack one by one until you push an operand.
2) Pop all operators and operands out of the stack
What tree traversals would create infix, postfix and prefix mathematical operations?
In-order would produce infix, or normal
Post-order would produce postfix, or Reverse Polish Notation
Pre-order would produce prefix, or Polish Notation
What is prefix notation?
Expressions that are written with their operators before the operands.
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 done.
