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
Why might Backus-Naur form be used to represent a language instead of Regular Expressions?
Regular expressions cannot support recursion like Backus-Naur can
Regular Expression: what does * mean?
0 or more repetitions
Regular Expression: what does + mean?
1 or more repetitions
Regular Expression: what does ? mean?
Previous character optional
Regular Expression: what does ┃ mean?
Alternative/ or
Regular Expression: what does () mean?
Used to group regular expressions
What is Reverse Polish Notation?
A postfix way of writing expressions. Rather than the opcode being between the operand it is written after the operand.
Can be executed on a stack
What are the advantages of using RPN over infix notation?
Simpler for computer to evaluate
Simpler to code algorithm
Don’t need brackets
In Finite State Machine what is the double circle?
Valid stop state
When it is valid to stop
How does a finite state machine differ from a Turing machine?
Don’t have to worry about tape
Or header
What is meant by the term reject state?
No escape from that state -no way out
Rule won’t be valid if you stop there
What are finite state machines used for?
Used to validate an input
Represent regular expressions in a computer
A less powerful Turing machine
Definition of a Finite State Machine
A FSM is a computing machine that has a fixed set of possible states, a set of inputs that change the state, and a set of possible outputs.
What is the use of a call stack?
Each time a subroutine is called, the return address, parameters, and local variables used int the subroutine are held in a stack frame in the call stack.
These are then all popped from the stack each time the end of a subroutine is reached.
What does recursion look like in Backus-Naur Form?
where a statement is defined in terms of itself e.g.,
<variable> ::= <variable>│<variable>, <variable>
</variable></variable></variable></variable>
What is a Syntax Diagram?
graphical method of representing the syntax of a language, and maps directly to Backus-Naur Form
What is the Travelling Salesman Problem?
Finding the quickest route to traverse all nodes
it will become intractable when you add enough nodes
Which complexity dictates the growth rate?
Factorial
Explain what is meant by the time complexity of an algorithm?
How long it will take an algorithm to complete in relation to the size of the input.
Explain why recursion isn’t suitable for a large array?
Recursion may not be suitable for searching large arrays because each call requires a new stack frame, which can consume a lot of memory.
Define Cardinality
the number of elements in a set.
What is an algorithm?
A (step-by-step) description of how to complete a task
Independent of any programming language;
What is meant by the divide and conquer approach?
Divide and Conquer is an algorithm design paradigm that involves breaking a problem down into smaller, more manageable sub-problems, solving each sub-problem independently, and then combining their solutions to solve the original problem.
What is the format of a transition function?
δ (Current state, Input symbols) = (Next state, Output symbol, Movement)
