(P1) Fundamentals of Algorithms Flashcards
What is graph traversal?
The process of visiting each vertex in a graph.
What are the two graph traversals?
Depth-first and breadth-first.
Describe depth-first traversal.
A branch is fully explored before backtracking.
Uses a stack and is used navigating mazes.
Describe breadth-first traversal.
A node is fully explored before venturing on the next node.
Uses a queue.
Used for determining the shortest path on an unweighted graph.
What is an algorithm?
A set of instructions which completes a task in a finite time and always terminates.
What is a tree?
A connected acyclic graph.
Describe tree traversal.
Process of visiting each node in a tree.
Unique to trees and must start at the root.
Where should the dot be drawn for a pre-order traversal?
Left.
Where should the dot be drawn for a in-order traversal?
Bottom.
Where should the dot be drawn for a post-order traversal?
Right.
What can pre-order traversal be used for?
Copying trees.
What can an in-order traversal be used for?
Used in binary trees to outputs the contents of a binary tree in ascending order.
What can post-order traversals be used for?
Infix to RPN conversions.
Producing a postfix expression from an expression tree.
Emptying a tree.
How are Infix to RPN and binary trees related?
Infix to RPN involve the making and traversing of a binary tree.
What is an opcode?
An operator.
What is an operand?
Data which is applied to the operator.
When creating an expression tree, what should always be the parent node and the child nodes?
Parents should be the opcode.
Children should be the operands.
What is produced from performing an in-order traversal on an expression tree?
Infix expression.
What is produced from performing an post-order traversal on an expression tree?
Postfix expression.
How do you work out a postfix expression?
Perform the calculation of the opcode and only the two preceding operands and put back into expression. Repeat.
What notation do humans use?
Infix notation.
What does RPN stand for?
Reverse Polish Notation.
What is RPN?
A postfix way of writing expressions.
Eliminates need for brackets and any confusion of the order of execution.
Opcode is written after the operands.
What data structure can be used to evaluate postfix equations?
Stacks.
Why is RPN ideal for interpreters?
RPN can be executed on a stack, making it ideal for interpreters which are based on a stack such as Bytecode or PostScript.
What is the pseudocode for a RPN calculation?
Stack1 <— Stack
RPN <— Array
Op2 <— Single
Op1 <— Single
Result <— Single
For i = 0 to RPN.count - 1
If RPN (i) = operand
Stack1.push (RPN(i))
ElseIf RPN (i) = opcode
Op2 = Stack1.pop
Op1 = Stack1.pop
Result = Perform(RPN(i), Op1, Op2)
End If
End For
Print Stack1.peek
What are the three different searching algorithms?
Linear search, binary search and binary tree search.
Describe a linear search.
Conducted on an unordered list.
Hugh time complexity.
Has one loop.
Time complexity of O(n).
What is pseudocode for a Linear search?
LinearSearch(Target, ArrayofValues)
Boolean Found
Integer Count
Found <— FALSE
Count <— 0
Do Until Found == TRYE or Count == ArrayofValues Count
If Target == ArrayofValues(Count)
Found <— True
Else
Count <— Count + 1
End If
Loop
If Found = True
Output Target found at Count
Else
Output Target not found
End if
Describe a binary search.
Used on any ordered list.
Works by looking at the midpoint of a list and determining if the target is higher or lower.
Time complexity is O(log(n))
What sorting algorithms can be used to order a list?
Merge or bubble sort.
What is the pseudocode for a binary search?
BinarySearch(Target, ArrayorValues)
Integer TopPointer
Integer BottomPointer
Integer Midpoint
Boolean Found
Found <— FALSE
BottomPointer <— 0
TopPointer <— ArrayorValues Count - 1
Do Until Found = True or TopPointer < BottomPointer
Midpoint = int mid TopPointer, BottomPointer
If ArrayofValues(Midpoint) = Target
Found = TRUE
ElseIf ArrayofValues(Midpoint) > Target
TopPointer = Midpointer - 1
ElseIf ArrayofValues(Midpoint) < Target
BottomPointer = Midpoint + 1
End If
Loop
If Found = TRUE
Output Target found at Midpoint
Else
Output Target not found
End if
What method can a binary search be completed through?
Recursion.
What is the time complexity for a binary tree search?
O(log(n))
What is Big O notation?
A way of classifying algorithms based on time and space complexity.
Describe bubble sort.
The idea of swapping the position of adjacent items to order them.
Time complexity of O(n^2)
Very inefficient.
What is pseudocode for a bubble sort?
Integer Max
String Temp
Boolean Swapped
Integer Passes
Max <— List.Count - 1
Swapped <— TRUE
Passes <— 0
Do Until Swapped == FALSE or Max == 0
Swapped <— FALSE
Max <— Max - 1
Passes <— Passes + 1
For a = 0 to Max
If List(a) > List(a + 1)
Temp <— List(a)
List(a) <— List(a + 1)
List(a + 1) <— Temp
Swapped <— TRUE
End If
Next
Loop
OUTPUT Passes
OUTPUT List
Describe merge sort.
Orders arrays by splitting them into smaller lists and them reforming them
Divide and conquer
Quicker than bubble sort
Time complexity of O(nlog(n))
What is an optimisation algorithm?
Finds the best possible solution to the problem posed.
Give an example of an optimisation algorithm.
Dijkstra’s algorithm.
What is the purpose of Dijksta’s algorithm?
Finds the shortest path between two nodes in a graph.
