Fundamentals of Algorithms Flashcards
What is Breadth-first traversal?
Start at root
Enqueue node onto the queue
Mark as visited
Repeat steps 2,3 for all nodes connected to head node
Dequeue the front of the queue
Repeat steps 4,5 until queue is empty
What is Depth-first traversal?
A method of searching a graph by navigating to the smallest undiscovered node adjacent to the current node.
Backtracks on itself up and down branches
Uses a stack
Where do you put the dot for pre-order?
left
Where do you put the dot for post-order?
right
Where do you put the dot for in-order?
bottom
What is infix form?
A form of mathematical notation which places the operators between the operands
e.g., 4 + 5 = 9
How do you convert infix to Reverse Polish (postfix)?
Display it like a tree and then do post order traversal
How do you do Reverse Polish Notation with a single stack?
When you encounter an operand, push it onto the stack.
When you encounter an operator, pop two values from the stack and push the result into the stack.
When you have finished i.e. have been through the whole expression, pop the final answer from the stack
What is a Linear Search?
Look through each element in turn until a match is found
Doesn’t work well on long lists as it can take a long time especially if list is not ordered.
What is a Binary Search?
Only works if values in structure are ordered
It works by repeatedly dividing in half the portion of the list that could contain the item, until you’ve narrowed down the possible location to just one.
What is a bubble sort?
A sorting algorithm that works by examining each adjacent elements in the list from left to right, switching their positions if they are out of order.
How does a merge sort work?
The list is divided into the smallest unit (one element)
It continuously cuts down a list into multiple sub lists until each has only one item, then merges those sub lists into a sorted list.
Until finally all the elements are sorted and combined into one list.
( RECURSIVE algorithm split in half on left each element until all separated then move to the right and do the same )
What is an Optimisation Algorithm?
Finds the best possible solution to a problem e.g., Dijksta’s Algorithm
What does Dijksta’s Algorithm do?
It finds the shortest path from the starting node to every other node in a network
How does Dijksta’s keep track of visited nodes?
With a Priority queue
How does Dijksta’s Algorithm work?
Makes note of distances from nodes to start position, at this point only the nodes connected to start will have a value, the others will have a distance of infinity.
Creates list called ‘Unvisited’
Take note the start node is fully explored and choose node closest to the start node, update the table to reflect the shortest distance from A to each node. Mark that node as fully explored.
Repeat step 2, always selecting the node the shortest distance from A which hasn’t been fully explored, continue until every node has been fully explored.
USES PRIORITY QUEUE
